数据结构复习：栈 (Stack) 的核心应用与算法实战

1. 栈的基本概念回顾

栈是一种后进先出 (LIFO, Last In First Out) 的线性数据结构。

  • 主要操作：push (入栈), pop (出栈), top/peek (查看栈顶), isEmpty (判空)。
  • 核心本质：栈主要用于处理具有完全包含关系或逆序处理的问题。

2. 栈的四大核心应用场景

2.1 符号匹配与语法解析 (Symbol Matching)

这是栈最经典的应用。编译器在检查代码语法（如括号匹配 { [ ( ) ] }）时，利用栈来确保每一个右括号都能匹配最近的一个未匹配的左括号。

  • 原理：遇到左括号入栈，遇到右括号检查栈顶是否为对应的左括号，若是则出栈，否则报错。

2.2 表达式求值 (Expression Evaluation)

计算机无法像人类一样直接理解中缀表达式（如 3 + 4 * 5），通常需要转化为后缀表达式 (逆波兰表达式, RPN) 或 前缀表达式。

  • 中缀转后缀：使用一个栈存储运算符，根据优先级决定何时出栈输出。
  • 后缀表达式求值：使用一个栈存储操作数。遇到数字入栈，遇到运算符则弹出栈顶两个数字进行计算，结果再入栈。

2.3 函数调用与递归 (Function Call & Recursion)

在操作系统层面，栈用于管理函数的调用。

  • 调用栈 (Call Stack)：每当调用一个函数时，系统会为该函数创建一个栈帧 (Stack Frame)，存储局部变量、参数和返回地址。
  • 递归：递归本质上就是利用系统栈来保存每一层的状态。如果递归过深，会导致 Stack Overflow。

2.4 单调栈 (Monotonic Stack)

这是算法竞赛和高难度面试题中的重点。

  • 定义：栈内元素保持单调递增或单调递减。
  • 应用：用于寻找数组中左边/右边第一个比当前元素大/小的元素。
  • 时间复杂度：每个元素最多进栈一次、出栈一次，所以复杂度通常是 $O(n)$。

3. LeetCode 精选算法题 (C++ 版)

以下题目涵盖了栈的不同考察方向，建议按照顺序练习。

题目 1：有效的括号 (基础)

LeetCode 20: Valid Parentheses

描述：给定一个只包括 '(', ')', '{', '}', '[', ']' 的字符串，判断字符串是否有效。

解题思路：
标准的栈应用。遇到左括号入栈，遇到右括号判断栈顶。注意处理栈空的情况。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
class Solution {
public:
    bool isValid(string s) {
        if (s.size() % 2 != 0) return false; // 奇数长度一定无效
        stack<char> st;
        for (char c : s) {
            if (c == '(' || c == '[' || c == '{') {
                st.push(c);
            } else {
                if (st.empty()) return false;
                char top = st.top();
                if ((c == ')' && top == '(') || 
                    (c == ']' && top == '[') || 
                    (c == '}' && top == '{')) {
                    st.pop();
                } else {
                    return false;
                }
            }
        }
        return st.empty();
    }
};
````

### 题目 2：最小栈 (辅助栈思想)

**LeetCode 155: Min Stack**

> **描述**：设计一个支持 `push`, `pop`, `top` 操作，并能在常数时间内检索到最小元素的栈。

解题思路：

使用两个栈。

1. `dataStack`: 正常存储数据。
    
2. `minStack`: 同步存储当前的最小值。每次 push 时，如果新值小于等于 `minStack` 栈顶，则也 push 进 `minStack`。
    

C++

```cpp
class MinStack {
    stack<int> s;
    stack<int> min_s;
public:
    MinStack() {}
    
    void push(int val) {
        s.push(val);
        // 注意这里是 <=，重复的最小值也要入栈
        if (min_s.empty() || val <= min_s.top()) {
            min_s.push(val);
        }
    }
    
    void pop() {
        if (s.top() == min_s.top()) {
            min_s.pop();
        }
        s.pop();
    }
    
    int top() { return s.top(); }
    
    int getMin() { return min_s.top(); }
};

题目 3：逆波兰表达式求值 (后缀表达式)

LeetCode 150: Evaluate Reverse Polish Notation

描述：根据逆波兰表示法，求表达式的值。输入: ["2","1","+","3","*"] -> ((2 + 1) * 3) = 9。

解题思路：

遇到数字 push，遇到符号 pop 两个数字计算后 push 结果。注意减法和除法的操作数顺序（先 pop 出来的是右操作数）。

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<long long> st;
        for (const string& s : tokens) {
            if (s == "+" || s == "-" || s == "*" || s == "/") {
                long long b = st.top(); st.pop();
                long long a = st.top(); st.pop();
                if (s == "+") st.push(a + b);
                else if (s == "-") st.push(a - b);
                else if (s == "*") st.push(a * b);
                else if (s == "/") st.push(a / b);
            } else {
                st.push(stoll(s));
            }
        }
        return st.top();
    }
};

题目 4：每日温度 (单调栈经典)

LeetCode 739: Daily Temperatures

描述：给定一个温度列表，对于每一个位置，求下一次气温升高需要等待的天数。如果之后都没升高，填 0。

解题思路：

维护一个单调递减栈（存储下标）。

  1. 遍历数组，如果当前温度 T[i] 大于栈顶下标对应的温度 T[top]，说明找到了栈顶元素右边第一个比它大的数。

  2. 此时弹出栈顶，计算下标差值 i - top，即为等待天数。

  3. 重复上述过程直到栈为空或当前温度不再大于栈顶温度，将 i 入栈。

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        int n = temperatures.size();
        vector<int> ans(n, 0);
        stack<int> st; // 存下标
        
        for (int i = 0; i < n; ++i) {
            // 当前元素大于栈顶元素 -> 破坏了递减性质 -> 触发计算
            while (!st.empty() && temperatures[i] > temperatures[st.top()]) {
                int prevIndex = st.top();
                st.pop();
                ans[prevIndex] = i - prevIndex;
            }
            st.push(i);
        }
        return ans;
    }
};

题目 5：验证栈序列 (模拟)

LeetCode 946: Validate Stack Sequences

描述：给定 pushed 和 popped 两个序列，判断 popped 是否可能是 pushed 的弹出序列。

解题思路：

直接模拟。

  1. 遍历 pushed 数组，将元素入栈。

  2. 每次入栈后，循环检查：如果栈不为空且栈顶元素等于 popped 当前指向的元素，则出栈，并移动 popped 指针。

  3. 最后如果栈为空，说明序列合法。

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
        stack<int> st;
        int j = 0; // 指向 popped 数组
        for (int x : pushed) {
            st.push(x);
            while (!st.empty() && st.top() == popped[j]) {
                st.pop();
                j++;
            }
        }
        return st.empty();
    }
};

4. 总结

在期末复习或面试中，遇到以下关键词请优先考虑 栈：

  1. 最近相关性：如“匹配最近的括号”、“消除相邻重复项”。

  2. 反转/逆序：如“链表逆序打印”、“逆波兰表达式”。

  3. 嵌套结构：如“解析 XML/JSON”、“目录路径简化”。

  4. 下一个更大/更小元素：这是单调栈的专属领域。