c++ linked stack详解

C语言中的链式栈（linked stack）是一种基于链表实现的栈，它可以动态地增加或删除元素，并且不用考虑栈的大小限制。

链式栈的实现需要定义一个结构体，该结构体包含一个指向栈顶的指针和链表节点的个数。

struct node {
    int data;
    struct node* next;
};

typedef struct {
    struct node* top;
    int size;
} stack;

在定义结构体之后，我们需要实现以下几个常见的操作：

1. 初始化栈

void init_stack(stack* s) {
    s->top = NULL;
    s->size = 0;
}

2. 判断栈是否为空

int is_empty(stack* s) {
    return s->size == 0;
}

3. 入栈

void push(stack* s, int data) {
    struct node* new_node = (struct node*)malloc(sizeof(struct node));
    new_node->data = data;
    new_node->next = s->top;
    s->top = new_node;
    s->size++;
}

4. 出栈

int pop(stack* s) {
    if (is_empty(s)) {
        printf("Stack is empty.\n");
        return -1;
    }
    int data = s->top->data;
    struct node* temp = s->top;
    s->top = s->top->next;
    free(temp);
    s->size--;
    return data;
}

5. 获取栈顶元素

int top(stack* s) {
    if (is_empty(s)) {
        printf("Stack is empty.\n");
        return -1;
    }
    return s->top->data;
}

6. 清空栈

void clear(stack* s) {
    while (!is_empty(s)) {
        pop(s);
    }
}

这些操作都是基于链表的操作，因此链式栈可以动态地增加或删除元素，并且不用考虑栈的大小限制。但是，由于链式栈的实现需要动态分配内存，因此它的空间复杂度比数组栈要高。在使用链式栈时，需要注意内存泄漏的问题。