2.3 栈：后进先出的护体真气

2.3 栈：后进先出的护体真气

本节摘要：栈只开放一端（栈顶），进栈出栈都在栈顶完成，纪律是后进先出（LIFO）。这层"限制"换来了极强的语义保证：取到的永远是最近放进去的那个。函数调用栈、括号匹配、撤销操作、表达式求值、深度优先搜索，全都靠这条纪律运转。本节用可跟踪的栈状态演化把两个经典应用走通。

只开一个口的口袋

把栈想成一个只开上口的口袋：放东西（push）和取东西（pop）都只能从口上进行，最先放进去的被压在最底下，最后放进去的离口最近。后放先取不是缺点，恰恰是它存在的理由——很多问题的结构本来就是"最近发生的先处理"：多级撤销要撤的是最近一步；函数返回要接续的是最近调用的那层；嵌套结构最内层配对最先闭合。

用列表就能实现一个栈：尾部当栈顶，append 与 pop 都是尾部操作、均摊 O(1)。数组尾部恰好是整个容器最便宜的操作位，这就是栈招式的物理基础。

括号匹配：栈状态的逐步演化

代码版把每一步的栈内容打印出来，与上图一一对应：

# 括号匹配：栈状态全程可跟踪
def match(text):
    pairs = {")": "(", "]": "[", "}": "{"}
    stack = []
    for ch in text:
        if ch in "([{":
            stack.append(ch)                 # 左括号：压栈
            print(f"读 {ch}：压栈 → 栈 {stack}")
        elif ch in ")]}":
            if not stack or stack[-1] != pairs[ch]:   # 右括号：必须与栈顶配对
                print(f"读 {ch}：栈顶 {stack[-1] if stack else '空'} 无法配对 → 非法")
                return False
            stack.pop()
            print(f"读 {ch}：弹栈配对 → 栈 {stack}")
    return not stack                          # 结束时栈必须为空

print(match("{[()]}"))
# 输出：
# 读 {：压栈 → 栈 ['{']
# 读 [：压栈 → 栈 ['{', '[']
# 读 (：压栈 → 栈 ['{', '[', '(']
# 读 )：弹栈配对 → 栈 ['{', '[']
# 读 ]：弹栈配对 → 栈 ['{']
# 读 }：弹栈配对 → 栈 []
# True
print(match("([)]"))
# 输出：
# 读 (：压栈 → 栈 ['(']
# 读 [：压栈 → 栈 ['(', '[']
# 读 )：栈顶 [ 无法配对 → 非法
# False
​

两种非法一目了然：交错（栈顶不是等着的那个）与未闭合（扫完栈非空）。每个字符进出栈至多一次，O(n) 时间、最坏 O(n) 空间。编译器的语法检查、JSON 与 HTML 的标签配对，都是这道题的工业化变体。

函数调用栈：栈不是数据结构课的玩具

程序运行时，每次函数调用都会压入一个栈帧（参数、局部变量、返回地址），函数返回时弹帧。递归之所以"自己会记账"，靠的就是它——第一章 1.3 的爆栈实验，本质是栈帧叠得超过了栈容量。用打印语句看栈帧进出：

# 观察函数调用栈：帧的压入与弹出
def level(k, depth):
    if k == 0:
        print("  " * depth + "到达地基，开始逐层返回")
        return
    print("  " * depth + f"第 {k} 层压帧")
    level(k - 1, depth + 1)          # 调用下一层：再压一帧
    print("  " * depth + f"第 {k} 层弹帧，继续收尾")

level(3, 0)
# 输出：
# 第 3 层压帧
#   第 2 层压帧
#     第 1 层压帧
#       到达地基，开始逐层返回
#     第 1 层弹帧，继续收尾
#   第 2 层弹帧，继续收尾
# 第 3 层弹帧，继续收尾
​

同一个结构还撑起了逆序输出（压进去什么，弹出来就倒着）、编辑器撤销（每次操作压栈，撤销就是弹栈恢复）、浏览器后退（访问历史压栈）与第四章深度优先搜索的显式栈版本。识别窍门：问题里出现"最近的先处理""嵌套的最内层先结束"，栈就该出场。

演练：O(1) 取最小的最小栈

栈的招式表里没有"查最小"，硬查要 O(n)。但只要在主栈旁边再养一个备忘栈，专门登记"新低"，get_min 就能一步到位——这是"用辅助结构扩招式"的标准打法，后面第七章树状数组的思路与之同源：

# 最小栈：主栈照常进出，备忘栈只登记新低
class MinStack:
    def __init__(self):
        self.st = []        # 主栈：照常进出
        self.mn = []        # 备忘栈：栈顶永远是当前栈内最小值
    def push(self, x):
        self.st.append(x)
        if not self.mn or x <= self.mn[-1]:   # 新来者不大于当前最小，才登记
            self.mn.append(x)
    def pop(self):
        x = self.st.pop()
        if x == self.mn[-1]:                  # 弹走的恰是最小，备忘同步退场
            self.mn.pop()
        return x
    def get_min(self):
        return self.mn[-1]                    # 一步读最小，不用翻栈

s = MinStack()
for x in (5, 2, 7, 2, 9):
    s.push(x)
print("压入 5 2 7 2 9 后当前最小 =", s.get_min())
s.pop(); s.pop()                              # 弹走 9 与 2：备忘栈里还有一个 2 在
print("再弹两个后当前最小 =", s.get_min())
s.pop()                                       # 弹走 7：最小不变
s.pop()                                       # 弹走 2：最小值退役，5 接班
print("2 退役后当前最小 =", s.get_min())
# 输出：
# 压入 5 2 7 2 9 后当前最小 = 2
# 再弹两个后当前最小 = 2
# 2 退役后当前最小 = 5
# 备忘栈只登记"不大于当前最小"的新低，弹栈时同步收缩——get_min 始终一步到位
​

注意登记条件写的是"不大于"而不是"小于"：重复的最小值（两个 2）都要记下，否则先弹掉一个，备忘就提前见底。每步都是 O(1)，代价只是一个至多与主栈等高的辅助栈——空间换时间的老配方。

招式清单与复杂度

⚠️ 常见坑：用列表实现栈时误把 pop(0) 当弹栈——那是弹头部，O(n)，而且破坏 LIFO 语义。栈顶必须锁定在列表尾部。

💡 关键直觉：栈的全部威力来自"限制"——只有一口，反而保证了"栈顶即最近"这条不变量。数据结构设计里，限制即语义。

走火入魔：把栈用到它管不了的地方

**事故一：需要随机访问却上了栈。**栈天生看不见底部与中间，"查栈里有没有某元素"只能弹空再重建，O(n) 还破坏数据。需要按关键字查找的场景属于哈希表（2.5 节）。

**事故二：用栈处理"先来先服务"。**打印任务、消息消费都是队列语义，用栈实现会全面倒序。判断口诀：最近者优先选栈，最早者优先选队列——正是下一节的主角。

本节要点回顾

• 栈的心法：单开口、后进先出；栈顶永远是最近压入的元素，这条不变量支撑起配对、撤销、递归三大应用；
• 括号匹配是栈的教科书应用：左括号压栈、右括号验栈顶，交错与未闭合两种错误都能捕获，O(n) 一趟；
• 函数调用栈每层调用压一帧、返回弹一帧，递归的记账与爆栈都由它解释（呼应 1.3）；
• 识别信号：最近先处理、嵌套最内层先闭合、需要逆序输出；
• 两条纪律：栈顶锁列表尾部（别用 pop(0)），需要随机访问或先来先服务时换结构。

同样是受限的线性表，把唯一出口换到另一头，语义就整个翻转——队列登场。