📚 栈

init

动手试试：把令牌压（push）上塔顶；再把它们弹（pop）下来。然后在下方：往括号游戏里喂入任意带括号的字符串——那个栈就是解析器本身。

为什么它重要

栈无处不在：函数调用、撤销/重做、表达式解析、回溯算法。理解栈，就是理解程序如何执行，以及如何解决那些需要"记住"和"撤回"的问题。

核心思想

想想餐厅里一摞盘子。你只能从顶上拿或放。最后放上去的那只盘子，会被最先取走。

后进先出（LIFO）。

这条简单的约束威力惊人：

• 函数调用：当函数 A 调用 B 时，B 的上下文压在顶上。B 返回时被弹出，A 接着往下执行。
• 撤销：每个动作都压栈。撤销则弹出最后一个动作。
• 括号匹配：遇到 '(' 就压栈，遇到 ')' 就弹栈。如果括号是平衡的，最后栈应当为空。

所有操作都是 O(1)——你永远只碰栈顶。

要点回顾

• 压栈（push）、弹栈（pop）、查看栈顶（peek）都是 O(1)
• LIFO 顺序——后进先出
• 用于函数调用栈、表达式求值、回溯
• 既可用数组实现，也可用链表实现

再深入一些

调用栈正是递归函数能够运作的原因——每次调用的局部变量都被压入栈中，返回时再弹出。当递归层数过深时，就会发生栈溢出。栈也是把中缀表达式转换为后缀表达式（调度场算法）以及单趟求值后缀表达式的关键。

实战中的栈

• CPU 调用栈。 你程序里每次函数调用都会压入一个栈帧（返回地址 + 局部变量 + 保存的寄存器）。硬件栈指针是每一颗现代 CPU 上的一个寄存器。当你带着栈回溯信息崩溃时，你读到的就是这个栈，自顶向下。
• 浏览器的撤销/重做。 两个栈：一个存过去的动作，一个用于重做。每一款编辑器（Photoshop、VS Code、Figma）都建立在这个套路之上。
• 用显式栈实现 DFS。 递归是对栈的隐式使用；在很深的图上，你会维护一个显式的栈数组，以免把调用栈压爆。参见 图那一课——它的 DFS 边界本身就是一个栈。
• 机器人中的恢复状态。 在执行一个有风险的动作之前压入上一个"安全"状态，失败时弹回到它——这是运动规划器里 try/except 式恢复机制的基础。
• 编译器。 每个解析器都用栈：移进/归约解析、表达式解析、作用域跟踪。你的代码正是通过栈驱动的、对嵌套结构的识别，变成一棵 AST 的。

数学细节

时间复杂度

Push: O(1)

Pop: O(1)

Peek: O(1)

Search: O(n)

空间

n 个元素需 O(n)

实现

栈操作

let mut stack = Vec::new();

stack.push(1);  // Push onto top
stack.push(2);
stack.push(3);  // Stack: [1, 2, 3] (3 is top)

let top = stack.pop();  // Returns Some(3)
let peek = stack.last(); // Returns Some(&2)

经典应用

• 括号平衡检查
• 函数调用栈
• 撤销/重做功能
• 表达式求值
• DFS 遍历

练习

三道经典的栈题目——每一道都用到了 LIFO 纪律的一种不同方式：

• 最小栈 —— 简单 · 用一个并行的辅助栈跟踪当前最小值，使 getMin 达到 O(1)
• 下一个更大元素 —— 中等 · 一个存放"等待中"下标的单调栈，摊还 O(n)
• 后缀表达式求值 —— 中等 · 把栈当作一台计算机；每一台 RPN 计算器和 JVM 字节码虚拟机都是这样求值表达式的

→ 浏览全部练习题