第 5 章
栈：后进先出的魔法
第五章：栈 — 后进先出的魔法
你把盘子一个个叠起来，取的时候只能从最上面拿。你按了浏览器的"后退"按钮，回到的是你最后访问的那个页面。你在编辑器里按 Ctrl+Z 撤销，撤销的是你最后做的那个操作。
这三个场景有一个共同的数学结构：栈（Stack）。最后放入的元素，最先被取出——Last In, First Out，简称 LIFO。
栈看起来简单得不值一提，但它是计算机科学中最基础的抽象之一。你的程序能调用函数、能递归、能解析表达式、能撤销操作，背后全是栈在工作。理解栈，不只是理解一个数据结构，而是理解计算本身的一个核心机制。
Level 1 · 你需要知道的
1.1 栈的基本概念
栈是一种受限的线性数据结构。它只允许在一端（称为栈顶，top）进行插入和删除操作。
栈支持三个核心操作：
| 操作 | 含义 | 时间复杂度 |
|---|---|---|
push(x) |
将元素 x 压入栈顶 | O(1) |
pop() |
弹出并返回栈顶元素 | O(1) |
peek() / top() |
查看栈顶元素但不弹出 | O(1) |
附加操作：
is_empty()— 判断栈是否为空size()— 返回栈中元素个数
为什么要"受限"？ 数组可以随机访问任意位置，链表可以在任意位置插入删除。栈故意把自己限制成"只能操作栈顶"，这种限制反而带来了语义上的清晰和实现上的高效。当你看到一个栈，你立刻知道：最近放进去的东西会最先出来。这个约束让很多问题的解法变得优雅。
栈的 LIFO 性质的形式化描述：
设栈 S 上依次执行 push(a₁), push(a₂), ..., push(aₙ)，则执行 n 次 pop() 得到的序列是 aₙ, aₙ₋₁, ..., a₁。即：输入序列的逆序。
1.2 Python 中用 list 实现栈
Python 的 list 天然支持栈操作：
class Stack:
"""基于 Python list 的栈实现"""
def __init__(self):
self._data = []
def push(self, item):
"""将元素压入栈顶 — O(1) 均摊"""
self._data.append(item)
def pop(self):
"""弹出并返回栈顶元素 — O(1) 均摊
Raises:
IndexError: 如果栈为空
"""
if self.is_empty():
raise IndexError("pop from empty stack")
return self._data.pop()
def peek(self):
"""查看栈顶元素但不弹出 — O(1)
Raises:
IndexError: 如果栈为空
"""
if self.is_empty():
raise IndexError("peek from empty stack")
return self._data[-1]
def is_empty(self):
"""判断栈是否为空 — O(1)"""
return len(self._data) == 0
def size(self):
"""返回栈中元素个数 — O(1)"""
return len(self._data)
def __repr__(self):
return f"Stack({self._data})"
# 使用示例
s = Stack()
s.push(10)
s.push(20)
s.push(30)
print(s.peek()) # 30
print(s.pop()) # 30
print(s.pop()) # 20
print(s.size()) # 1
为什么不直接用 list？ 在实际工程中，很多人确实直接用 list 的 append 和 pop 来当栈用。封装成类的好处是：
- 接口约束：防止意外使用
insert、del等非栈操作 - 语义清晰：代码里出现
stack.push(x)比items.append(x)更能表达意图 - 错误处理：空栈时给出有意义的错误信息
但如果你在面试或竞赛中，直接用 list 完全没问题：
# 面试/竞赛中的简洁写法
stack = []
stack.append(42) # push
top = stack[-1] # peek
val = stack.pop() # pop
is_empty = len(stack) == 0
1.3 调用栈（Call Stack）
每当你的程序调用一个函数，计算机就在一个叫做"调用栈"的结构上 push 一个栈帧（Stack Frame）。当函数返回时，对应的栈帧被 pop 掉。
def multiply(a, b):
return a * b
def square(x):
return multiply(x, x)
def print_square(n):
result = square(n)
print(result)
print_square(5)
执行 print_square(5) 时，调用栈的变化过程：
步骤 1: print_square(5) 被调用
┌─────────────────┐
│ print_square │ ← 栈顶
│ n = 5 │
└─────────────────┘
步骤 2: square(5) 被调用
┌─────────────────┐
│ square │ ← 栈顶
│ x = 5 │
├─────────────────┤
│ print_square │
│ n = 5 │
└─────────────────┘
步骤 3: multiply(5, 5) 被调用
┌─────────────────┐
│ multiply │ ← 栈顶
│ a = 5, b = 5 │
├─────────────────┤
│ square │
│ x = 5 │
├─────────────────┤
│ print_square │
│ n = 5 │
└─────────────────┘
步骤 4: multiply 返回 25，其栈帧被弹出
┌─────────────────┐
│ square │ ← 栈顶
│ x = 5 │
│ (收到返回值 25) │
├─────────────────┤
│ print_square │
│ n = 5 │
└─────────────────┘
步骤 5: square 返回 25，其栈帧被弹出
┌─────────────────┐
│ print_square │ ← 栈顶
│ n = 5 │
│ result = 25 │
└─────────────────┘
步骤 6: print(25)，然后 print_square 返回，栈清空
（空栈）
递归就是函数调用自身，每次调用都在调用栈上 push 一个新帧：
def factorial(n):
if n <= 1:
return 1
return n * factorial(n - 1)
# factorial(5) 的调用栈最深时有 5 层：
# factorial(1) ← 栈顶
# factorial(2)
# factorial(3)
# factorial(4)
# factorial(5) ← 栈底
每一层都有自己的局部变量 n。这就是递归能"记住"每一层状态的原因——它们存在不同的栈帧里。
1.4 括号匹配
问题：给定一个只包含 ()、[]、{} 的字符串，判断它是否合法。
合法的括号序列："()", "()[]{}", "{[()]}", "([{}])"
不合法的括号序列："(]", "([)]", "{{", ")"
核心思路：遇到左括号就 push，遇到右括号就 pop 并检查是否匹配。
def is_valid_parentheses(s: str) -> bool:
"""
判断括号序列是否合法
时间复杂度：O(n)，每个字符最多被 push 和 pop 各一次
空间复杂度：O(n)，最坏情况全是左括号
"""
stack = []
# 用字典映射右括号 -> 对应的左括号
matching = {')': '(', ']': '[', '}': '{'}
for char in s:
if char in '([{':
# 左括号：压栈
stack.append(char)
elif char in ')]}':
# 右括号：检查栈顶是否匹配
if not stack:
return False # 栈空，没有对应的左括号
if stack.pop() != matching[char]:
return False # 栈顶的左括号类型不匹配
# 遍历结束后，栈应该为空（所有左括号都被匹配了）
return len(stack) == 0
# 测试
assert is_valid_parentheses("()") == True
assert is_valid_parentheses("()[]{}") == True
assert is_valid_parentheses("{[()]}") == True
assert is_valid_parentheses("(]") == False
assert is_valid_parentheses("([)]") == False
assert is_valid_parentheses("{") == False
为什么栈在这里是完美的数据结构？ 因为括号匹配的核心规则是：最后打开的括号必须最先关闭。这正是 LIFO。
1.5 表达式求值
1.5.1 中缀、前缀、后缀表达式
我们日常写的数学表达式是中缀表达式（运算符在操作数中间）：
3 + 4 * 2
计算这个表达式需要知道运算符优先级（先乘后加）和结合性。这对人来说直觉，对计算机来说麻烦。
后缀表达式（又叫逆波兰表达式，Reverse Polish Notation, RPN）把运算符放在操作数后面：
3 4 2 * +
后缀表达式的好处：
- 不需要括号
- 不需要优先级规则
- 从左到右扫描一遍就能求值
1.5.2 后缀表达式求值
算法极其简单：
- 从左到右扫描
- 遇到数字，push 到栈
- 遇到运算符，pop 两个操作数，计算结果，push 回栈
- 最终栈中剩下唯一元素就是结果
def eval_rpn(tokens: list[str]) -> int:
"""
求值逆波兰表达式
tokens: 每个元素是数字字符串或运算符 "+", "-", "*", "/"
时间复杂度：O(n)
空间复杂度：O(n)
"""
stack = []
operators = {'+', '-', '*', '/'}
for token in tokens:
if token in operators:
# 注意：先 pop 出来的是右操作数
b = stack.pop()
a = stack.pop()
if token == '+':
stack.append(a + b)
elif token == '-':
stack.append(a - b)
elif token == '*':
stack.append(a * b)
elif token == '/':
# 注意：题目要求截断除法（向零取整）
stack.append(int(a / b))
else:
stack.append(int(token))
return stack[0]
# 示例："3 + 4 * 2" 的后缀形式
print(eval_rpn(["3", "4", "2", "*", "+"])) # 11
# 示例："(1 + 2) * (3 + 4)" 的后缀形式
print(eval_rpn(["1", "2", "+", "3", "4", "+", "*"])) # 21
1.5.3 中缀转后缀：调度场算法（Shunting-yard Algorithm）
这是 Edsger Dijkstra 在 1961 年发明的算法，名字来源于铁路调度场——火车车厢在不同轨道间被重新排列，就像 token 在输出队列和操作符栈之间被重新排列。
算法规则：
- 遇到数字：直接输出
- 遇到左括号
(：push 到操作符栈 - 遇到右括号
)：把操作符栈中的元素 pop 并输出，直到遇到左括号（左括号丢弃） - 遇到运算符 op：
- 当栈顶运算符的优先级 ≥ op 的优先级时，pop 并输出
- 然后将 op push 到栈
- 扫描完毕：把操作符栈中剩余的运算符全部 pop 并输出
def infix_to_postfix(expression: str) -> list[str]:
"""
中缀表达式转后缀表达式（调度场算法）
支持 +, -, *, / 和括号
假设输入是合法的，数字和运算符之间用空格分隔
"""
precedence = {'+': 1, '-': 1, '*': 2, '/': 2}
output = []
op_stack = []
tokens = expression.split()
for token in tokens:
if token.lstrip('-').isdigit():
# 数字（包括负数）
output.append(token)
elif token == '(':
op_stack.append(token)
elif token == ')':
# pop 直到遇到左括号
while op_stack and op_stack[-1] != '(':
output.append(op_stack.pop())
op_stack.pop() # 丢弃左括号
elif token in precedence:
# 运算符：pop 所有优先级 >= 当前的运算符
while (op_stack and
op_stack[-1] != '(' and
op_stack[-1] in precedence and
precedence[op_stack[-1]] >= precedence[token]):
output.append(op_stack.pop())
op_stack.append(token)
# 把栈中剩余的运算符全部输出
while op_stack:
output.append(op_stack.pop())
return output
# 测试
print(infix_to_postfix("3 + 4 * 2"))
# ['3', '4', '2', '*', '+']
print(infix_to_postfix("( 1 + 2 ) * ( 3 + 4 )"))
# ['1', '2', '+', '3', '4', '+', '*']
print(infix_to_postfix("3 + 4 * 2 / ( 1 - 5 )"))
# ['3', '4', '2', '*', '1', '5', '-', '/', '+']
完整的求值流程：中缀 → 调度场算法 → 后缀 → 后缀求值 → 结果
def evaluate_expression(expression: str) -> float:
"""完整的表达式求值：中缀 → 后缀 → 求值"""
postfix = infix_to_postfix(expression)
return eval_rpn(postfix)
print(evaluate_expression("3 + 4 * 2")) # 11
print(evaluate_expression("( 1 + 2 ) * ( 3 + 4 )")) # 21
1.6 最小栈
问题：设计一个栈，除了 push、pop、peek 之外，还要支持 get_min() 操作，返回栈中的最小元素。所有操作都要求 O(1) 时间。
关键洞察：如果我们只用一个变量记录当前最小值，当最小值被 pop 掉之后，我们就不知道新的最小值是什么了。解决方案是：用一个辅助栈，同步记录每个状态下的最小值。
class MinStack:
"""
支持 O(1) 获取最小值的栈
思路：维护一个辅助栈 min_stack，其栈顶始终是当前栈中的最小值。
每次 push 时，同时在 min_stack 中记录新的最小值。
每次 pop 时，同时 pop min_stack。
"""
def __init__(self):
self._stack = []
self._min_stack = [] # min_stack[i] = min(stack[0..i])
def push(self, val: int) -> None:
self._stack.append(val)
# 如果 min_stack 为空，或者新值 <= 当前最小值，push 新最小值
if not self._min_stack or val <= self._min_stack[-1]:
self._min_stack.append(val)
else:
# 否则重复 push 当前最小值（保持两个栈同步）
self._min_stack.append(self._min_stack[-1])
def pop(self) -> int:
self._min_stack.pop()
return self._stack.pop()
def peek(self) -> int:
return self._stack[-1]
def get_min(self) -> int:
"""O(1) 获取当前栈中的最小值"""
return self._min_stack[-1]
# 使用示例
ms = MinStack()
ms.push(5)
ms.push(3)
ms.push(7)
ms.push(1)
print(ms.get_min()) # 1
ms.pop() # 弹出 1
print(ms.get_min()) # 3
ms.pop() # 弹出 7
print(ms.get_min()) # 3
ms.pop() # 弹出 3
print(ms.get_min()) # 5
空间优化：上面的实现中，min_stack 和主栈一样长。可以只在最小值发生变化时才 push 到 min_stack，但 pop 时的逻辑会更复杂。对于面试来说，上面的写法最清晰。
Level 2 · 深入理解
2.1 调用栈帧的内部结构
在 Level 1 中我们看到了调用栈的宏观行为。现在让我们深入到单个栈帧内部。
当一个函数被调用时，CPU 会在调用栈上分配一块内存——栈帧（Stack Frame）。一个典型的栈帧包含：
高地址
┌──────────────────────────┐
│ 调用者传入的参数 │ (由调用者 push)
├──────────────────────────┤
│ 返回地址 │ (call 指令自动 push)
├──────────────────────────┤ ← 帧指针 (Frame Pointer, FP/RBP)
│ 保存的上一帧的帧指针 │
├──────────────────────────┤
│ 局部变量 1 │
│ 局部变量 2 │
│ ... │
├──────────────────────────┤
│ 临时计算空间 │
├──────────────────────────┤ ← 栈指针 (Stack Pointer, SP/RSP)
低地址
各部分的作用：
-
参数：调用者传给被调用者的数据。在 x86-64 中，前 6 个整数参数通过寄存器传递（rdi, rsi, rdx, rcx, r8, r9），多余的才通过栈传递。
-
返回地址：函数执行完毕后，CPU 应该跳回到哪条指令继续执行。这是
call指令自动 push 的。 -
保存的帧指针：用于恢复上一帧的基址，形成一个栈帧链表。
-
局部变量：函数内定义的变量存放在这里。
-
临时空间：表达式计算的中间结果。
Python 中的等价物：
虽然 Python 使用虚拟机而不是直接操作硬件栈，但概念是一样的。Python 的每个栈帧（PyFrameObject）包含：
import sys
def show_frame_info():
frame = sys._getframe() # 获取当前栈帧
print(f"函数名: {frame.f_code.co_name}")
print(f"局部变量: {frame.f_locals}")
print(f"行号: {frame.f_lineno}")
print(f"调用者: {frame.f_back.f_code.co_name}")
def caller():
x = 42
show_frame_info()
caller()
# 输出：
# 函数名: show_frame_info
# 局部变量: {'frame': <frame at 0x...>}
# 行号: 5
# 调用者: caller
2.2 栈溢出（Stack Overflow）
操作系统为每个线程分配固定大小的栈空间（通常 1-8 MB）。当递归太深或局部变量太大时，栈空间耗尽，就会发生栈溢出。
# 这会导致 RecursionError（Python 的栈溢出保护）
def infinite_recursion():
return infinite_recursion()
# Python 默认递归深度限制是 1000
import sys
print(sys.getrecursionlimit()) # 1000
# 即使不是无限递归，深度太大也会溢出
def deep_recursion(n):
if n == 0:
return 0
return deep_recursion(n - 1) + 1
# deep_recursion(10000) # RecursionError!
栈溢出的常见原因：
- 无限递归：忘记写基础情况（base case），或基础情况永远不被满足
- 递归深度过大：输入数据量大，递归层数达到数千或数万
- 局部变量过大：在函数内分配巨大的数组（C/C++ 中更常见）
防范策略：
# 策略 1：增大递归限制（治标不治本）
sys.setrecursionlimit(100000)
# 策略 2：改用迭代（用显式栈替代递归，见 2.5 节）
# 策略 3：尾递归优化（Python 不支持，但其他语言如 Scheme 支持）
# 尾递归：递归调用是函数的最后一个操作
def factorial_tail(n, acc=1):
if n <= 1:
return acc
return factorial_tail(n - 1, n * acc) # 尾调用
2.3 用栈实现 DFS
深度优先搜索（DFS）的递归版本本质上就是利用调用栈。我们可以用显式栈来实现完全等价的非递归版本。
图的 DFS — 递归版：
def dfs_recursive(graph: dict, start: str, visited: set = None) -> list:
"""
图的 DFS（递归版）
graph: 邻接表 {node: [neighbors]}
"""
if visited is None:
visited = set()
visited.add(start)
result = [start]
for neighbor in graph[start]:
if neighbor not in visited:
result.extend(dfs_recursive(graph, neighbor, visited))
return result
图的 DFS — 显式栈版：
def dfs_iterative(graph: dict, start: str) -> list:
"""
图的 DFS（显式栈版）
注意：遍历顺序可能与递归版不完全相同（取决于邻居的 push 顺序），
但都是有效的 DFS。
"""
visited = set()
stack = [start]
result = []
while stack:
node = stack.pop()
if node in visited:
continue
visited.add(node)
result.append(node)
# 将邻居逆序 push，这样先 push 的后处理，
# 保证遍历顺序与递归版一致
for neighbor in reversed(graph[node]):
if neighbor not in visited:
stack.append(neighbor)
return result
# 测试
graph = {
'A': ['B', 'C'],
'B': ['D', 'E'],
'C': ['F'],
'D': [],
'E': ['F'],
'F': []
}
print(dfs_recursive(graph, 'A')) # ['A', 'B', 'D', 'E', 'F', 'C']
print(dfs_iterative(graph, 'A')) # ['A', 'B', 'D', 'E', 'F', 'C']
二叉树的前序遍历 — 显式栈版：
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def preorder_iterative(root: TreeNode) -> list[int]:
"""前序遍历：根 → 左 → 右"""
if not root:
return []
result = []
stack = [root]
while stack:
node = stack.pop()
result.append(node.val)
# 先 push 右子树，再 push 左子树
# 因为栈是 LIFO，所以左子树会先被处理
if node.right:
stack.append(node.right)
if node.left:
stack.append(node.left)
return result
2.4 用两个栈实现队列
问题：用两个栈实现一个队列，支持 enqueue（入队）和 dequeue（出队）操作。
核心思想：栈是 LIFO，队列是 FIFO。如果我们把一个栈的元素全部倒入另一个栈，顺序就反转了。两次反转 = 原始顺序 = FIFO。
class QueueWithTwoStacks:
"""
用两个栈实现队列
in_stack: 负责入队（所有 enqueue 操作都 push 到这里）
out_stack: 负责出队（dequeue 时从这里 pop）
当 out_stack 为空且需要 dequeue 时，
把 in_stack 的所有元素倒入 out_stack。
摊还分析：每个元素最多被 push/pop 各两次（进 in_stack 一次，
出 in_stack 一次，进 out_stack 一次，出 out_stack 一次），
所以每个操作的摊还时间复杂度是 O(1)。
"""
def __init__(self):
self._in_stack = [] # 入队栈
self._out_stack = [] # 出队栈
def enqueue(self, item) -> None:
"""入队 — O(1)"""
self._in_stack.append(item)
def dequeue(self):
"""出队 — 摊还 O(1)"""
if not self._out_stack:
# out_stack 为空，把 in_stack 的元素全部倒过来
if not self._in_stack:
raise IndexError("dequeue from empty queue")
while self._in_stack:
self._out_stack.append(self._in_stack.pop())
return self._out_stack.pop()
def peek(self):
"""查看队首元素 — 摊还 O(1)"""
if not self._out_stack:
if not self._in_stack:
raise IndexError("peek from empty queue")
while self._in_stack:
self._out_stack.append(self._in_stack.pop())
return self._out_stack[-1]
def is_empty(self) -> bool:
return not self._in_stack and not self._out_stack
def size(self) -> int:
return len(self._in_stack) + len(self._out_stack)
# 测试
q = QueueWithTwoStacks()
q.enqueue(1)
q.enqueue(2)
q.enqueue(3)
print(q.dequeue()) # 1 (FIFO!)
q.enqueue(4)
print(q.dequeue()) # 2
print(q.dequeue()) # 3
print(q.dequeue()) # 4
摊还分析的形式化证明：
使用势能法（Potential Method）。定义势能函数 Φ = in_stack 中的元素数量。
enqueue：实际代价 = 1（push 到 in_stack），Φ 增加 1。摊还代价 = 1 + 1 = 2。dequeue（out_stack 非空）：实际代价 = 1（pop from out_stack），Φ 不变。摊还代价 = 1。dequeue（out_stack 为空，in_stack 有 k 个元素）：实际代价 = k（倒入）+ 1（pop），Φ 减少 k。摊还代价 = (k + 1) - k = 1。
所以每个操作的摊还代价都是 O(1)。
2.5 递归消除：用显式栈替代递归的通用方法
任何递归都可以改写为迭代+显式栈。通用方法如下：
思路：模拟调用栈。递归函数的每个"栈帧"就是我们显式栈中的一个元素。栈帧需要记录：当前的参数、执行到哪一步了（模拟"返回地址"）、中间结果。
示例：递归的归并排序 → 迭代版
先看递归版：
def merge_sort_recursive(arr: list) -> list:
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort_recursive(arr[:mid])
right = merge_sort_recursive(arr[mid:])
return merge(left, right)
def merge(left: list, right: list) -> list:
result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
result.extend(left[i:])
result.extend(right[j:])
return result
通用递归消除模板：
def recursive_to_iterative_template():
"""
通用模板：将递归转换为迭代
核心思想：
1. 用显式栈模拟调用栈
2. 每个栈帧记录：参数 + 状态（执行到哪一步）+ 中间结果
3. 用状态机模拟递归函数中不同"阶段"的执行
"""
# 定义栈帧
# frame = (args, state, partial_results)
stack = [(initial_args, 'ENTER', {})]
return_value = None
while stack:
args, state, partial = stack[-1]
if state == 'ENTER':
# 对应递归函数的入口
if base_case(args):
return_value = base_result(args)
stack.pop()
else:
# 准备第一次递归调用
stack[-1] = (args, 'AFTER_FIRST_CALL', partial)
stack.append((sub_args_1, 'ENTER', {}))
elif state == 'AFTER_FIRST_CALL':
# 第一次递归返回了
partial['first_result'] = return_value
# 准备第二次递归调用
stack[-1] = (args, 'AFTER_SECOND_CALL', partial)
stack.append((sub_args_2, 'ENTER', {}))
elif state == 'AFTER_SECOND_CALL':
# 第二次递归也返回了
partial['second_result'] = return_value
# 合并结果
return_value = combine(partial['first_result'],
partial['second_result'])
stack.pop()
return return_value
具体示例：用显式栈实现树的中序遍历
def inorder_iterative(root: TreeNode) -> list[int]:
"""
中序遍历：左 → 根 → 右
思路：不断往左走并压栈，走到底后弹出处理，再转向右子树
"""
result = []
stack = []
current = root
while current or stack:
# 一路向左，全部压栈
while current:
stack.append(current)
current = current.left
# 弹出栈顶（最左的未处理节点）
current = stack.pop()
result.append(current.val)
# 转向右子树
current = current.right
return result
什么时候应该用显式栈替代递归？
- 递归深度可能很大（> 1000）：Python 默认递归限制 1000 层
- 性能敏感的场景：函数调用有开销（创建栈帧、保存寄存器等）
- 需要更精细的控制：比如需要在遍历过程中暂停、恢复
Level 3 · 想知道更多
3.1 栈的历史
栈的概念并非一开始就存在于计算机中。它的发明经历了几个关键节点：
1946 年 — Alan Turing 的子程序概念
Alan Turing 在为 ACE（Automatic Computing Engine）编写的设计报告中，描述了"子程序"（subroutine）的概念——一段可以被重复调用的代码。但他还没有明确栈的概念；当时的子程序是通过修改指令中的地址来实现"返回"的，不支持递归。
1955 年 — Friedrich Bauer 和 Klaus Samelson
德国慕尼黑工业大学的 Friedrich Bauer 和 Klaus Samelson 独立发明了栈数据结构（他们称之为 "Keller" ——德语中"地窖"的意思，形象地比喻为"从上方存取物品的地窖"）。他们将栈用于翻译算术表达式，这是栈在编译器中应用的起源。
1957 年 — 栈专利
Bauer 和 Samelson 为"自动计算机中的将表达式逐步处理为子表达式序列的方法"申请了专利（德国专利 DE1094019）。这可能是计算机科学中最早的软件相关专利之一。
1958 年 — 硬件栈的出现
Charles Hamblin 在澳大利亚提出了将栈直接作为处理器架构一部分的想法，即栈机（Stack Machine）。后来 Burroughs B5000（1961年）成为第一台基于栈架构的商用计算机。
1960 年 — 递归的争论
ALGOL 60 语言委员会关于是否支持递归进行了激烈的争论。支持递归就意味着需要运行时栈（call stack）。Dijkstra 强烈主张支持递归，最终这一特性被写入 ALGOL 60 标准，而调用栈也从此成为几乎所有编程语言的标配。
3.2 Dijkstra 的调度场算法
Edsger W. Dijkstra 在 1961 年发表了调度场算法（Shunting-yard Algorithm），用于将中缀表达式转换为后缀表达式（或直接求值）。这个算法之所以重要，是因为它优雅地解决了运算符优先级和结合性的问题。
算法名称的由来：
铁路调度场（Shunting yard）是一种用于重新排列火车车厢顺序的铁路设施。车厢从一条轨道进入，通过侧线（siding）的暂存，以不同的顺序从另一条轨道出去。在算法中：
- 输入轨道 = 中缀表达式的 token 流
- 侧线 = 操作符栈
- 输出轨道 = 后缀表达式
处理运算符结合性：
左结合运算符（如 +、-、*、/）：当栈顶优先级 ≥ 当前运算符时 pop。 右结合运算符（如 幂运算 ^）：当栈顶优先级 > 当前运算符时才 pop。
def shunting_yard_full(expression: str) -> list[str]:
"""
完整版调度场算法，支持右结合运算符和一元运算符
"""
precedence = {'+': 2, '-': 2, '*': 3, '/': 3, '^': 4}
right_associative = {'^'}
output = []
op_stack = []
tokens = tokenize(expression) # 假设有一个 tokenizer
for token in tokens:
if is_number(token):
output.append(token)
elif is_function(token):
op_stack.append(token)
elif token == '(':
op_stack.append(token)
elif token == ')':
while op_stack[-1] != '(':
output.append(op_stack.pop())
op_stack.pop() # 丢弃 '('
# 如果栈顶是函数，也要弹出
if op_stack and is_function(op_stack[-1]):
output.append(op_stack.pop())
elif token in precedence:
while (op_stack and
op_stack[-1] != '(' and
op_stack[-1] in precedence and
(precedence[op_stack[-1]] > precedence[token] or
(precedence[op_stack[-1]] == precedence[token] and
token not in right_associative))):
output.append(op_stack.pop())
op_stack.append(token)
while op_stack:
output.append(op_stack.pop())
return output
Dijkstra 为什么发明这个算法？ 在 1960 年代初期，编译器需要将人类写的表达式转换为机器指令。中缀表达式对机器来说难以处理（需要考虑优先级和括号），而后缀表达式可以用一个简单的栈机来执行。调度场算法就是这个转换的关键步骤。
3.3 栈在编译器中的角色
栈在编译器和解释器的多个阶段都扮演重要角色：
1. 词法分析（Lexical Analysis）
某些词法分析器使用栈来处理嵌套的注释或字符串插值：
# Python f-string 的嵌套解析需要栈
# f"{'nested' + f'{42}'}" — 花括号可以嵌套
2. 语法分析（Parsing）
移进-归约解析（Shift-Reduce Parsing） 是一种自底向上的语法分析方法，核心数据结构就是栈：
输入: id + id * id
语法: E → E + E | E * E | id
解析过程（简化）：
栈 | 输入 | 动作
| id + id * id | 移进
id | + id * id | 归约 (id → E)
E | + id * id | 移进
E + | id * id | 移进
E + id | * id | 归约 (id → E)
E + E | * id | 移进（* 优先级高，不归约 E+E）
E + E * | id | 移进
E + E * id | | 归约 (id → E)
E + E * E | | 归约 (E * E → E)
E + E | | 归约 (E + E → E)
E | | 接受
3. 运行时的虚拟机
Python 的字节码解释器（CPython VM）就是一个基于栈的虚拟机：
import dis
def add(a, b):
return a + b
dis.dis(add)
# 输出：
# 0 LOAD_FAST 0 (a) ← push a 到操作数栈
# 2 LOAD_FAST 1 (b) ← push b 到操作数栈
# 4 BINARY_ADD ← pop 两个操作数，push 结果
# 6 RETURN_VALUE ← pop 结果并返回
Java 的 JVM 也是基于栈的虚拟机。相比之下，Lua 的 VM 和 Android 的 Dalvik VM 是基于寄存器的。
3.4 Forth 语言：完全基于栈的编程
Forth 是 Charles Moore 在 1970 年发明的编程语言，它的独特之处在于：程序员直接操作栈。没有变量声明，没有表达式语法，一切都是通过栈操作完成的。
\ Forth 中计算 (3 + 4) * 5
3 4 + 5 * \ 结果：35
\ 定义一个求平方的 "word"（函数）
: square ( n -- n^2 ) dup * ;
\ 使用
7 square . \ 输出 49
\ 定义阶乘
: factorial ( n -- n! )
1 swap \ 栈：1 n
1+ 1 do \ 循环 i 从 1 到 n
i * \ 累乘
loop
;
5 factorial . \ 输出 120
Forth 的设计哲学：
- 极简：整个语言核心可以用几 KB 实现
- 可扩展：定义新 word 就是扩展语言
- 直接：程序员显式控制数据在栈上的流动
Forth 至今仍在嵌入式系统中使用（如 Open Firmware，Sun/Apple 的启动固件）。PostScript（PDF 的前身）和 Bitcoin Script 也是栈式语言。
用 Python 实现一个简化的 Forth 解释器：
class ForthInterpreter:
"""简化的 Forth 解释器"""
def __init__(self):
self.stack = []
self.dictionary = {} # 用户定义的 words
# 内置操作
self.builtins = {
'+': lambda: self._binary_op(lambda a, b: a + b),
'-': lambda: self._binary_op(lambda a, b: a - b),
'*': lambda: self._binary_op(lambda a, b: a * b),
'/': lambda: self._binary_op(lambda a, b: a // b),
'dup': lambda: self.stack.append(self.stack[-1]),
'drop': lambda: self.stack.pop(),
'swap': lambda: self._swap(),
'over': lambda: self.stack.append(self.stack[-2]),
'.': lambda: print(self.stack.pop()),
'.s': lambda: print(self.stack),
}
def _binary_op(self, op):
b = self.stack.pop()
a = self.stack.pop()
self.stack.append(op(a, b))
def _swap(self):
self.stack[-1], self.stack[-2] = self.stack[-2], self.stack[-1]
def execute(self, code: str):
tokens = code.split()
i = 0
while i < len(tokens):
token = tokens[i]
if token == ':':
# 定义新 word
name = tokens[i + 1]
body = []
i += 2
while tokens[i] != ';':
body.append(tokens[i])
i += 1
self.dictionary[name] = body
elif token in self.builtins:
self.builtins[token]()
elif token in self.dictionary:
# 执行用户定义的 word（递归）
self.execute(' '.join(self.dictionary[token]))
else:
# 尝试作为数字 push
self.stack.append(int(token))
i += 1
# 使用
forth = ForthInterpreter()
forth.execute(": square dup * ;")
forth.execute("7 square .") # 49
forth.execute("3 4 + 5 * .") # 35
Level 4 · 实战与面试
4.1 Python list 作为栈的性能特性
Python 的 list 底层是一个动态数组。append 和 pop（末尾操作）的时间复杂度是 O(1) 均摊。
为什么是"均摊"而不是严格 O(1)？
当动态数组满了需要扩容时，Python 会分配一个更大的数组（通常是原来的 1.125 倍左右），然后把所有元素复制过去。这一次操作是 O(n) 的，但由于扩容的频率越来越低，分摊到每次 append 上仍然是 O(1)。
import sys
# 观察 list 的内存分配策略
lst = []
prev_size = 0
for i in range(100):
new_size = sys.getsizeof(lst)
if new_size != prev_size:
print(f"len={i:3d}, size={new_size:5d} bytes, "
f"capacity≈{(new_size - 56) // 8}") # 64-bit system
prev_size = new_size
lst.append(i)
# 输出（大致）：
# len= 0, size= 56 bytes, capacity≈0
# len= 1, size= 88 bytes, capacity≈4
# len= 5, size= 120 bytes, capacity≈8
# len= 9, size= 184 bytes, capacity≈16
# len= 17, size= 248 bytes, capacity≈24
# ...
与 collections.deque 的对比：
deque 也可以用作栈（用 append/pop），且也是 O(1)。区别在于：
list：连续内存，cache 友好，但头部插入/删除是 O(n)deque：双向链表实现（实际是块链表），两端操作都是 O(1)
对于纯栈操作（只操作末尾），list 通常更快，因为内存更紧凑。
import timeit
# 性能对比
setup = "from collections import deque"
# list 作为栈
t_list = timeit.timeit(
"s = []\nfor i in range(10000): s.append(i)\nfor i in range(10000): s.pop()",
number=1000
)
# deque 作为栈
t_deque = timeit.timeit(
"s = deque()\nfor i in range(10000): s.append(i)\nfor i in range(10000): s.pop()",
setup=setup,
number=1000
)
print(f"list: {t_list:.3f}s")
print(f"deque: {t_deque:.3f}s")
# 通常 list 略快或持平
4.2 面试高频题详解
4.2.1 有效的括号（LeetCode #20）
这就是 Level 1 中的括号匹配问题。面试时注意的陷阱：
def isValid(s: str) -> bool:
stack = []
mapping = {')': '(', ']': '[', '}': '{'}
for char in s:
if char in mapping:
# 陷阱 1：栈为空时 pop 会报错
top = stack.pop() if stack else '#'
if top != mapping[char]:
return False
else:
stack.append(char)
# 陷阱 2：别忘了检查栈是否为空
return not stack
面试追问：
- "如果输入中有非括号字符怎么办？"→ 忽略即可
- "如果只有一种括号呢？"→ 用计数器就行，不需要栈
- "如果要找出第一个不匹配的位置呢？"→ 栈中存索引
4.2.2 每日温度（LeetCode #739）— 单调栈
问题：给定每日温度数组，返回对于每一天，需要等多少天才能等到更高的温度。
输入: [73, 74, 75, 71, 69, 72, 76, 73]
输出: [1, 1, 4, 2, 1, 1, 0, 0]
暴力解法是 O(n²)。使用单调栈可以做到 O(n)。
def daily_temperatures(temperatures: list[int]) -> list[int]:
"""
单调栈解法
维护一个单调递减栈（栈中存索引）。
对于每个新温度，如果它比栈顶对应的温度高，
说明栈顶那天终于等到了更高温度。
时间复杂度：O(n) — 每个元素最多入栈一次、出栈一次
空间复杂度：O(n)
"""
n = len(temperatures)
result = [0] * n
stack = [] # 存索引，对应温度单调递减
for i in range(n):
# 当前温度比栈顶高：栈顶等到了答案
while stack and temperatures[i] > temperatures[stack[-1]]:
prev_idx = stack.pop()
result[prev_idx] = i - prev_idx
stack.append(i)
# 栈中剩余的元素，说明后面没有更高温度，result 保持 0
return result
# 测试
temps = [73, 74, 75, 71, 69, 72, 76, 73]
print(daily_temperatures(temps))
# [1, 1, 4, 2, 1, 1, 0, 0]
单调栈的本质：对于数组中的每个元素，找到它右边（或左边）第一个比它大（或小）的元素。这是一类问题的通用解法，我们会在第 6 章深入讨论。
4.2.3 逆波兰表达式求值（LeetCode #150）
这就是 Level 1 中的 eval_rpn。面试时的注意点：
def evalRPN(tokens: list[str]) -> int:
stack = []
for token in tokens:
if token in {'+', '-', '*', '/'}:
b, a = stack.pop(), stack.pop() # 注意顺序！
if token == '+': stack.append(a + b)
elif token == '-': stack.append(a - b)
elif token == '*': stack.append(a * b)
elif token == '/':
# 陷阱：Python 的 // 是向下取整，题目要求向零取整
# -7 // 2 = -4（Python），但题目要求 -3
stack.append(int(a / b)) # int() 向零取整
else:
stack.append(int(token))
return stack[0]
关键陷阱：
a和b的顺序：先 pop 出来的是b（右操作数）- 除法的截断方向：Python 的
//是向负无穷取整，但题目要求向零取整
4.2.4 基本计算器（LeetCode #224）
问题：实现一个基本计算器，支持 +、-、(、) 和空格。
输入: "(1+(4+5+2)-3)+(6+8)"
输出: 23
这比调度场算法简单，因为只有加减法（同优先级），但需要处理嵌套括号：
def calculate(s: str) -> int:
"""
基本计算器：支持 +、-、括号
核心思路：用栈保存括号外的状态（当前结果和符号）。
遇到 '(' 时把当前结果和符号 push 进栈，重新开始计算。
遇到 ')' 时把括号内的结果和栈中保存的状态合并。
时间复杂度：O(n)
空间复杂度：O(n)
"""
stack = []
result = 0 # 当前累积结果
sign = 1 # 当前符号：+1 或 -1
num = 0 # 当前正在构建的数字
for char in s:
if char.isdigit():
num = num * 10 + int(char)
elif char == '+':
result += sign * num
num = 0
sign = 1
elif char == '-':
result += sign * num
num = 0
sign = -1
elif char == '(':
# 保存当前状态，重新开始
stack.append(result)
stack.append(sign)
result = 0
sign = 1
elif char == ')':
# 把当前数字加入结果
result += sign * num
num = 0
# 从栈中恢复：先 pop 符号，再 pop 之前的结果
result = stack.pop() * result + stack.pop()
# 别忘了最后一个数字
result += sign * num
return result
# 测试
print(calculate("1 + 1")) # 2
print(calculate("2 - 1 + 2")) # 3
print(calculate("(1+(4+5+2)-3)+(6+8)")) # 23
print(calculate("-(2 + 3)")) # -5
4.3 栈 vs 递归：什么时候用显式栈
| 场景 | 推荐方式 | 理由 |
|---|---|---|
| 递归深度 < 100 | 递归 | 代码简洁，不会溢出 |
| 递归深度可能 > 1000 | 显式栈 | 避免 RecursionError |
| 树/图遍历（学习/面试） | 两种都要会 | 面试常考"递归和迭代两种写法" |
| 生产代码处理大数据 | 显式栈 | 稳定性和可预测性 |
| 需要暂停/恢复遍历 | 显式栈 | 递归不方便中断 |
| 尾递归（函数式风格） | 递归（如果语言支持 TCO） | Python 不支持，改用循环 |
实际案例：文件系统遍历
import os
# 递归版（可能在深层嵌套目录中溢出）
def find_files_recursive(directory, extension):
results = []
for entry in os.listdir(directory):
path = os.path.join(directory, entry)
if os.path.isfile(path) and path.endswith(extension):
results.append(path)
elif os.path.isdir(path):
results.extend(find_files_recursive(path, extension))
return results
# 显式栈版（安全，无深度限制）
def find_files_iterative(directory, extension):
results = []
stack = [directory]
while stack:
current_dir = stack.pop()
try:
for entry in os.listdir(current_dir):
path = os.path.join(current_dir, entry)
if os.path.isfile(path) and path.endswith(extension):
results.append(path)
elif os.path.isdir(path):
stack.append(path)
except PermissionError:
continue # 跳过无权限的目录
return results
4.4 常见陷阱与最佳实践
陷阱 1：空栈 pop
# 错误：没检查就 pop
def bad_code(stack):
return stack.pop() # 如果栈为空 → IndexError
# 正确：先检查
def good_code(stack):
if not stack:
return None # 或 raise 自定义异常
return stack.pop()
陷阱 2：peek 前不检查
# 错误
top = stack[-1] # 如果栈为空 → IndexError
# 正确
top = stack[-1] if stack else None
陷阱 3：操作数顺序
# 在后缀表达式求值中：
b = stack.pop() # 右操作数
a = stack.pop() # 左操作数
result = a - b # 不是 b - a！
# 记忆法：先进栈的是左操作数（更早出现）
陷阱 4：用 list 的前端作为栈顶
# 错误（性能灾难）：用 list 的头部作为栈顶
stack.insert(0, item) # O(n)！
stack.pop(0) # O(n)！
# 正确：始终用 list 的尾部作为栈顶
stack.append(item) # O(1) 均摊
stack.pop() # O(1) 均摊
陷阱 5：递归 + 全局状态
# 陷阱：递归中修改全局/共享状态
visited = set() # 全局
def dfs(node):
visited.add(node)
for neighbor in graph[node]:
if neighbor not in visited:
dfs(neighbor)
# 如果要多次调用 dfs，visited 不会自动清空！
# 改进：作为参数传入，或在每次调用前重置
4.5 综合练习：实现一个完整的表达式计算器
将本章所学整合，实现一个支持 +、-、*、/、括号、一元负号的计算器：
class Calculator:
"""
完整的数学表达式计算器
支持：
- 四则运算：+, -, *, /
- 括号：()
- 一元负号：-3, -(2+1)
- 多位数和小数：123, 3.14
实现方式：调度场算法（中缀→后缀）+ 后缀求值
"""
def __init__(self):
self.precedence = {'+': 1, '-': 1, '*': 2, '/': 2, 'NEG': 3}
self.right_assoc = {'NEG'}
def tokenize(self, expression: str) -> list:
"""词法分析：将字符串分解为 token 列表"""
tokens = []
i = 0
prev_token = None
while i < len(expression):
if expression[i].isspace():
i += 1
continue
if expression[i].isdigit() or expression[i] == '.':
# 读取数字（包括小数）
j = i
while j < len(expression) and (expression[j].isdigit() or expression[j] == '.'):
j += 1
tokens.append(('NUM', float(expression[i:j])))
prev_token = 'NUM'
i = j
elif expression[i] == '-' and (prev_token is None or prev_token in ('(', 'OP')):
# 一元负号
tokens.append(('OP', 'NEG'))
prev_token = 'OP'
i += 1
elif expression[i] in '+-*/':
tokens.append(('OP', expression[i]))
prev_token = 'OP'
i += 1
elif expression[i] == '(':
tokens.append(('LPAREN', '('))
prev_token = '('
i += 1
elif expression[i] == ')':
tokens.append(('RPAREN', ')'))
prev_token = 'NUM' # ) 后面的 - 是二元的
i += 1
else:
raise ValueError(f"Unexpected character: {expression[i]}")
return tokens
def to_postfix(self, tokens: list) -> list:
"""调度场算法：token 列表 → 后缀表达式"""
output = []
op_stack = []
for token_type, token_value in tokens:
if token_type == 'NUM':
output.append(token_value)
elif token_type == 'LPAREN':
op_stack.append('(')
elif token_type == 'RPAREN':
while op_stack[-1] != '(':
output.append(op_stack.pop())
op_stack.pop()
elif token_type == 'OP':
while (op_stack and op_stack[-1] != '(' and
op_stack[-1] in self.precedence and
(self.precedence[op_stack[-1]] > self.precedence[token_value] or
(self.precedence[op_stack[-1]] == self.precedence[token_value] and
token_value not in self.right_assoc))):
output.append(op_stack.pop())
op_stack.append(token_value)
while op_stack:
output.append(op_stack.pop())
return output
def evaluate_postfix(self, postfix: list) -> float:
"""后缀表达式求值"""
stack = []
for token in postfix:
if isinstance(token, float):
stack.append(token)
elif token == 'NEG':
stack.append(-stack.pop())
else:
b = stack.pop()
a = stack.pop()
if token == '+': stack.append(a + b)
elif token == '-': stack.append(a - b)
elif token == '*': stack.append(a * b)
elif token == '/': stack.append(a / b)
return stack[0]
def calculate(self, expression: str) -> float:
"""计算表达式的值"""
tokens = self.tokenize(expression)
postfix = self.to_postfix(tokens)
return self.evaluate_postfix(postfix)
# 测试
calc = Calculator()
print(calc.calculate("3 + 4 * 2")) # 11.0
print(calc.calculate("(1 + 2) * (3 + 4)")) # 21.0
print(calc.calculate("-3 + 4")) # 1.0
print(calc.calculate("-(2 + 3) * 4")) # -20.0
print(calc.calculate("10 / 3")) # 3.333...
本章小结
栈是计算机科学中最基础的数据结构之一。它的 LIFO 特性使得它天然适合处理"嵌套"和"配对"的问题。
核心要点：
| 知识点 | 关键理解 |
|---|---|
| 栈的本质 | 受限的线性结构，只允许操作栈顶 |
| 调用栈 | 每个函数调用 = push 一个帧，返回 = pop |
| 括号匹配 | 最后打开的最先关闭 = LIFO |
| 表达式求值 | 中缀 → 后缀 → 栈求值 |
| 最小栈 | 辅助栈同步记录每个状态的最小值 |
| DFS | 递归本质就是栈 |
| 递归消除 | 用显式栈模拟调用栈 |
| 单调栈 | "下一个更大/更小元素"的通用解法 |
下一章预告：第 6 章我们将学习队列——栈的"对偶"数据结构。从 BFS 到滑动窗口，从优先队列到单调队列，队列的应用同样精彩。