栈：把“最后一步”变成“下一步”

有些问题不需要任意位置的插入和删除，反而要求我们始终处理“最近放进去的那一个”。浏览器回退要先撤销最近打开的页面，函数返回要先结束最内层调用，括号闭合要先匹配最近出现但尚未匹配的左括号。它们共享同一种顺序：后进先出。

栈就是把这种顺序写成明确接口的数据结构。元素只能从同一端加入和移除，这一端叫栈顶；另一端叫栈底。接口很少，但边界不能含糊：空栈能不能查看顶部，固定容量装满后怎么办，弹出后旧槽位里的值是否还属于栈，都要由表示规则回答。

本文先建立栈的抽象模型，再用固定数组实现并证明边界正确，随后讨论动态数组、链式表示和共享空间。最后，我们会把同一套“压入—查看—弹出”动作放进括号匹配、表达式求值、函数调用与深度优先搜索中。

后进先出到底约束了什么

设元素依次按 $x_1,x_2,\ldots,x_k$ 压入一个初始为空的栈，中间没有弹出，那么弹出顺序一定是：

这不是“优先处理较大值”或“按时间排序”，而是接口造成的结果。我们无法越过栈顶直接删除中间元素。只要某个元素上方还有更新的元素，它就必须继续等待。

五个常用操作

• push(x)：把 x 放到栈顶；
• pop()：移除并返回当前栈顶；
• peek() 或 top()：返回栈顶，但不修改栈；
• isEmpty()：判断栈是否为空；
• size()：返回当前元素个数。

其中 pop 和 peek 都要求栈非空。固定容量栈的 push 还要求栈未满。抽象接口可以用前置条件表达，也可以让实现返回错误值、抛出异常或扩容；无论选哪种策略，调用方都不能把失败当成一次成功操作。

假设从栈底到栈顶写作 [甲, 乙, 丙]，那么 peek() 返回 丙，栈仍是 [甲, 乙, 丙]；pop() 返回 丙，栈变为 [甲, 乙]。书写状态时先声明方向很有必要，否则同一个列表既可能被理解为“左端是栈顶”，也可能被理解为“右端是栈顶”。本文统一把最右端当作栈顶。

操作序列应当怎样追踪

考虑以下序列：

push(4), push(1), push(3), pop(), push(8), peek(), pop()

逐步记录状态，比只在脑中记答案可靠：

两次弹出的都是“各自时刻最后压入且尚未弹出”的元素。这里的“尚未弹出”很关键：已经离开栈的 3 不会影响后来 8 的位置。

交互实验：亲手改变栈状态

输入一个值并执行操作。面板会同时显示栈顶、元素数量和操作日志；容量固定为 6，因此可以观察上溢与下溢。

小测

固定数组如何准确表示栈

用长度为 capacity 的数组 A[0..capacity-1] 实现栈时，我们让变量 top 表示当前元素个数，也就是下一个可写槽位。于是有效元素恰好位于：

空栈满足 top == 0，满栈满足 top == capacity。只要栈状态合法，就有不变式：

若 top > 0，栈顶元素是 A[top-1]；栈底始终是 A[0]。这种约定把“顶部边界”和“元素数量”合并成一个变量，判断空、满和大小都很直接。

另一种常见约定让 top 直接指向栈顶下标，此时空栈写作 top == -1，栈顶是 A[top]。两种约定都正确，但公式不能混用。本文后续始终采用“top 是元素个数”的约定。

压栈、弹出与查看顶部

PUSH(A, capacity, top, x)
    若 top == capacity：报告上溢
    A[top] = x
    top = top + 1
 
POP(A, top)
    若 top == 0：报告下溢
    top = top - 1
    返回 A[top]
 
PEEK(A, top)
    若 top == 0：报告空栈错误
    返回 A[top - 1]

PUSH 必须先确认有空位，再写 A[top]。如果先递增 top，就会跳过一个槽位；如果满栈时仍写入，就会越过数组边界。

POP 的顺序恰好相反：先把边界向左移动，再读取新边界处的旧栈顶。弹出前 top = k，旧栈顶在 A[k-1]；执行 top = k-1 后，读取 A[top] 正好得到它。

弹出后不必为了维护栈的逻辑正确性而擦除该槽位。假设 [15, 6, 2, 9] 弹出 9，数组的第 3 号槽位可能仍保留比特模式 9，但有效区间已经缩为 A[0..2]，所以这个 9 不再属于栈。若槽位保存对象引用，主动清空可以让对象更早释放；那是资源管理要求，不是 LIFO 语义本身。

为什么操作是常数时间

每个操作只完成常数次比较、下标计算、读写和加减，不会遍历数组。因而固定数组栈的 push、pop、peek、isEmpty 与 size 最坏都是 $O(1)$。

这里的 $O(1)$ 不表示永远成功。满栈时 push 可以在常数时间内报告上溢，空栈时 pop 也可以在常数时间内报告下溢。错误检查本身就是接口的一部分。

一个边界清楚的 C++ 实现

#include <array>
#include <cstddef>
#include <stdexcept>
#include <utility>
 
template <typename T, std::size_t Capacity>
class FixedStack {
private:
    std::array<T, Capacity> data_{};
    std::size_t top_ = 0; // 元素个数，也是下一个可写下标
 
public:
    bool empty() 

这段代码把每个危险下标访问放在边界检查之后。top() 返回常量引用且不改变 top_；pop() 先递减再移动出旧栈顶。模板参数 Capacity 可以是 0，此时栈永远为空且已满，任何 push、pop 都会先抛出异常，不会访问数组槽位。

从不变式检查实现

不变式不仅是定义，也能用来证明每一步没有越界。

对 push：前置检查保证 top < capacity，所以 A[top] 是合法槽位。写入后执行 top + 1，新值至多为 capacity，不变式仍成立，新元素位于有效区间最后一格。

对 pop：前置检查保证 top > 0。递减后新值至少为 0，A[top] 的下标合法；有效区间缩短一格，返回的正是原来的最后一格。

小测

容量策略决定实现的真实代价

抽象栈只规定 LIFO 顺序，没有规定底层一定是固定数组。固定数组、动态数组和链表都能实现相同接口，但它们处理容量和内存的方式不同。

固定数组、动态数组与链式表示

动态数组的 push 在普通情况下只写末尾；容量耗尽时，需要申请更大的连续空间并复制或移动已有元素，因此那一次是 $O(n)$。如果容量按固定倍数增长，一连串 $n$ 次压栈的总搬移量仍是 $O(n)$，所以单次压栈的摊还成本为 $O(1)$。这不等于每一次都是最坏 $O(1)$。

链表把头节点当栈顶：压栈创建节点并让它指向原头部，弹出则让头指针移到下一节点。指针修改是常数次，但节点分配可能失败，也可能比数组末尾写入更慢。链表节点分散，还会失去连续数组的缓存局部性。

如果只需要栈语义，数组末尾或链表头部才是合适端点。在普通数组头部插入并把所有元素右移，虽然结果也能模拟 LIFO，却把 push 变成 $O(n)$；在单链表尾部作栈顶而不保存尾节点的前驱，pop 也可能需要遍历。实现必须让受限端点真正支持常数时间修改。

两个栈共享一段数组

有时两个栈的总元素数有明确上限，但各自峰值不确定。若把长度为 $n$ 的数组硬切成两半，一个栈可能上溢，而另一半仍有大量空位。更灵活的方法是让两个栈从两端相向增长：

• 左栈的 leftTop 是下一个左侧写入位置，从 0 向右增长；
• 右栈的 rightTop 是下一个右侧写入位置，从 n-1 向左增长；
• 当 leftTop > rightTop 时才真正没有空槽。

PUSH_LEFT(x)
    若 leftTop > rightTop：报告上溢
    A[leftTop] = x
    leftTop = leftTop + 1
 
PUSH_RIGHT(x)
    若 leftTop > rightTop：报告上溢
    A[rightTop] = x
    rightTop = rightTop - 1

左栈弹出时先减少 leftTop 再读取；右栈弹出时先增加 rightTop 再读取。两边都只做常数次操作。只有两个栈元素总数达到 $n$ 时才上溢，空间不会因为预先分区而闲置。

选实现时先问三个问题

第一，最大容量能否在创建时确定？若能，固定数组的最坏操作时间和内存上限都清楚。第二，是否允许偶发的线性扩容？普通应用通常能接受动态数组的摊还成本，硬实时路径则可能不能。第三，元素地址是否必须稳定？动态数组扩容可能移动元素，使指向旧槽位的指针和引用失效；独立链表节点通常不会因其他节点入栈而搬家。

小测

括号与表达式为什么适合用栈

扫描文本时，左括号提出一个“以后要完成的匹配任务”。如果又遇到新的左括号，新的任务必须先完成，才能回到外层任务。因此右括号必须匹配最近出现、尚未闭合的左括号，这正是 LIFO。

括号匹配的完整条件

从左到右扫描字符串：

1. 遇到 (、[、{，把它压栈；
2. 遇到右括号，若栈为空，说明缺少左括号；
3. 栈非空时弹出最近的左括号，检查类型是否对应；
4. 扫描结束后，栈必须为空，否则仍有未闭合的左括号。

bool matched(const std::string& text) {
    std::vector<char> stack;
    for (char ch : text) {
        if (ch == '(' || ch == '[' || ch == '{') {
            stack.push_back(ch);
        } else if (ch == ')' || ch ==

([)] 的左右括号数量相等，但扫描到 ) 时栈顶是 [，类型不匹配，所以立即失败。) ( 则在第一个字符就下溢。只比较三类括号的总数量，无法识别顺序和嵌套错误。

每个字符最多入栈一次、出栈一次，时间复杂度是 $O(n)$。最坏情况下字符串前半段全是左括号，辅助空间为 $O(n)$；若最大嵌套深度为 $d$，更精确地说空间是 $O(d)$。

后缀表达式把等待中的操作数放进栈

后缀表达式把运算符写在操作数后面。例如：

中缀：(3 + 4) * 5
后缀：3 4 + 5 *

从左到右扫描后缀记号：数字直接压栈；遇到二元运算符，先弹出右操作数 b，再弹出左操作数 a，计算 a 运算 b，把结果压回。扫描结束时，栈中应当恰好剩一个结果。

EVALUATE_POSTFIX(tokens)
    建立空栈 S
    对每个 token：
        若 token 是数字：PUSH(S, token)
        否则：
            若 SIZE(S) < 2：表达式非法
            b = POP(S)
            a = POP(S)
            PUSH(S, APPLY(token, a, b))
    若 SIZE(S) != 1：表达式非法
    返回 POP(S)

操作数顺序不能颠倒。后缀式 10 3 - 中，先弹出的是 3，它是右操作数；再弹出 10，结果是 $10-3=7$，不是 $3-10$。加法和乘法恰好满足交换律，容易掩盖这个错误，所以测试求值器时应加入减法和除法。

从中缀转后缀时，运算符也会等待

扫描中缀表达式时，数字可以直接输出，运算符却可能要等右侧更高优先级的运算完成。运算符栈记录这些“尚未输出的运算”。对于常见的左结合运算符 + - * /：

• 遇到左括号就压入运算符栈；
• 遇到右括号就持续弹出，直到对应左括号被移除；
• 遇到新运算符时，先弹出栈顶所有优先级不低于它的运算符，再压入新运算符；
• 扫描结束后弹出剩余运算符，若还有括号则表达式非法。

例如 2 + 3 * 4 会得到 2 3 4 * +，因为 * 比 + 更晚进入栈，却更早输出。若加入右结合运算符（常见的幂运算），相同优先级时不能照搬“先弹出”规则；结合性必须成为转换条件的一部分。

交互实验：观察括号栈与操作数栈

切换模式后运行示例，也可以输入自己的括号串或以空格分隔的后缀表达式。后缀模式支持 + - * / 与数字。

小测

调用栈与深度优先搜索是一回事的两种外观

函数 A 调用 B 时，A 必须暂停并记住“B 返回后从哪里继续”。若 B 又调用 C，那么 C 必须先返回给 B，B 才能返回给 A。最近发生的未完成调用最先结束，因此运行时通常用栈保存活动调用的信息。

栈帧记录一次尚未结束的调用

每次调用对应一个栈帧。具体布局由语言实现、编译器和平台决定，但概念上常包括参数、局部状态、返回位置，以及恢复调用者所需的信息。新调用把新帧压到顶部；函数结束弹出顶部帧，继续执行下一帧保存的位置。

例如 main → 处理订单 → 校验库存：执行校验时，顶部是“校验库存”帧；它返回后该帧弹出，“处理订单”重新成为顶部；处理完成后再回到 main。底部调用存活最久，顶部调用最先结束。

递归只是函数调用自己，仍遵循同一规则。每次递归都有独立参数和局部状态。若递归一直没有到达终止条件，或深度超过运行环境可提供的调用栈空间，就会发生调用栈溢出。即使算法的时间复杂度合理，递归深度也必须单独分析。

对于只在末尾调用自身、且返回后不再做工作的尾递归，一些编译器或运行时可以复用当前帧，但不能假设所有语言和构建配置都会进行这种优化。需要严格控制栈深时，显式循环更可预测。

DFS 的活动路径天然是一条栈

深度优先搜索从某个顶点出发，尽可能沿着尚未访问的邻接边继续深入。当前顶点没有未探索邻居时，搜索退回发现它的顶点，继续扫描那里的下一条边。

递归 DFS 可以写成：

DFS_VISIT(u)
    把 u 标记为“访问中”
    对 u 的每个邻居 v：
        若 v 尚未发现：
            parent[v] = u
            DFS_VISIT(v)
    把 u 标记为“已完成”

“访问中”的顶点按祖先到当前顶点形成一条活动路径，也正是递归调用栈中的帧序列。最新发现的顶点位于顶部，搜索从它继续；它完成后弹出，上一层顶点恢复执行。遇到多个连通分量时，从尚未发现的顶点重新启动，最后得到由多棵深度优先树组成的森林。

想保留递归行为，显式栈要保存“做到哪里”

只把顶点压入普通栈，可以得到一种有效的深度优先遍历，但邻居访问次序、完成时刻和递归版本未必一致。递归帧不仅记住顶点 u，还隐含记住 u 的邻接表已经扫描到哪里。要逐步模拟递归，应让显式栈保存帧 {u, nextIndex}：

ITERATIVE_DFS(start)
    发现 start
    PUSH({u: start, nextIndex: 0})
 
    当栈非空：
        frame = TOP()
        若 frame.nextIndex == Adj[frame.u].length：
            标记 frame.u 已完成
            POP()
            继续下一轮
 
        v = Adj[frame.u][frame.nextIndex]
        frame.nextIndex = frame.nextIndex + 1
        若 v 尚未发现：
            parent[v] = frame.u
            发现 v
            PUSH({u: v, nextIndex: 0})

每个顶点最多压栈一次、弹出一次。使用邻接表时，每条邻接记录也只被扫描一次，所以总时间为：

显式帧栈最多保存一条活动路径，最坏有 $|V|$ 个顶点，辅助空间是 $O(|V|)$。递归版本的调用栈也是同一数量级。显式栈不会降低最坏空间阶，但能把容量管理从语言调用栈移到程序控制的数据结构中。

发现时刻与完成时刻形成嵌套区间

为每个顶点记录发现时间 $d[u]$ 和完成时间 $f[u]$，必有：

如果 $v$ 是 $u$ 在 DFS 树中的后代，那么 u 被发现后尚未完成时，v 才会被发现并完成，所以：

这和正确括号的嵌套完全相同：发现 u 像写下左括号，完成 u 像写下配对右括号。若两个顶点互不处于对方的祖先链上，它们的活动区间不会部分交叉，而是彼此分离。栈保证了“内层先结束”，因此产生这种括号结构。

交互实验：递归帧如何驱动 DFS

下面的固定图按界面列出的邻接顺序搜索。每次点击执行一个微步骤，可以看到顶部帧的邻接下标推进、发现新顶点和完成后弹栈。

把这些场景放在一起看，栈保存的其实都是“尚未完成的工作”。括号栈保存尚未闭合的左括号，操作数栈保存尚未被运算符消费的值，调用栈保存尚未返回的函数，DFS 帧栈保存尚未扫描完邻接表的顶点。辨认出这类结构时，先写清每个栈元素代表什么、何时压入、何时弹出、空栈与结束条件，算法通常就已经清楚了一半。

小测