Skip to content

栈与队列

后进先出与先进先出,循环队列,以及单调栈和单调队列。

Updated View as Markdown

栈和队列是所有数据结构里最简单的两种,它们只允许在固定的位置进出。限制越多,行为越好预测,这就是它们好用的原因。

本章的知识点与 GESP、CSP-J/S 大纲的对应关系如下。

考试 大纲要求 本章位置
GESP C++ 六级 考点 7:栈、队列、循环队列的基本定义、应用场景和常见操作 全章
CSP-J/S 入门级 3.1 线性结构:栈、队列 全章
CSP-J/S 入门级 3.2 字符串:括号序列与表达式(栈的经典应用) 练习 1、练习 2
GESP C++ 六级 单调栈与单调队列(算法优化) 单调栈与单调队列

栈

栈(Stack)只允许在一端插入和删除,这一端叫栈顶。排在最后进来的元素最先出去,所以叫后进先出(LIFO,Last In First Out)。

生活里的类比是一摞盘子:只能从最上面拿,也只能往最上面放。想拿最下面那个,得先把上面的都拿走。

栈的基本操作只有四个:

操作 含义
push(x) 把 x 压入栈顶
pop() 弹出栈顶元素
top() 查看栈顶元素,不弹出
empty() 判断栈是否为空

用数组手写一个栈非常直接。

#include <bits/stdc++.h>
using namespace std;

const int N = 100005;
int stk[N];  // 存放栈里的元素
int tp = 0;  // 栈顶下标,0 表示空栈

void push(int x) { stk[++tp] = x; }   // 压栈
void pop() { --tp; }                   // 出栈
int top() { return stk[tp]; }          // 栈顶
bool empty() { return tp == 0; }       // 是否为空

在 C++ 里更省事的是直接用 STL 的 stack:

#include <bits/stdc++.h>
using namespace std;

int main() {
    stack<int> s;
    s.push(1);
    s.push(2);
    s.push(3);
    cout << s.top() << endl; // 输出 3
    s.pop();
    cout << s.top() << endl; // 输出 2
    cout << s.size() << endl; // 输出 2
    return 0;
}

栈的每个操作都是 O(1)。

栈的典型应用

  • 括号匹配。遇到左括号压栈,遇到右括号看栈顶是不是对应的左括号。
  • 表达式求值。后缀表达式的计算、中缀转后缀都靠栈,见表达式那一章。
  • 函数调用。递归本质上是系统在帮你维护一个调用栈,这也是「递归爆栈」的由来。
  • 撤销操作。编辑器的撤销记录就是一个个压进栈里的状态。
  • 进制转换。短除法得到的余数是倒序的,压栈再弹出正好。
  • 深度优先搜索。DFS 可以用栈来写非递归版本。

括号匹配

#include <bits/stdc++.h>
using namespace std;

int main() {
    string s;
    cin >> s;
    stack<char> st;
    bool ok = true;
    for (char c : s) {
        if (c == '(' || c == '[' || c == '{') {
            st.push(c);
        } else {
            if (st.empty()) { ok = false; break; }
            char t = st.top();
            if ((c == ')' && t == '(') ||
                (c == ']' && t == '[') ||
                (c == '}' && t == '{')) {
                st.pop();
            } else {
                ok = false;
                break;
            }
        }
    }
    if (!st.empty()) ok = false;
    cout << (ok ? "YES" : "NO") << endl;
    return 0;
}

队列

队列(Queue)只允许在一端插入、另一端删除。插入的一端叫队尾,删除的一端叫队头。先进来的先出去,所以叫先进先出(FIFO,First In First Out)。

生活里的类比是排队买票:后来的人排在队尾。

操作 含义
push(x) 把 x 放到队尾
pop() 弹出队头元素
front() 查看队头元素
back() 查看队尾元素
empty() 判断队列是否为空

循环队列

用数组模拟队列时,如果队头队尾都只往后走,前面空出来的位置就浪费了,队尾很快会撞到数组末尾。解决办法是让下标绕回去,这就是循环队列。

const int N = 100005;
int q[N];
int head = 0, tail = 0;  // [head, tail) 区间存放元素

bool empty() { return head == tail; }

void push(int x) {
    q[tail] = x;
    tail = (tail + 1) % N;
}

void pop() {
    head = (head + 1) % N;
}

int front() { return q[head]; }

这个写法用「队空」区分状态,代价是会浪费一个位置,队列最多存 N - 1 个元素。要存满就再加一个计数器记录当前元素个数。

在 C++ 里同样可以直接用 STL:

queue<int> q;
q.push(1);
q.push(2);
cout << q.front() << endl; // 1
q.pop();
cout << q.front() << endl; // 2

队列的典型应用

  • 广度优先搜索。BFS 的每一层都靠队列维护访问顺序。
  • 任务调度。打印机任务队列、操作系统的进程就绪队列。
  • 滑动窗口最值。用单调队列把 O(nk) 优化到 O(n)。
  • 模拟排队过程。银行叫号、缓冲区。

单调栈与单调队列

它们就是栈和队列的用法,只是额外要求里面的元素保持单调,用来快速找出「左边或右边第一个比它大/小的元素」以及「窗口内的最值」。

单调栈:找下一个更大元素

给定数组,求每个元素右边第一个比它大的元素的下标。

#include <bits/stdc++.h>
using namespace std;

int a[100005], ans[100005];

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];

    stack<int> s; // 存下标,栈内对应的值单调不增
    for (int i = 1; i <= n; i++) {
        while (!s.empty() && a[s.top()] < a[i]) {
            ans[s.top()] = i; // i 就是它右边第一个更大的
            s.pop();
        }
        s.push(i);
    }
    for (int i = 1; i <= n; i++) cout << ans[i] << " ";
    return 0;
}

每个元素最多进栈一次、出栈一次,所以总复杂度是 O(n),比两层循环的 O(n^2) 快得多。

单调队列:滑动窗口最值

求长度为 k 的滑动窗口里的最大值。队头始终是当前窗口的最大值,新元素进来时把队尾比它小的都挤出去。

deque<int> dq; // 存下标,对应的值单调递减
for (int i = 1; i <= n; i++) {
    while (!dq.empty() && dq.front() <= i - k) dq.pop_front(); // 过期的出队
    while (!dq.empty() && a[dq.back()] <= a[i]) dq.pop_back(); // 比新元素小的出队
    dq.push_back(i);
    if (i >= k) cout << a[dq.front()] << " "; // 队头就是窗口最大值
}

同样是 O(n)。

复杂度

操作 栈 队列 单调栈/单调队列
插入 O(1) O(1) 均摊 O(1)
删除 O(1) O(1) 均摊 O(1)
访问顶端 O(1) O(1) O(1)

常见易错点

  • 栈和队列是「操作受限的线性表」,只能在一端或两端操作,不能像数组那样随便访问中间元素。
  • STL 的 stack 和 queue 没有迭代器,不能遍历,也不能用范围 for。
  • pop() 只删除不返回。想取栈顶或队头,先用 top() / front() 再 pop()。
  • 循环队列的容量是 N - 1,忘了这一条会莫名其妙丢数据。
  • 调用 top()、front()、pop() 之前一定先判断非空,空容器上操作是未定义行为。
  • 单调栈和单调队列的复杂度是均摊线性,不是每步都 O(1),但总量是 O(n)。
  • 单调栈求「下一个更大元素」时,栈里存的是下标而不是值。存值就没法判断「那个位置过期了没有」,也没法回填答案。
  • 后缀表达式求值,先弹出的是右操作数。减法和除法写反顺序,答案直接错;这个 bug 用加法样例测不出来。
  • 只有一种括号时用计数、多种括号时必须用栈。计数法省内存但只适用于单种括号。

练习

练习 1:括号匹配

在线评测练习:P1424 括号匹配

题目描述

输入一行只由小括号 ( 和 ) 组成的字符串,判断括号是否配对。

配对的含义是:每个 ) 都能在它左边找到一个尚未被配对的 (。

输入格式

输入一行,包含一个只由 ( 和 ) 组成的字符串。

输出格式

输出一行:括号全部配对输出 YES,否则输出 NO。

输入输出样例

输入

(()())

输出

YES

输入

(()))

输出

NO

数据范围

  • 1 \le |s| \le 10^6,字符串只含 ( 与 )。

题目分析

正文里的括号匹配示例处理了三种括号,本题只有小括号,所以可以写得更简单——甚至连栈都不需要,一个计数器就够了:

  • 遇到 (,计数加 1;
  • 遇到 ),计数减 1;如果减到负数,说明右括号多了,直接判 NO;
  • 扫完之后计数必须为 0,否则左括号多了。

为什么计数就够了? 因为只有一种括号时,「尚未配对的左括号个数」这一个数字就能完整描述栈的状态——栈里存的全是同一种字符,用长度表示足矣。这是「能用简单结构就别用复杂结构」的典型例子。

但要注意:一旦括号种类变成多种(比如 ()[]{}),计数就不行了,必须真的用栈,因为要记住「哪个左括号在等哪个右括号」。这正是正文示例用栈的原因。

两个必须处理的细节:

  1. )( 这种「先多后少」的情况。计数扫描过程中会先变成 -1,如果不及时判 NO,最后可能又回到 0,误判成合法。所以要在减到负数时立刻退出。
  2. 空串。题目数据范围是 |s| \ge 1,但如果真的遇到空串,计数为 0,应输出 YES(空串是合法括号序列)。

复杂度:时间 O(n),空间 O(1)(计数法)或 O(n)(栈法)。|s| 到 10^6 时两者都能过。

参考代码

如果题目要求多种括号混在一起,就把 cnt 换成 stack<char>,按正文示例的写法处理。

练习 2:后缀表达式求值

在线评测练习:P1418 后缀表达式求值

题目描述

输入一行后缀表达式(逆波兰表达式),操作数为非负整数,运算符只有 +、-、*、/(整除),元素之间用空格分隔。输出表达式的值。

输入格式

输入一行,包含一个后缀表达式,元素之间用一个空格隔开。

输出格式

输出一行一个整数,表示表达式的值。

输入输出样例

输入

3 4 + 2 *

输出

14

输入

5 1 2 + 4 * + 3 -

输出

14

(第二个样例对应中缀表达式 5 + (1+2) \times 4 - 3。)

数据范围

  • 操作数与运算符的总个数不超过 10^5。
  • 操作数为不超过 10^9 的非负整数。
  • 保证表达式合法,中间结果与最终结果都在 int 范围内,除法不会除以 0。

题目分析

这是栈最经典的应用,也是本章技术含量最高的练习之一。

后缀表达式的好处是不需要括号:运算符的位置本身就已经确定了运算顺序。求值过程极其规整:

  1. 从左往右扫;
  2. 遇到数字就压栈;
  3. 遇到运算符就弹出两个数——注意先弹出的是右操作数,后弹出的是左操作数——算完把结果压回栈;
  4. 扫完之后栈里恰好剩一个数,就是答案。

第 3 步的顺序是最容易错的地方。 以 5 3 - 为例:

  • 先弹出的是 3(右操作数);
  • 后弹出的是 5(左操作数);
  • 正确计算是 5 - 3 = 2,如果写成 3 - 5 = -2 就错了。

加法和乘法交换,写反了看不出问题;减法和除法一旦写反,答案就全错。练这题的价值就在这里——用加法样例测不出这个 bug,必须用减法或除法验证。

为什么这样算一定对? 因为后缀表达式的定义保证了:每个运算符出现时,它需要的两个操作数恰好已经算好并压在栈顶。这是「用栈维护待合并的部分结果」的典型场景。

输入处理要小心:元素之间用空格分隔,但操作数可能是多位数(比如 1234),所以不能按字符读。最省事的做法是用 cin >> string 逐个读入 token,再判断它是数字还是运算符:

string t;
while (cin >> t) { ... }   // 自动跳过空白,按空格切分

s 是运算符就按运算处理;否则用 stoll(s) 转成数字(10^9 以内 int 也够,但中间结果可能超出,稳妥起见用 long long)。

参考代码

此题承上启下:它用到的「弹两个、算一下、压回去」模式,是表达式求值、计算器、编译器前端的基础。下一节《表达式》会讲中缀表达式的转换——那一步比求值更难,但求值这一环永远是栈。

小结

  • 栈是后进先出,队列是先进先出,两者的基本操作都是 O(1)。
  • 循环队列用取模让下标回绕,代价是浪费一个位置来区分空和满。
  • 栈的经典应用有括号匹配、表达式求值和递归;队列的经典应用是 BFS 和任务调度。
  • 单调栈找「下一个更大/更小元素」,单调队列求「窗口最值」,两者都能把 O(n^2) 降到 O(n)。
  • 后缀表达式求值是栈最经典的应用:数字入栈,运算符弹两个算一个再压回,最后栈里只剩答案。
  • 单种括号的匹配用计数就够,多种括号必须用栈——因为要记住「哪个左括号在等哪个右括号」。
Navigation

Type to search…

↑↓ navigate↵ selectEsc close