栈的典型应用

学习目标

本节学习栈的典型应用。

学习完成后，你需要能够识别哪些问题适合使用栈。只要一个问题具有“最近出现的内容需要最先处理”的特点，就很可能可以用栈建模。

括号匹配

括号匹配是栈最经典的应用之一。

例如，判断下面的括号是否匹配：

([]{})

处理思路是：遇到左括号就入栈；遇到右括号就检查栈顶是否是对应的左括号。如果匹配，就把栈顶弹出；如果不匹配，说明括号结构有问题。

遇到左括号 (、[、{，压入栈。
遇到右括号 )、]、}，查看栈顶元素。
如果栈顶是对应的左括号，弹出栈顶。
如果栈为空或栈顶不匹配，说明括号不合法。
扫描结束后，如果栈为空，说明所有括号都匹配。

括号匹配代码

下面用四种语言实现简单的括号匹配：

bool isValid(string text) {
    stack<char> st;

    for (char ch : text) {
        if (ch == '(' || ch == '[' || ch == '{') {
            st.push(ch);
        } else {
            if (st.empty()) {
                return false;
            }

            char top = st.top();
            st.pop();

            if ((ch == ')' && top != '(') ||
                (ch == ']' && top != '[') ||
                (ch == '}' && top != '{')) {
                return false;
            }
        }
    }

    return st.empty();
}

boolean isValid(String text) {
    Deque<Character> stack = new ArrayDeque<>();

    for (char ch : text.toCharArray()) {
        if (ch == '(' || ch == '[' || ch == '{') {
            stack.push(ch);
        } else {
            if (stack.isEmpty()) {
                return false;
            }

            char top = stack.pop();

            if ((ch == ')' && top != '(') ||
                (ch == ']' && top != '[') ||
                (ch == '}' && top != '{')) {
                return false;
            }
        }
    }

    return stack.isEmpty();
}

def is_valid(text):
    stack = []

    for ch in text:
        if ch in "([{":
            stack.append(ch)
        else:
            if not stack:
                return False

            top = stack.pop()

            if (ch == ")" and top != "(") or                (ch == "]" and top != "[") or                (ch == "}" and top != "{"):
                return False

    return len(stack) == 0

bool IsValid(string text)
{
    Stack<char> stack = new Stack<char>();

    foreach (char ch in text)
    {
        if (ch == '(' || ch == '[' || ch == '{')
        {
            stack.Push(ch);
        }
        else
        {
            if (stack.Count == 0)
            {
                return false;
            }

            char top = stack.Pop();

            if ((ch == ')' && top != '(') ||
                (ch == ']' && top != '[') ||
                (ch == '}' && top != '{'))
            {
                return false;
            }
        }
    }

    return stack.Count == 0;
}

这段代码的关键是：每个右括号都必须匹配最近的尚未匹配的左括号。这个“最近”正是栈发挥作用的地方。

撤销操作

编辑器中的撤销操作也很适合用栈。

用户每执行一次操作，就把操作记录压入栈。当用户点击撤销时，弹出最近一次操作并反向执行。

输入 A -> 输入 B -> 删除 B
撤销时先恢复 B，因为删除 B 是最近一次操作

这种场景的核心仍然是后进先出：最近执行的操作最先被撤销。

函数调用栈

程序执行函数调用时，也会使用类似栈的机制。

当一个函数调用另一个函数时，当前函数的执行现场需要保存起来。被调用函数执行完成后，程序再回到上一个函数继续执行。

这就像不断压入函数调用记录，再按相反顺序返回。

main 调用 A
A 调用 B
B 执行结束，回到 A
A 执行结束，回到 main

这个过程正好符合后进先出。

单调栈的预告

在算法题中，还会遇到单调栈。单调栈不是一种新的基础结构，而是在普通栈的基础上维护某种单调性，例如从栈底到栈顶递增或递减。

它常用于解决“下一个更大元素”“柱状图最大矩形”等问题。现阶段只需要知道：这些进阶技巧仍然建立在栈的后进先出规则上。

本节小结

栈适合处理“最近出现的内容最先被处理”的问题。

括号匹配、撤销操作、函数调用、表达式求值和一些算法题技巧都与栈有关。判断一个问题能不能用栈，关键是看它是否存在明显的回退、撤销、最近匹配或反向恢复过程。