---
title: "栈与队列"
description: "后进先出与先进先出，循环队列，以及单调栈和单调队列。"
---

> Documentation Index
> Fetch the complete documentation index at: https://cppguide.xyz/llms.txt
> Use this file to discover all available pages before exploring further.

# 栈与队列

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

本章的知识点与 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()` | 判断栈是否为空 |

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

```cpp
#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`：

```cpp
#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 可以用栈来写非递归版本。

### 括号匹配

```cpp
#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()` | 判断队列是否为空 |

### 循环队列

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

```cpp
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：

```cpp
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)$。
- **模拟排队过程**。银行叫号、缓冲区。

## 单调栈与单调队列

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

### 单调栈：找下一个更大元素

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

```cpp
#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$ 的滑动窗口里的最大值。队头始终是当前窗口的最大值，新元素进来时把队尾比它小的都挤出去。

```cpp
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 括号匹配](https://dailyup.run/tasks/508)

#### 题目描述

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

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

#### 输入格式

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

#### 输出格式

输出一行：括号全部配对输出 `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$ 时两者都能过。

#### 参考代码

> 🔒 参考代码已隐藏。请在网页版输入解锁密码查看：https://cppguide.xyz/ds/stack-queue/index.md

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

### 练习 2：后缀表达式求值

在线评测练习：[P1418 后缀表达式求值](https://dailyup.run/tasks/502)

#### 题目描述

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

#### 输入格式

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

#### 输出格式

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

#### 输入输出样例

输入

```
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，再判断它是数字还是运算符：

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

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

#### 参考代码

> 🔒 参考代码已隐藏。请在网页版输入解锁密码查看：https://cppguide.xyz/ds/stack-queue/index.md

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

## 小结

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

Source: https://cppguide.xyz/ds/stack-queue/index.mdx
