栈(Stack)

栈提供后进先出的访问顺序。Python 中 list 的 append 与尾部 pop 可以实现栈;显式栈还能把某些递归遍历改成循环。

一句话定义

栈提供后进先出的访问顺序。Python 中 list 的 append 与尾部 pop 可以实现栈;显式栈还能把某些递归遍历改成循环。

为什么重要

  • 函数调用就是栈:每次调用压入一个栈帧,返回时弹出;错误时看到的回溯(traceback)就是调用栈(见 k1.prog.stack-trace)。
  • 括号匹配、表达式求值、撤销(Undo)、浏览器后退、深度优先搜索(见 k2.algo.dfs)都靠栈。

使用边界

Python 调用帧与系统 C 栈不应直接等同。递归上限和可承受深度取决于解释器与执行环境;提高上限还可能增加内存或触发底层扩展的限制。

原理 / 图解

图 1

Python 中用 list 的 append / pop() 即可,二者都是摊还 O(1)O(1)。官方教程“将列表作为栈使用”:https://docs.python.org/3/tutorial/datastructures.html#using-lists-as-stacks

可运行示例

括号匹配、逆波兰表达式(RPN)求值、递归深度上限、用显式栈把递归改成循环(Python 3.15.0 一稿运行记录):

# 文件:examples/10_stack.py
# 栈:后进先出 LIFO。Python 用 list 的 append/pop 即可
def balanced(s: str) -> bool:
    pairs, stack = {")": "(", "]": "[", "}": "{"}, []
    for ch in s:
        if ch in "([{": stack.append(ch)
        elif ch in pairs:
            if not stack or stack.pop() != pairs[ch]: return False
    return not stack
for s in ["{[()]}", "([)]", '{"a": [1, 2]}', "(("]:
    print(f"{s!r:16} 括号匹配: {balanced(s)}")

# 逆波兰表达式求值(计算器、编译器的经典用法)
def rpn(tokens):
    st = []
    for t in tokens:
        if t in "+-*/":
            b, a = st.pop(), st.pop()
            st.append({"+": a + b, "-": a - b, "*": a * b, "/": a / b}[t])
        else: st.append(float(t))
    return st[0]
print("(3 + 4) * 2 的逆波兰 3 4 + 2 * =", rpn("3 4 + 2 *".split()))

# 函数调用栈本身就是栈:递归太深会溢出
import sys
def depth(n): return 0 if n == 0 else 1 + depth(n - 1)
print("默认递归上限:", sys.getrecursionlimit())
try: depth(100_000)
except RecursionError as e: print("RecursionError:", e)

# 用显式栈把递归改成循环(DFS 常用)
def depth_iter(n):
    stack, d = [n], 0
    while stack:
        x = stack.pop()
        if x: d += 1; stack.append(x - 1)
    return d
print("显式栈处理 100000 层:", depth_iter(100_000))

一稿留存输出:

'{[()]}'         括号匹配: True
'([)]'           括号匹配: False
'{"a": [1, 2]}'  括号匹配: True
'(('             括号匹配: False
(3 + 4) * 2 的逆波兰 3 4 + 2 * = 14.0
默认递归上限: 1000
RecursionError: maximum recursion depth exceeded
显式栈处理 100000 层: 100000

一稿示例在默认递归限制附近触发 RecursionError,具体可用深度受调用上下文影响(默认递归上限约为 1000),改用显式栈后处理 10 万层也没问题。sys.getrecursionlimit:https://docs.python.org/3/library/sys.html#sys.getrecursionlimit

常见误区

  • pop(0) 当栈用:那是从底部取,变成队列且是 O(n)O(n)。
  • 空栈 pop:会抛 IndexError,要先判空。
  • 随意调大 sys.setrecursionlimit:可能导致解释器真正的 C 栈溢出而崩溃;深递归应改迭代。
  • 混淆“栈”数据结构和“栈内存”:前者是抽象结构,后者是程序运行时的内存区域,二者相关但不是一回事。

与 AI 开发的关系

  • 解析模型输出:检查 LLM 生成的 JSON/代码括号是否配对、提取嵌套结构,常用栈。
  • Agent 任务分解:子任务的“进入/返回”天然是栈式结构。

延伸阅读

理解检查

把递归改成显式栈后,空间复杂度会自动变成 O(1) 吗?

参考答案:不会。显式栈仍要保存未完成的状态,只是避免 Python 递归调用深度限制。

核验与复现

核验日期:2026-10-14。示例状态:运行通过。本轮日志:10_stack.py。

配套代码与核验资料

继续浏览基础 返回知识 →返回顶部 ↑
本篇目录
教程图解100%
教程图解