栈和队列是所有数据结构里最简单的两种,它们只允许在固定的位置进出。限制越多,行为越好预测,这就是它们好用的原因。
本章的知识点与 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,如果不及时判 NO,最后可能又回到 0,误判成合法。所以要在减到负数时立刻退出。- 空串。题目数据范围是
|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。
题目分析
这是栈最经典的应用,也是本章技术含量最高的练习之一。
后缀表达式的好处是不需要括号:运算符的位置本身就已经确定了运算顺序。求值过程极其规整:
- 从左往右扫;
- 遇到数字就压栈;
- 遇到运算符就弹出两个数——注意先弹出的是右操作数,后弹出的是左操作数——算完把结果压回栈;
- 扫完之后栈里恰好剩一个数,就是答案。
第 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)。 - 后缀表达式求值是栈最经典的应用:数字入栈,运算符弹两个算一个再压回,最后栈里只剩答案。
- 单种括号的匹配用计数就够,多种括号必须用栈——因为要记住「哪个左括号在等哪个右括号」。