算法刷题系列（九）：栈——后进先出的状态管理

算法刷题系列（九）：栈——后进先出的状态管理

在前面的表达式计算篇中，括号和递归调用都体现了一个共同特点：最近开始、尚未完成的工作，要先于更早的工作结束。栈正是用来管理这种“后进先出”关系的数据结构。

本篇从栈的操作和不变量开始，用原创的括号匹配例子说明何时压入、何时弹出，并分别用 Java 和 Python 实现。后面讲括号问题和单调栈时，还会在这个基础上扩展。

一、栈是什么？

栈（Stack）只允许从一端访问元素，这一端称为栈顶。常见操作包括：

• push(x)：把 x 放到栈顶；
• pop()：移除并返回栈顶元素；
• peek() / top()：查看栈顶但不移除；
• isEmpty()：判断栈是否为空。

栈遵循 LIFO（Last In, First Out，后进先出）。想象一叠盘子：最后放上去的盘子，最先被拿走。

对常见数组式或链表式栈实现，压入和弹出通常是摊还 O(1) 时间；具体实现还会影响扩容成本和内存布局。

二、栈的不变量

理解栈题时，不要只记住“用一个容器”。要说清楚栈里保存的是什么，以及它为什么只需要看栈顶。

例如，扫描括号字符串时：

• 遇到左括号，将它压入栈；
• 遇到右括号，它必须和最近一个尚未匹配的左括号配对；
• 因为“最近打开的括号最先关闭”，只需检查栈顶。

扫描到任意位置时，栈中保存的就是“已经出现、但还没有匹配右括号的左括号”，顺序从栈底到栈顶与它们在字符串中的出现顺序一致。

三、原创例子：检查括号是否匹配

只考虑三种括号：(), [], {}。字符串合法需要同时满足：

1. 每个右括号都有一个相同类型、尚未匹配的左括号；
2. 括号关闭顺序与打开顺序相反；
3. 扫描结束时没有未匹配的左括号。

逐字符处理：

• 左括号：压入；
• 右括号：若栈为空则失败；否则弹出栈顶并检查类型；
• 扫描结束：栈必须为空。

例如 "{[()]}" 的处理过程如下：

字符	动作	栈（底 → 顶）
{	压入	{
[	压入	{ [
(	压入	{ [ (
)	匹配并弹出	{ [
]	匹配并弹出	{
}	匹配并弹出	空

若输入是 "([)]"，读到 ) 时栈顶是 [，类型不匹配，必须立即判定失败。不能只统计左、右括号数量，因为数量相同不代表嵌套顺序正确。

四、Java 实现

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Map;

public class BracketMatcher {
    private static final Map<Character, Character> OPEN_TO_CLOSE = Map.of(
        '(', ')',
        '[', ']',
        '{', '}'
    );

    public static boolean isValid(String text) {
        if (text == null) {
            throw new IllegalArgumentException("text must not be null");
        }

        Deque<Character> stack = new ArrayDeque<>();

        for (char current : text.toCharArray()) {
            if (OPEN_TO_CLOSE.containsKey(current)) {
                stack.push(current);
            } else if (current == ')' || current == ']' || current == '}') {
                if (stack.isEmpty()) {
                    return false;
                }

                char opening = stack.pop();
                if (OPEN_TO_CLOSE.get(opening) != current) {
                    return false;
                }
            } else {
                throw new IllegalArgumentException(
                    "Unsupported character: " + current
                );
            }
        }

        return stack.isEmpty();
    }
}

ArrayDeque 的 push 和 pop 都在同一端操作，可以自然表示栈。这里约定输入只能包含括号；出现其他字符会显式报错，而不是静默忽略。

五、Python 实现

OPEN_TO_CLOSE = {
    "(": ")",
    "[": "]",
    "{": "}",
}
CLOSING = set(OPEN_TO_CLOSE.values())

def is_valid(text: str) -> bool:
    if text is None:
        raise ValueError("text must not be None")

    stack: list[str] = []

    for current in text:
        if current in OPEN_TO_CLOSE:
            stack.append(current)
        elif current in CLOSING:
            if not stack:
                return False
            opening = stack.pop()
            if OPEN_TO_CLOSE[opening] != current:
                return False
        else:
            raise ValueError(f"unsupported character: {current!r}")

    return not stack

assert is_valid("{[()]}")
assert not is_valid("([)]")
assert not is_valid("(()")
assert not is_valid("())")
assert is_valid("")

空字符串没有未匹配的括号，因此在本题定义下是合法的。若具体题目规定字符串不能为空，可在入口处额外检查。

六、正确性与复杂度

每个左括号最多入栈一次，每个右括号最多弹栈一次；因此每个字符只处理常数次：

• 时间复杂度： O(n)；
• 额外空间复杂度： O(n)，最坏情况下所有字符都是左括号。

正确性来自栈顶顺序：对任意右括号来说，最近出现且尚未匹配的左括号必须与它匹配。若栈顶类型不匹配，则任何更早的左括号都被栈顶括号挡住，无法构成合法嵌套；若扫描结束栈不空，则仍有左括号没有匹配右括号。

七、栈还能解决什么问题？

• 表达式解析：暂存尚未完成的运算符或括号状态。
• 深度优先搜索：显式保存待访问节点，替代递归调用栈。
• 撤销操作：最近一次操作最先被撤销。
• 单调栈：维护一组单调候选，查找最近的更大或更小元素。
• 路径回溯：保存当前路径，并在返回时撤销最近一步选择。

这些问题看起来不同，但都存在“最近加入的状态需要先处理”的顺序关系。

八、常见错误

1. 只比较左右括号数量：无法发现 "([)]" 这种交叉匹配。
2. 弹栈前不检查空栈：遇到多余右括号会发生异常或错误结果。
3. 只检查过程，不检查结束状态：未匹配左括号会留在栈中。
4. 括号类型映射写反：建议统一使用“左括号 → 对应右括号”的映射。
5. 用栈处理不需要后进先出的关系：如果题目要求按到达顺序处理，应考虑队列。
6. 忽略输入字符约束：若题目只保证括号字符，可按该前提实现；否则明确非法字符策略。

九、与后续主题的连接

栈处理“最近未完成的状态”，队列则处理“最早到达、最早处理的状态”。下一篇会介绍队列，并用无权图最短路径说明为什么 BFS 必须按层、按先进先出的顺序扩展。

栈的思想还会在后续重新出现：括号专题会讨论更多括号约束，单调栈专题则会把“只保留有用候选”的不变量作为重点。

小结

栈的关键不是容器 API，而是后进先出的顺序和栈内不变量。遇到嵌套、撤销、最近未完成状态或深度优先过程时，可以考虑栈。括号匹配中，栈顶始终是最近一个尚未闭合的左括号，因此能在线性时间内检查类型和顺序。