链式栈

链式栈用链表实现，栈顶为链表头部（头结点之后），入栈出栈都在头部操作，无需担心栈满。

typedef struct SNode {
    int data;
    struct SNode *next;
} SNode, *LinkStack;

// 入栈（头插法）
bool Push(LinkStack &S, int x) {
    SNode *s = (SNode *)malloc(sizeof(SNode));
    s->data = x;
    s->next = S->next;  // S 为头结点
    S->next = s;
    return true;
}

// 出栈
bool Pop(LinkStack &S, int &x) {
    if (S->next == NULL) return false;  // 栈空
    SNode *p = S->next;
    x = p->data;
    S->next = p->next;
    free(p);
    return true;
}

时间复杂度：入栈、出栈均为 $O(1)$ ，且链式栈不会栈满。

习题

习题 1

栈的顺序存储和链式存储有何优缺点？

答案与解析

顺序栈：空间连续、实现简单、支持随机访问，但需要预先分配空间，存在栈满溢出风险。

链式栈：空间按需分配、不会栈满，插入/删除都在头部（ $O(1)$ ），但不支持随机访问，每个结点需额外存储指针。

上一章节顺序栈顺序栈的存储结构、入栈出栈取栈顶操作与共享栈。

下一章节栈的经典应用括号匹配、表达式求值与栈的其他典型应用。