栈：一座只从顶端进出的容器

kiracrimson

36人浏览 · 2026-09-07 22:25:31

kiracrimson · 2026-09-07 22:25:31 发布

栈：一座只从顶端进出的容器

为什么需要

前面实现的顺序表、链表，可以在任意位置插入和删除——很灵活，但调用者必须时刻想清楚"数据放到哪、从哪取"。而很多场景根本不想要这种自由，只想要一个约束：先放进去的，后拿出来（后进先出）。撤销上一步、函数调用一层层返回、括号匹配、表达式求值，本质都是"最近的最优先处理"。

与其每次手写，不如把它抽象成一个容器。这个容器就是栈（Stack）。

💡 背景补充：操作系统与编译器也大量使用"栈"：函数调用栈记录返回地址，递归靠它回溯。那是系统维护的栈，这一课我们实现的是用户态的栈，同名不同物，别混。

这节课有一个贯穿始终的观点：数据结构只约束行为，不约束实现。栈规定了后进先出（LIFO，Last In First Out），但"用数组还是链表""要不要预先分配空间"都由我们定。这里用数组实现，通常叫顺序栈。

一个合格的栈对外只暴露一组接口：初始化、销毁、入栈、出栈、取栈顶、判空、求大小。为什么是这几个？因为"后进先出"只需要这些操作，调用方永远不需要随机访问中间的某个元素——接口的数目由需求决定。

更重要的是，调用方不该知道内部是数组还是链表。封装是为了不让任何人绕开这条"只能动栈顶"的纪律，绕过它往往就是 bug 的开始。

核心机制：top 的语义决定一切

数组实现的栈有三个成员：

typedef struct Stack {
    STdataType* a;   // 指向动态数组的指针
    int top;         // "栈顶在哪"的下标
    int capacity;    // 容量
} ST;

a 指向堆上动态开辟的数组，满了就扩容；capacity 记录容量，没有争议。整节课的难点集中在 top 这一格：它到底指哪？

top 有两种自洽的定义，各有配套的初始化、入栈、判满写法：

top 的语义	指向栈顶元素	指向栈顶的下一个位置（= 元素个数）
空栈时 top	-1	0
栈空判据	`top == -1`	`top == 0`
入栈写法	`a[++top] = x`	`a[top++] = x`
满栈判据	`top + 1 == capacity`	`top == capacity`
元素个数	`top + 1`	`top`

两种选谁都行，前提是前后自洽。最容易翻车的是这一组组合：

惯性思维：top 天然该指向栈顶元素，那初始化为 0 天经地义。
事实：这个组合作废——top 等于 0 时，到底"没有数据"还是"有一个数据在下标 0"？分不清。

课上老师把这个点翻来覆去讲，因为它太隐蔽了：整型变量初始化为 0 是再自然不过的习惯。可只要选了"top 指向栈顶元素"，空栈就必须初始化为 -1，哪怕它看着别扭。反过来，想省心用 0 初始化，就得承认 top 指向的是"下一个空位"。

本课代码选第二种：top 初始 0、指向栈顶的下一个位置。好处是 top 的值恰好等于元素个数，和顺序表的 size 语义一致，判满也最直观。

入栈（含扩容）是重头：

void STPush(ST* pst, STdataType x) {
    assert(pst);
    if (pst->top == pst->capacity) {          // 满了才扩容
        int newc = pst->capacity == 0 ? 4 : pst->capacity * 2;
        STdataType* tmp =
            (STdataType*)realloc(pst->a, newc * sizeof(STdataType));
        if (tmp == NULL) {
            perror("realloc fail");
            return;                            // 别继续写，内存没给够
        }
        pst->a = tmp;
        pst->capacity = newc;
    }
    pst->a[pst->top] = x;                      // 先放数据，再移动 top
    pst->top++;
}

两个易错点。其一，扩容倍数前必须特判 capacity == 0：否则 capacity = capacity * 2 恒为 0，第一次入栈就死循环，永远开不出空间。其二，初始 a 是 NULL，而 realloc(NULL, n) 等价于 malloc(n)——第一次入栈时容量恰为 0，一个函数同时承担了"首次分配"和"扩容"两种职责。

📖 参考：《高质量C++/C编程指南》第7章——malloc 申请后应立刻检查返回值是否为 NULL（规则7-2-1）。

💡 背景补充：realloc 可能"原地扩"也可能"搬家换址"，由堆管理器内部决定，调用者不用关心，只认新指针。

出栈、判空相对简单，但藏着边界：

void STPop(ST* pst) {
    assert(pst);
    assert(pst->top > 0);   // 空栈再弹 = 未定义行为，先拦下
    pst->top--;             // 删除不必抹数据，只动 top，旧值会被覆盖
}

bool STEmpty(ST* pst) {
    return pst->top == 0;   // 空为真
}

📖 参考：《高质量C++/C编程指南》第6章——用 assert 在入口检查"不应该发生"的情况，是防御式编程的第一步。

代码演示一：遍历会清空栈

给顺序表、链表写过 Print，给栈写一个试试？别写。从头到尾打印所有元素，本身就把"只能从顶端取"的约束捅穿了。合法的遍历姿势是：循环"取顶 → 弹顶"，直到栈空。

// 访问栈中全部元素。副作用：栈会被清空——这是栈的特性，不是 bug
while (!STEmpty(&st)) {
    STdataType x = STTop(&st);   // 先看栈顶
    STPop(&st);                  // 再弹掉，才能看到下一个
    // 对 x 做点什么……
}

为什么这样设计是合理的？因为现实中"遍历"栈的需求很少见；常见的是只取最近的几个。取一个弹一个，天然符合"处理完最近的就丢掉"的语义——下一个例题里，栈顶数据正好要丢弃，这种"边取边删"就派上用场了。

代码演示二：LeetCode 20 有效的括号

题目（有效的括号）：给定一个只含 ( ) { } [ ] 的字符串，判断括号是否合法配对。

括号配对是栈的教科书级用例：离当前右括号最近的那个左括号，必须先和它配对——这不就是后进先出吗？

算法只有三条规则：

遇到左括号 ( { [，入栈；
遇到右括号，先看栈——栈空，说明右括号多了（如 ")("），非法；栈不空，取栈顶比对，配对就弹掉，不配则非法；
字符串走完，栈必须为空——否则说明左括号多了（如 "(()"）。

用上方实现的栈，解题代码只需写 isValid：

// 注意：OJ 提交时需把上方整套栈实现一并贴入
bool isValid(char* s) {
    ST st;
    STInit(&st);
    while (*s != '\0') {
        if (*s == '(' || *s == '{' || *s == '[') {
            STPush(&st, *s);            // 左括号：入栈，等配对
        } else {                        // 右括号来了
            if (STEmpty(&st)) {         // 栈空：没有可配对的左括号
                STDestory(&st);
                return false;           // 例：")(" 的第一个字符
            }
            char top = STTop(&st);
            STPop(&st);                 // 栈顶就是最近未配对的左括号
            if ((top == '(' && *s != ')') ||
                (top == '{' && *s != '}') ||
                (top == '[' && *s != ']')) {
                STDestory(&st);
                return false;           // 配对不上
            }
        }
        s++;                            // 指针后移在循环体内
    }
    bool ret = STEmpty(&st);            // 走完栈必须空，挡 "(()"
    STDestory(&st);
    return ret;
}

逐用例验证一下逻辑是否自洽：

输入	过程	结论
`"( [] )"`	遇 `(` 入栈 → 遇 `[` 入栈 → 遇 `]` 与栈顶 `[` 配对并弹出 → 遇 `)` 与 `(` 配对并弹出 → 栈空	true
`")("`	遇 `)` 时栈空 → 直接返回	false
`"(()"`	括号全部配完，但栈里还剩一个 `(`	false
`"([)]"`	遇 `]` 栈顶是 `(`，配对不上	false

这题正好呼应前面所有讨论：为什么要 assert 判空、为什么"边取边删"合理、为什么封装的接口够用——解题时我们只碰了 STEmpty / STPush / STTop / STPop，从未直接动 st.top。这就是把栈设计成一组接口的意义：用约束换安全。

常见误区

top 的语义与初始值不匹配：想"指向栈顶元素"却初始化为 0，空栈和单元素栈分不清。选一个方案，配套到底。
空栈直接 pop / 取 top：越界访问，读到随机值。自己写的代码用 assert 兜底；OJ 上没人帮你断言，要手动 STEmpty 判断。
扩容写成 capacity * 2 而忘了容量为 0：0 翻倍还是 0，第一次入栈就卡死。先特判 capacity == 0 给初值（如 4）。
误以为"入栈 1 2 3 4，出栈必为 4 3 2 1"：不一定！边入边出时，出栈可以是 1 2 3 4（入一个弹一个）。LIFO 约束的是同一时刻驻留在栈内的数据的相对次序，不是全局的逆序。
给栈写 Print 全量打印：违背"只动栈顶"。真要访问全部元素，就用"取顶 + 弹顶"的循环，接受栈被清空的结果。
在外部直接 st.top-- 之类"抄小路"访问内部：省几步，却绕过了所有边界检查——就像逃票走野路，省了门票，丢了护栏。