第 32 章 栈¶
配套例题：BISHI2 【模板】栈的操作（题解已通过官方样例）、BISHI117 小苯的 IDE 括号问题（easy） 来源：S3 day1《栈 队列》 前置：30-序列与数组
栈是后进先出（LIFO）的容器。S3 day1 的比喻很到位：
栈中的元素先入后出，就像摆在桌面上的一堆书，先堆上去的书垫在底下。 从顶上一本一本取出来时，最先放上去的书最后取出来。
好消息是：Python 的 list 天然就是一个完美的栈，不需要任何封装。
这一章的重点因此不在「怎么实现栈」，而在「怎么认出一道题是栈题」。
32.1 list 就是栈¶
| 栈操作 | C++ std::stack |
Python list |
复杂度 |
|---|---|---|---|
| 入栈 | stk.push(x) |
st.append(x) |
\(O(1)\) 均摊 |
| 出栈 | stk.pop() |
st.pop() |
\(O(1)\) |
| 取栈顶 | stk.top() |
st[-1] |
\(O(1)\) |
| 判空 | stk.empty() |
not st |
\(O(1)\) |
| 大小 | stk.size() |
len(st) |
\(O(1)\) |
S3 day1 给的伪代码是数组 + top 指针：
int top = 0
int stk[n]
function push(int x): stk[top++] = x
function get_top(): return stk[top - 1]
function pop(): return stk[--top]
Python 的 list.append / list.pop 内部做的正是这件事（ob_size 就是 top），
所以不要自己维护 top 指针——那只会更慢，因为多了 Python 层的算术。
注意
pop()的两个语义差异： - C++ 的stk.pop()不返回值，取值要先top()； - Python 的st.pop()返回被弹出的值。写题时若只是想丢弃栈顶，直接
st.pop()即可，不要写_ = st.pop()。
空栈保护¶
if st: # ✅ 唯一正确的判空写法
x = st.pop() # 进了这个分支才 pop，栈一定非空
x = st.pop() # ❌ 空栈时抛 IndexError: pop from empty list
top = st[-1] # ❌ 空栈时抛 IndexError: list index out of range
竞赛里绝大多数栈题的 WA 都来自忘了判空，尤其是「弹到栈空为止」的循环：
32.2 栈的四大用途¶
| 用途 | 典型题 | 讲解位置 |
|---|---|---|
| 括号 / 配对匹配 | 括号序列合法性、HTML 标签匹配 | 本章 32.3 |
| 表达式求值 | 中缀转后缀、逆波兰求值 | 本章 32.4 |
| 单调栈 | 左右第一个更大/更小元素 | 37-单调栈与单调队列 |
| 递归 / DFS | 手动模拟调用栈避免爆栈 | 60-DFS深度优先搜索 |
S3 day1 特别指出第四点：
回溯、函数递归和深度优先搜索（DFS）都需要使用栈，只不过系统提供了函数调用栈。 递归调用函数时，当前的函数所处的状态被压栈，直到其执行完毕才弹栈恢复。
在 C++ 里可以 ulimit -s 524288 把系统栈开到 512MB；
在 Python 里你没有这个选项（sys.setrecursionlimit 只改计数器），
所以深度超过约 \(10^4\) 的递归必须手动改写成显式栈。
这就是「栈」这个数据结构在 Python 竞赛里比在 C++ 里更重要的原因。
32.3 括号匹配¶
模板一：单一括号，只判合法¶
def is_balanced(s):
"""只有一种括号时，栈退化成一个计数器。O(n)。"""
d = 0 # d 是尚未闭合的左括号数，等价于「栈的当前高度」
for c in s:
if c == "(":
d += 1 # 左括号入栈
else:
d -= 1 # 右括号配掉一个左括号
if d < 0: # 高度变负说明这个右括号无左括号可配，后面补也无用
return False
return d == 0 # 扫完必须恰好清零，剩下没闭合的左括号同样不合法
优化意识：只有一种括号时不需要栈，一个整数就够。 这个「深度」变量还能顺带回答很多问题：最大嵌套深度就是 \(\max d\)， 每个位置的括号深度就是当时的 \(d\)。
模板二：多种括号¶
PAIR = {")": "(", "]": "[", "}": "{"} # 由右括号反查它该配的左括号
def is_balanced_multi(s):
st = [] # 栈里存尚未闭合的左括号
for c in s:
if c in "([{": # 三种左括号一律入栈
st.append(c)
elif c in PAIR: # 只有右括号触发匹配，其余字符直接跳过
# 栈空说明没有左括号可配；类型对不上说明嵌套交叉。
# 两个条件的顺序不能反，否则空栈时 pop 会抛 IndexError
if not st or st.pop() != PAIR[c]:
return False
return not st # 收尾时栈必须空，否则有左括号一直没闭合
模板三：求最长合法括号子串¶
栈里存下标而不是字符，这是括号题的通用升级技巧：
def longest_valid(s):
"""最长合法括号子串长度，O(n)。栈底放一个「上一个不合法位置」的哨兵。"""
st = [-1] # 哨兵取 -1，使从下标 0 起的合法段算出 i - (-1) = i + 1
best = 0 # 一个合法段都没有时答案就是 0
for i, c in enumerate(s):
if c == "(":
st.append(i) # 存下标而不是字符，弹栈时才能直接算长度
else:
st.pop() # 右括号先无条件弹一个：弹掉的要么是配对的左括号，要么是哨兵
if st: # 还有元素说明刚才配对成功，新栈顶是当前合法段左边界的前一位
if i - st[-1] > best: # 栈顶在边界外一格，两下标相减就是段长，不用再 +1
best = i - st[-1]
else:
st.append(i) # 这个 ')' 无法匹配，成为新的哨兵
return best
括号题通法：栈里存下标 → 弹栈时用
i - st[-1]直接算出区间长度。 这个套路和单调栈算矩形面积是同一个（37 章）。
32.4 表达式求值¶
S3 day1 讲得很完整，这里给 Python 实现。
后缀表达式（逆波兰）求值¶
8 - (3 + 2 * 6) / 5 + 4的后缀形式是8 3 2 6 * + 5 / - 4 +。 从左到右扫：数字入栈，运算符从栈顶取两个数运算后把结果压回。
课件里的执行过程：
stack: 8 3 2 6，读入 *，计算 2 * 6 = 12
stack: 8 3 12，读入 +，计算 3 + 12 = 15
stack: 8 15 5，读入 /，计算 15 / 5 = 3
stack: 8 3，读入 -，计算 8 - 3 = 5
stack: 5 4，读入 +，计算 5 + 4 = 9
def eval_rpn(tokens):
"""求值后缀表达式，tokens 是字符串列表。O(n)。"""
st = [] # 栈里只放已经算出的中间结果
for t in tokens:
if t == "+":
# 先弹出的是右操作数，后弹出的才是左操作数，减法除法靠这个顺序
b = st.pop(); a = st.pop(); st.append(a + b)
elif t == "-":
b = st.pop(); a = st.pop(); st.append(a - b)
elif t == "*":
b = st.pop(); a = st.pop(); st.append(a * b)
elif t == "/":
b = st.pop(); a = st.pop()
# 竞赛中「整数除法」通常指向零取整，Python 的 // 是向下取整，要区分
st.append(int(a / b) if a * b < 0 else a // b)
elif t == "^":
b = st.pop(); a = st.pop(); st.append(a ** b)
else:
st.append(int(t)) # 不是运算符就是数字，转成 int 压栈
return st[-1] # 合法后缀式扫完后栈里恰剩一个数，就是答案
陷阱：
b = st.pop(); a = st.pop()的顺序不能反—— 后弹出的是左操作数。-和/不满足交换律，写反了样例都过不了。陷阱：负数整除。
-7 // 2 == -4（向下），而 C++ 的-7 / 2 == -3（向零）。 题目说「整数除法」时要看清是哪一种，详见 03-运算符与位运算。
中缀转后缀（调度场算法）¶
S3 day1 给出的规则：
- 遇到数字直接输出；
- 遇到运算符和左括号压入符号栈；
- 遇到右括号则一直弹栈输出直到遇到左括号；
- 压入运算符时，如果栈顶符号不为括号且优先级不小于当前运算符，则弹出栈顶运算符并输出， 直到栈空 / 遇到左括号 / 遇到优先级更低的运算符，然后压入当前运算符；
- 读入结束后弹出栈内所有运算符。
PRI = {"+": 1, "-": 1, "*": 2, "/": 2, "^": 3} # 数值越大越先算
RIGHT_ASSOC = {"^"} # 右结合运算符
def to_rpn(tokens):
"""中缀 -> 后缀（调度场算法）。O(n)。"""
out = [] # 输出队列，最终的后缀式
ops = [] # 符号栈，只放运算符和左括号
for t in tokens:
if t == "(": # 左括号无条件入栈，它是后续弹栈的下界
ops.append(t)
elif t == ")": # 遇右括号：一路弹到左括号为止
while ops and ops[-1] != "(":
out.append(ops.pop())
ops.pop() # 弹掉左括号，括号本身不进输出
elif t in PRI:
# 栈顶优先级更高就必须先算；优先级相同时左结合要弹（从左往右算），
# 右结合不弹（从右往左算），差别全在 t not in RIGHT_ASSOC 这一句
while (ops and ops[-1] != "("
and (PRI[ops[-1]] > PRI[t]
or (PRI[ops[-1]] == PRI[t] and t not in RIGHT_ASSOC))):
out.append(ops.pop())
ops.append(t) # 该弹的都弹完了，当前运算符才入栈
else:
out.append(t) # 数字直接进输出，不入符号栈
while ops: # 读完后栈内残余运算符依次输出，栈顶的先算
out.append(ops.pop())
return out
课件的练习：(8 + (7 - 6) + 5) + 4 * 3 / 2 * (1 + 9)
\(\to\) 8 7 6 - + 5 + 4 3 * 2 / 1 9 + * +。可以拿这组数据自测。
右结合的处理：
^是右结合的（\(2^{3^2} = 2^9\)）， 所以遇到同优先级时不弹栈。+ - * /是左结合，同优先级要弹。 这一行t not in RIGHT_ASSOC就是全部区别。
Python 特供：能不能直接 eval？¶
可以，但有三个致命限制：
| 问题 | 说明 |
|---|---|
| 除法语义 | Python 的 / 是真除法返回 float，题目多半要整除 |
| 幂运算符 | 题目里的 ^ 在 Python 里是异或，含义完全不同 |
| 大表达式 | eval 要走完整的编译流程，\(10^5\) 次调用会很慢 |
所以模板题老老实实写栈；只有在「表达式很短、语义恰好和 Python 一致」时，
eval 才是一个能省 30 行代码的应急手段。
32.5 对顶栈：用两个栈模拟光标¶
这是笔试高频模型：一个可以左右移动的光标，在光标处做插入/删除。
思路：用两个栈 left 和 right 背靠背，光标就在两个栈顶之间。
| 操作 | 实现 | 复杂度 |
|---|---|---|
| 光标左移 | right.append(left.pop()) |
\(O(1)\) |
| 光标右移 | left.append(right.pop()) |
\(O(1)\) |
| 在光标处插入 | left.append(c) |
\(O(1)\) |
| 删除光标左边一个 | left.pop() |
\(O(1)\) |
| 删除光标右边一个 | right.pop() |
\(O(1)\) |
| 还原完整串 | left + right[::-1] |
\(O(n)\) |
这就是 S3 day1 的选做题 #2「仅用两个栈实现一个双端队列」的思路。 对比：用
list存整串 + 一个下标当光标，每次删除是 \(O(n)\)，\(k\) 次操作就是 \(O(nk)\)。
32.6 例题¶
BISHI2 【模板】栈的操作（简单）¶
\(n \le 10^5\) 次操作：
push x入栈；pop若非空则删栈顶，否则输出Empty；query若非空则输出栈顶，否则输出Empty；size输出元素数量。 题面见 BISHI2 原题（牛客）。
算法上零难度，考的是读题精度和 IO 速度。
三个坑：
pop成功时不输出任何东西，只有空栈才输出Empty。这一条最容易写反；query空栈也输出Empty，但和pop的语义不同（一个删一个不删）；size永远有输出，空栈时输出0。
外加一个格式坑：只有 push 后面跟参数，pop/query/size 是单 token，
所以必须用游标按 token 读，不能按「每行两个数」读。
import sys
def main():
# push 带参数、pop/query/size 不带，行长不固定，只能整读后按 token 消费
data = sys.stdin.buffer.read().split()
n = int(data[0]) # 操作条数
i = 1 # token 游标，data[0] 已被 n 取走
st = [] # list 本身就是栈，进出都在尾部
out = [] # 输出先攒着，结尾一次写出
for _ in range(n):
op = data[i] # 操作码保持 bytes，直接与 b"..." 比较，省一次解码
i += 1 # 操作码消费掉，游标停在它的参数位上
if op == b"push":
st.append(data[i]) # 直接存原始 bytes，省掉 int/str 往返
i += 1 # push 的那个参数也消费掉
elif op == b"pop":
if st: # 判空必须在 pop 之前，空栈 pop 会抛 IndexError
st.pop() # 成功时不输出
else:
out.append("Empty") # 只有空栈时才有输出，这一条最容易写反
elif op == b"query":
out.append(st[-1].decode() if st else "Empty") # query 只看栈顶不弹栈，输出前才转 str
else: # size
out.append(str(len(st))) # size 永远有输出，空栈时是 0
sys.stdout.write("\n".join(out) + "\n") # 一次写出，逐行 print 会被 IO 拖垮
main()
「存 bytes 不转 int」是这类模板题的通用加速手段：
既然入栈的值最后原样输出，就没必要 int(data[i]) 再 str(x) 转回来，
省掉 \(2 \times 10^5\) 次转换。只有需要参与运算时才转。
题解见 solutions/BISHI2.py。
BISHI117 小苯的 IDE 括号问题（easy）（中等）¶
长度 \(n \le 2\times10^5\) 的串仅含
(、)、I，其中I恰好出现一次表示光标。 \(k \le n\) 次操作： - backspace：若光标左边是(且右边紧跟)，一次性删掉这对括号； 否则若左边还有字符就只删左边一个；左边为空则无效； - delete：若右边存在字符则删掉右边第一个，否则无效。输出全部操作后的最终串（含光标
I）。 题面见 BISHI117 原题（牛客）。
标准的对顶栈题。把 I 左边的部分作为左栈（栈顶 = 紧贴光标的字符），
右边的部分逆序存进右栈（栈顶 = 紧贴光标的字符），
于是三条规则全部变成 \(O(1)\) 的栈顶操作：
import sys
def main():
data = sys.stdin.buffer.read().split() # token 顺序：n、k、串、k 条操作
s = data[2].decode() # 串排第三个 token，下标 2
i = s.index("I") # 光标位置；题目保证 I 恰好出现一次
left = list(s[:i]) # 切片右端不含 i，正好取到光标左边全部；栈顶 left[-1] 紧贴光标
right = list(s[i + 1:])[::-1] # i+1 跳过 I 本身；反转后原来的第一个字符落到栈顶
k = int(data[1]) # 操作条数
for j in range(k):
op = data[3 + j] # 前 3 个 token 是 n、k、串，操作从下标 3 起
if op == b"backspace":
if left and right and left[-1] == "(" and right[-1] == ")": # 先判空再取 [-1]，短路保证不越界
left.pop() # 成对删除
right.pop()
elif left:
left.pop() # 不成对时退化成删左边一个字符
# 左边为空则什么都不做
else: # delete
if right: # 右边没字符时 delete 无效，什么都不做
right.pop()
right.reverse() # 右栈是逆序存的，输出前转回正序
sys.stdout.write("".join(left) + "I" + "".join(right) + "\n") # 光标 I 要原样留在两段之间
main()
复杂度 \(O(n + k)\)。
手动验证样例 1：n=10, k=3，s = ((()(I))((，光标在下标 5。
left = "((()("，right 栈从顶到底是 ) ) ( (。
| 操作 | 判断 | left | right（顶→底） |
|---|---|---|---|
| 初始 | ((()( |
))(( |
|
| backspace | 左 (、右 ) → 成对删 |
((() |
)(( |
| backspace | 左是 ) → 只删左一个 |
((( |
)(( |
| delete | 删右一个 | ((( |
(( |
输出 ((( + I + (( = (((I(( ✓
关键陷阱：
- 成对删除的判定是「左边是
(并且 右边是)」，两个条件缺一不可， 而且要先判空（left and right），否则空栈取[-1]会IndexError； - 右栈是逆序存的，最后输出前要
reverse()回来； - 输出必须保留
I——题目要的是最终的「括号串」，光标仍在里面。
为什么不能用字符串下标模拟？ 每次删除都要
s = s[:p] + s[p+1:]，是 \(O(n)\)，\(k\) 次就是 \(4\times10^{10}\)。 对顶栈把它降到 \(O(1)\)。这就是栈在这题的全部价值。
题解：solutions/BISHI117.py（已通过牛客判题机验证）
32.7 本章速查¶
| 要点 | 结论 |
|---|---|
| Python 的栈 | 直接用 list：append / pop / [-1] |
| 不要做的事 | 自己维护 top 指针（更慢） |
| 判空 | if st: / while st and ...（短路保证不越界） |
pop() 差异 |
Python 的 pop() 返回值，C++ 的不返回 |
| 单一括号匹配 | 不需要栈，一个计数器 d 就够 |
| 括号题通法 | 栈里存下标，弹栈时 i - st[-1] 得区间长 |
| 后缀求值 | b = pop(); a = pop()，顺序不能反 |
| 中缀转后缀 | 同优先级：左结合弹栈，右结合（^）不弹 |
eval |
除法语义、^ 含义、性能三个坑，模板题别用 |
| 光标类问题 | 对顶栈，\(O(1)\) 完成全部操作 |
| Python 递归 | 没有 ulimit -s，深度大就必须显式栈 |
| 看到什么 → 想到栈 |
|---|
| 括号 / 配对 / 嵌套 |
| 「上一个还没被处理的」「最近的一个」 |
| 表达式、运算优先级 |
| 「左边第一个比它大的」→ 单调栈（37 章） |
| 光标、撤销、回溯 |
| 递归深度太大要手动展开 |