3.1 栈：后进先出
前置：数组与链表的选择。这一节先钉牢 LIFO 契约，再比较数组栈与链表栈，最后把同一条规则用到括号匹配和深度优先搜索。
LIFO 只从一端进出
依次把 key、brick、book 压入同一个容器，再连续弹出三次，观察顺序会变成 book、brick、key。这条接口规定：
后放入的元素先取出，先放入的元素后取出。
这种规则叫后进先出，英文是 Last In, First Out，缩写 LIFO。遵守 LIFO 的抽象数据类型就是栈。我们只关心“顶部”这一端，不要求底层一定使用数组或链表。
先记住操作契约
| 操作 | 含义 | 空栈时的约定 | 抽象模型中的目标成本 |
|---|---|---|---|
push(x) | 把 x 放到栈顶 | 总能插入，除非资源耗尽 | Θ(1) |
pop() | 移除并返回栈顶 | 抛出异常或返回失败状态 | Θ(1) |
peek() | 查看栈顶，不移除 | 抛出异常或返回失败状态 | Θ(1) |
is_empty() | 判断是否为空 | 返回 True | Θ(1) |
len(stack) | 返回元素数 | 返回 0 | Θ(1) |
对空栈执行 pop 或 peek 叫下溢（underflow）。库之间的失败方式不同：有的抛异常，有的返回空值或布尔状态。写接口时要选定一种契约，调用方也必须按同一契约处理。
同一座栈，两种存法
第一种把栈顶放在动态数组的右端。CPython list 的末尾追加和弹出均摊 Θ(1)。一次追加可能扩容；一次弹出也可能触发缩容。末尾弹出虽然不移动后缀，仍不能把每次实际分配或复制都当成常数成本。可在 CPython 3.14 源码的 list_pop_impl 和 list_resize 中核对这条路径。
第二种复用上一章的单链表：头节点就是栈顶。push 新建一个节点并接到头部，pop 让头指针越过旧节点。在链表抽象模型里，两项操作都是 Θ(1)；实际运行还要承担每次分配节点和保存链接的开销。
下面的程序用两种实现处理同一批物品，并检查结果一致：
class ArrayStack:
def __init__(self):
self._data = []
def push(self, item):
self._data.append(item)
def pop(self):
if self.is_empty():
raise IndexError("pop from empty stack")
return self._data.pop()
def peek(self):
if self.is_empty():
raise IndexError("peek from empty stack")
return self._data[-1]
def is_empty(self):
return len(self._data) == 0
def to_list(self):
return self._data.copy()
def __len__(self):
return len(self._data)
class Node:
def __init__(self, value, next_node=None):
self.value = value
self.next = next_node
class LinkedStack:
def __init__(self):
self._head = None
self._size = 0
def push(self, item):
self._head = Node(item, self._head)
self._size += 1
def pop(self):
if self.is_empty():
raise IndexError("pop from empty stack")
value = self._head.value
self._head = self._head.next
self._size -= 1
return value
def peek(self):
if self.is_empty():
raise IndexError("peek from empty stack")
return self._head.value
def is_empty(self):
return self._head is None
def to_list(self):
values = []
current = self._head
while current is not None:
values.append(current.value)
current = current.next
return list(reversed(values))
def __len__(self):
return self._size
def is_valid_brackets(text):
matching = {")": "(", "]": "[", "}": "{"}
stack = []
for char in text:
if char in matching.values():
stack.append(char)
elif char in matching:
if not stack or stack.pop() != matching[char]:
return False
return not stack
if __name__ == "__main__":
array_stack = ArrayStack()
linked_stack = LinkedStack()
for item in ["alpha", "beta", "gamma"]:
array_stack.push(item)
linked_stack.push(item)
print(f"栈顶：{array_stack.peek()}")
print(f"弹出：{array_stack.pop()}")
linked_stack.pop()
print(f"剩余：{array_stack.to_list()}")
print(
"括号匹配："
f"{is_valid_brackets('map[{key}]')} "
f"{is_valid_brackets('map[(])')}"
)
assert array_stack.to_list() == linked_stack.to_list()
assert len(array_stack) == len(linked_stack) == 2
print("栈检查通过")栈顶：gamma
弹出：gamma
剩余：['alpha', 'beta']
括号匹配：True False
栈检查通过逐步读数组栈
_data[-1]是栈顶。栈的使用者不应该绕过接口修改_data。push把元素加到右端；pop从右端移除。peek只读栈顶，所以不会改变长度。pop和peek先检查空栈，避免把底层容器的偶然错误当成公开契约。to_list返回副本，示例才能查看状态而不泄露内部列表。
逐步读链表栈
假设头部依次是 gamma -> beta -> alpha：
push("delta")创建新节点，让它指向旧头部，再把_head改为新节点。pop()保存旧头部的值，让_head指向第二个节点。- 两个操作都没有沿链表遍历。
两种 to_list 都是演示用的浅拷贝，需要 Θ(n) 时间和输出空间；链表版本还要遍历节点。复制不会隔离元素内部的修改，不能把这项操作的成本算到每次 push 或 pop 上。
括号匹配：保存最近的未完成工作
扫描 map[{key}] 时，左括号代表尚未完成的嵌套结构，先把它压栈。右括号必须匹配最近一个尚未闭合的左括号；隔着内层去找外层，括号就会交叉。
以 [(]) 为例：
| 读到的字符 | 栈（底 → 顶） | 处理 |
|---|---|---|
[ | [ | 左括号入栈 |
( | [ ( | 左括号入栈 |
] | [ ( | 栈顶是 (，与 ] 不匹配，失败 |
这个算法有三种失败路径：
- 右括号出现时栈已经空，说明缺少左括号；
- 栈不空，但栈顶括号类型不匹配，例如上面的
[(])； - 扫描结束后栈仍有元素，说明缺少右括号。
示例函数忽略非括号字符，这是它明确选择的输入契约。真实语言的词法和语法规则更复杂；解析器常用显式栈、递归调用形成的隐式栈，或两者结合来处理嵌套结构。这里的程序只验证三类括号的配对和嵌套次序，不识别字符串和注释里的括号。对长度 n 的输入，最坏时间 Θ(n)，辅助空间 Θ(n)，例如全部字符都是左括号时。
显式栈与调用栈
递归函数把“稍后还要继续做什么”交给调用栈保存。迭代版本则可以把同样的状态放进显式容器。两者都消耗空间，差别在于状态由运行时管理还是由程序管理。
def depth_first_order(graph, start):
order = []
seen = set()
stack = [start]
while stack:
node = stack.pop()
if node in seen:
continue
seen.add(node)
order.append(node)
stack.extend(reversed(graph[node]))
return order
graph = {"A": ["B", "C"], "B": ["D"], "C": [], "D": []}
assert depth_first_order(graph, "A") == ["A", "B", "D", "C"]这里要求每个可达顶点都在 graph 中有邻接列表，reversed 让列表左边的邻居先弹出。节点在弹出时才标记，因此同一节点可能重复入栈，但只展开一次。令 V、E 为可达部分的顶点数和邻接项数，在哈希操作为常数的模型下，时间 Θ(V+E)，这个写法的显式栈最坏可存 O(V+E) 项；不能直接照抄递归 DFS 的 O(V) 栈空间。
空操作也可以采用返回状态的接口，而不是抛异常。关键是别让调用方猜：
def try_pop(stack):
if not stack:
return False, None
return True, stack.pop()
assert try_pop([]) == (False, None)
assert try_pop([None]) == (True, None)
assert try_pop(["钥匙"]) == (True, "钥匙")Python 的递归上限不是固定的“约 1000”。当前解释器的值可通过 sys.getrecursionlimit() 读取，也可在允许范围内调整。提高上限并不会消除 C 栈或进程内存限制。处理可能很深的树和图时，显式栈通常让失败条件与内存使用更容易控制。
调用栈由语言运行时、ABI、编译器生成的调用约定，以及机器提供的寄存器和指令共同实现。本章只借用 LIFO 关系，不展开这些系统细节。
常见语言的栈接口
| 语言 | 建议容器 | 压入 / 弹出 / 查看 | 需要留意 |
|---|---|---|---|
| Python | list | append(x) / pop() / stack[-1] | 末尾追加/弹出均摊 O(1)；空弹出或读取抛 IndexError |
| Java 17 | Deque<E> + ArrayDeque<E> | push / pop / peek | Stack 是旧 API，并未标注 @Deprecated；ArrayDeque 禁止 null，非线程安全；空 pop 抛异常，空 peek 返回 null |
| C++ | std::stack<T> | push / pop / top | 默认适配 std::deque；先确认非空，再读 top 并 pop；pop 不返回元素 |
参考契约：
常见错误怎么定位
| 症状 | 先检查什么 |
|---|---|
| 弹出顺序像 FIFO | push 与 pop 是否在同一端 |
| 空栈崩溃位置难懂 | 公开方法是否先执行空检查 |
| 括号交错仍返回真 | 右括号是否与“栈顶”比较，而不是与任意左括号比较 |
| 扫描结束仍误判为真 | 返回前是否检查栈已经清空 |
| 链表栈长度错误 | 每次 push 和成功的 pop 是否各更新一次 _size |
动手验证 LIFO 与下溢
- 依次压入
A、B、C，两次pop会得到什么？栈里还剩什么？ - 给
peek写一个空栈测试。它应该抛出哪种异常？ - 手算
{a[(b+c)]}和{a[(b+c])}的栈状态。 - 给链表栈增加
clear。更新入口和计数只需常数次赋值，为什么回收 n 个旧节点仍可能需要 Θ(n) 工作？ - 进阶：用两个栈实现一个队列。每个元素为什么只会在两个栈之间转移一次？
把栈的边界说清楚
push 与 pop 在同一端操作，peek 不改变长度，空栈按约定失败。用同一组输入验证数组栈和链表栈，再说明扩缩容和 to_list 各自花在哪里。括号匹配还要检查类型错配和扫描结束时的剩余内容。
下一节进入队列，看“先到先走”如何改变容器两端的分工。