栈

概念讲解

什么是栈？

栈（Stack）是一种后进先出（LIFO, Last In First Out）的数据结构。

类比： 一摞盘子，只能从顶部拿取

栈的基本操作

操作 说明 时间复杂度
push 入栈（添加元素到栈顶） O(1)
pop 出栈（移除栈顶元素） O(1)
top 获取栈顶元素 O(1)
empty 判断栈是否为空 O(1)
size 获取栈的大小 O(1)

实现方式

数组实现

1234567891011121314151617181920212223const int N = 1005;
int stk[N];  // 栈数组
int tt = 0;  // 栈顶指针

// 入栈
void push(int x) {
    stk[++tt] = x;
}

// 出栈
void pop() {
    tt--;
}

// 获取栈顶
int top() {
    return stk[tt];
}

// 判断是否为空
bool empty() {
    return tt == 0;
}

STL stack

12345678910111213141516171819#include <stack>
using namespace std;

stack<int> stk;

// 入栈
stk.push(1);

// 出栈
stk.pop();

// 获取栈顶
int x = stk.top();

// 判断是否为空
if (stk.empty()) { ... }

// 获取大小
int sz = stk.size();

经典应用

1. 括号匹配

问题： 判断括号序列是否合法。

1234567891011121314151617181920bool isValid(string s) {
    stack<char> stk;
    
    for (char c : s) {
        if (c == '(' || c == '[' || c == '{') {
            stk.push(c);
        } else {
            if (stk.empty()) return false;
            
            char top = stk.top();
            stk.pop();
            
            if (c == ')' && top != '(') return false;
            if (c == ']' && top != '[') return false;
            if (c == '}' && top != '{') return false;
        }
    }
    
    return stk.empty();
}

2. 表达式求值

问题： 计算中缀表达式的值。

12345678910111213141516171819202122232425262728293031323334int calculate(string s) {
    stack<int> nums;
    stack<char> ops;
    
    for (int i = 0; i < s.size(); i++) {
        if (isdigit(s[i])) {
            int num = 0;
            while (i < s.size() && isdigit(s[i])) {
                num = num * 10 + (s[i] - '0');
                i++;
            }
            i--;
            nums.push(num);
        } else if (s[i] == '(') {
            ops.push('(');
        } else if (s[i] == ')') {
            while (ops.top() != '(') {
                calc(nums, ops);
            }
            ops.pop();  // 弹出 '('
        } else {
            while (!ops.empty() && priority(ops.top()) >= priority(s[i])) {
                calc(nums, ops);
            }
            ops.push(s[i]);
        }
    }
    
    while (!ops.empty()) {
        calc(nums, ops);
    }
    
    return nums.top();
}

3. 单调栈

问题： 找到每个元素右边第一个比它大的元素。

123456789101112131415vector<int> nextGreater(vector<int>& nums) {
    int n = nums.size();
    vector<int> result(n, -1);
    stack<int> stk;
    
    for (int i = 0; i < n; i++) {
        while (!stk.empty() && nums[stk.top()] < nums[i]) {
            result[stk.top()] = nums[i];
            stk.pop();
        }
        stk.push(i);
    }
    
    return result;
}

考点分析

初赛考查方式

  1. 选择题： 栈的特性

    • 例：栈的特点是什么？
    • 答：后进先出（LIFO）

  2. 程序阅读： 理解栈的操作过程

  3. 完善程序： 补全栈相关代码

常见题型

  • 括号匹配
  • 表达式求值
  • 单调栈

例题精讲

例题 1：括号匹配

题目： 判断括号序列 "([])" 是否合法。

解答：

1. 遇到 '('，入栈
2. 遇到 '['，入栈
3. 遇到 ']'，匹配栈顶 '['，出栈
4. 遇到 ')'，匹配栈顶 '('，出栈
5. 栈为空，合法

例题 2：栈的应用

题目： 用两个栈实现队列。

解答：

12345678910111213141516171819class MyQueue {
    stack<int> in, out;
    
    void push(int x) {
        in.push(x);
    }
    
    int pop() {
        if (out.empty()) {
            while (!in.empty()) {
                out.push(in.top());
                in.pop();
            }
        }
        int x = out.top();
        out.pop();
        return x;
    }
};

练习题

基础题

  1. 栈的特点是什么？
查看答案

栈的特点是后进先出（LIFO, Last In First Out）。

最后入栈的元素最先出栈，就像一摞盘子，只能从顶部拿取。

  1. 写出栈的五个基本操作。
查看答案
  1. push(x)：入栈，将元素 x 添加到栈顶
  2. pop()：出栈，移除栈顶元素
  3. top()：获取栈顶元素（不移除）
  4. empty()：判断栈是否为空
  5. size()：获取栈中元素个数

所有操作时间复杂度均为 O(1)。

  1. 用数组实现一个栈。
查看答案
1234567891011121314151617181920212223const int N = 1005;
int stk[N];  // 栈数组
int tt = 0;  // 栈顶指针

// 入栈
void push(int x) {
    stk[++tt] = x;
}

// 出栈
void pop() {
    tt--;
}

// 获取栈顶
int top() {
    return stk[tt];
}

// 判断是否为空
bool empty() {
    return tt == 0;
}

提高题

  1. 洛谷 P1739 表达式括号匹配
查看答案

使用栈匹配括号：

12345678910111213141516171819202122232425#include <iostream>
#include <stack>
using namespace std;

int main() {
    string s;
    cin >> s;
    stack<char> stk;
    
    for (char c : s) {
        if (c == '@') break;
        if (c == '(') {
            stk.push(c);
        } else if (c == ')') {
            if (stk.empty()) {
                cout << "NO" << endl;
                return 0;
            }
            stk.pop();
        }
    }
    
    cout << (stk.empty() ? "YES" : "NO") << endl;
    return 0;
}
  1. 洛谷 P1449 后缀表达式
查看答案

使用栈计算后缀表达式：

12345678910111213141516171819202122232425262728293031#include <iostream>
#include <stack>
using namespace std;

int main() {
    string s;
    cin >> s;
    stack<int> stk;
    
    for (int i = 0; i < s.size(); i++) {
        if (isdigit(s[i])) {
            int num = 0;
            while (isdigit(s[i])) {
                num = num * 10 + (s[i] - '0');
                i++;
            }
            stk.push(num);
            i--;
        } else if (s[i] == '+' || s[i] == '-' || s[i] == '*' || s[i] == '/') {
            int b = stk.top(); stk.pop();
            int a = stk.top(); stk.pop();
            if (s[i] == '+') stk.push(a + b);
            else if (s[i] == '-') stk.push(a - b);
            else if (s[i] == '*') stk.push(a * b);
            else stk.push(a / b);
        }
    }
    
    cout << stk.top() << endl;
    return 0;
}

易错点

⚠️ 注意：

  1. 栈为空时不能 pop 或 top
  2. 数组栈要注意大小限制
  3. STL stack 的 pop 不返回值
  4. 单调栈要维护栈内元素的单调性