C++ 栈（stack）和队列（queue）入门

# C++ 栈（stack）和队列（queue）入门

栈和队列都是用来存放数据的数据结构。它们的主要区别是：**取出数据的顺序不同**。

- 栈：后进先出，最后放进去的元素最先取出来。 - 队列：先进先出，最先放进去的元素最先取出来。

本文先介绍基本概念，再讲解 C++ 标准库的用法，最后介绍如何用数组模拟。

## 一、栈：后进先出

栈可以理解为一摞盘子：每次把盘子放到最上面，取盘子时也从最上面取。

允许插入和删除元素的一端叫作**栈顶**，另一端叫作**栈底**。

假设依次放入 `1、2、3`：

```text 栈顶 → 3 2 栈底 → 1 ```

此时取出元素的顺序是：

```text 3 2 1 ```

这种规则叫作 **LIFO（Last In, First Out，后进先出）**。

### 1. 定义一个栈

标准头文件是 `<stack>`。在 GCC 竞赛环境中，也可以使用 `<bits/stdc++.h>`，但它不是标准 C++ 头文件。

```cpp stack<int> s; // 存放整数 stack<char> st; // 存放字符 stack<string> ss; // 存放字符串 ```

其中，尖括号内写元素类型，后面写变量名。

### 2. 常用操作

| 操作 | 作用 | 注意事项 | | --- | --- | --- | | `s.push(x)` | 将 `x` 放入栈顶 | 元素个数增加 1 | | `s.pop()` | 删除栈顶元素 | 没有返回值，调用前必须保证非空 | | `s.top()` | 访问栈顶元素 | 不删除元素，调用前必须保证非空 | | `s.empty()` | 判断栈是否为空 | 空时返回 `true`，否则返回 `false` | | `s.size()` | 获取元素个数 | 返回无符号整数类型 |

默认底层容器为 `deque` 时，上述操作的时间复杂度均为 $O(1)$。

### 3. 操作过程

下面的“栈内元素”均按**栈底到栈顶**的顺序书写。

| 操作 | 栈内元素 | 说明 | | --- | --- | --- | | `s.push(10)` | `10` | 放入 10 | | `s.push(20)` | `10 20` | 放入 20 | | `s.push(30)` | `10 20 30` | 放入 30 | | `s.top()` | `10 20 30` | 得到 30，栈不变 | | `s.pop()` | `10 20` | 删除 30 | | `s.top()` | `10 20` | 得到 20，栈不变 |

如果需要保存被删除的元素，要先读取，再删除：

```cpp if (!s.empty()) { int x = s.top(); s.pop(); cout << x << endl; } ```

不能写成 `int x = s.pop();`，因为 `pop()` 没有返回值。

### 4. 完整示例：逆序输出

输入 $n$ 个整数，按照输入顺序入栈，再依次取出栈顶，就能逆序输出。

```cpp #include <bits/stdc++.h>

using namespace std;

#define endl '\n' #define int long long

const int N = 2e5 + 5; const int MOD = 1e9 + 7; const int INF = 0x3f3f3f3f3f3f3f3f; const double PI = acos(-1.0);

void solve() { int n; cin >> n; // 读入元素个数

stack<int> s; // 定义一个空栈，每次调用 solve() 都会重新创建 // 按输入顺序入栈，后读入的元素会放在先读入的元素上面 for (int i = 1; i <= n; i++) { int x; cin >> x; s.push(x); // 将 x 放入栈顶 }

// 栈是后进先出：最后读入的元素最先输出，因此得到逆序结果 // 先判断栈非空，才能安全访问和删除栈顶 while (!s.empty()) { cout << s.top() << " "; // 读取并输出栈顶，top() 不会删除元素 s.pop(); // 删除刚输出的栈顶，让下一个元素成为栈顶 } cout << endl; // 所有元素输出后换行 }

signed main() { ios::sync_with_stdio(false); cin.tie(nullptr);

int tt = 1; // cin>>tt; while (tt--) solve(); return 0; }

// ease2k // eAs1nGG-_- // ```

输入：

```text 5 1 2 3 4 5 ```

输出（忽略行末空格）：

```text 5 4 3 2 1 ```

代码讲解：

1. `s.push(x)` 将读入的整数放到栈顶。 2. 全部入栈后，最后输入的 `5` 位于栈顶。 3. `s.top()` 读取当前栈顶，`s.pop()` 删除当前栈顶。 4. 删除 `5` 后，`4` 成为栈顶，重复操作直到栈为空。

每个元素入栈、出栈各一次，因此时间复杂度为 $O(n)$，额外空间复杂度为 $O(n)$。

## 二、队列：先进先出

队列可以理解为排队买票：新来的人排在队伍末尾，排在最前面的人先离开。

队列中，取出元素的一端叫作**队头**，插入元素的一端叫作**队尾**。

假设依次放入 `1、2、3`：

```text 队头 → 1 2 3 ← 队尾 ```

此时取出元素的顺序是：

```text 1 2 3 ```

这种规则叫作 **FIFO（First In, First Out，先进先出）**。

### 1. 定义一个队列

标准头文件是 `<queue>`。

```cpp queue<int> q; // 存放整数 queue<char> qc; // 存放字符 queue<string> qs; // 存放字符串 ```

### 2. 常用操作

| 操作 | 作用 | 注意事项 | | --- | --- | --- | | `q.push(x)` | 将 `x` 放入队尾 | 元素个数增加 1 | | `q.pop()` | 删除队头元素 | 没有返回值，调用前必须保证非空 | | `q.front()` | 访问队头元素 | 不删除元素，调用前必须保证非空 | | `q.back()` | 访问队尾元素 | 不删除元素，调用前必须保证非空 | | `q.empty()` | 判断队列是否为空 | 空时返回 `true`，否则返回 `false` | | `q.size()` | 获取元素个数 | 返回无符号整数类型 |

默认底层容器为 `deque` 时，上述操作的时间复杂度均为 $O(1)$。

注意：普通队列没有 `top()`，访问队头应该使用 `front()`。

### 3. 操作过程

下面的“队列内元素”均按**队头到队尾**的顺序书写。

| 操作 | 队列内元素 | 说明 | | --- | --- | --- | | `q.push(10)` | `10` | 放入 10 | | `q.push(20)` | `10 20` | 放入 20 | | `q.push(30)` | `10 20 30` | 放入 30 | | `q.front()` | `10 20 30` | 得到 10，队列不变 | | `q.back()` | `10 20 30` | 得到 30，队列不变 | | `q.pop()` | `20 30` | 删除 10 | | `q.front()` | `20 30` | 得到 20，队列不变 |

如果需要保存出队元素，同样要先读取，再删除：

```cpp if (!q.empty()) { int x = q.front(); q.pop(); cout << x << endl; } ```

### 4. 完整示例：按输入顺序输出

输入 $n$ 个整数，依次入队，再不断取出队头，就能按照原来的顺序输出。

```cpp #include <bits/stdc++.h>

using namespace std;

#define endl '\n' #define int long long

const int N = 2e5 + 5; const int MOD = 1e9 + 7; const int INF = 0x3f3f3f3f3f3f3f3f; const double PI = acos(-1.0);

void solve() { int n; cin >> n; // 读入元素个数

queue<int> q; // 定义一个空队列，每次调用 solve() 都会重新创建 // 按输入顺序入队，后读入的元素排在先读入的元素后面 for (int i = 1; i <= n; i++) { int x; cin >> x; q.push(x); // 将 x 放入队尾 }

// 队列是先进先出：最先读入的元素最先输出，因此保持输入顺序 // 先判断队列非空，才能安全访问和删除队头 while (!q.empty()) { cout << q.front() << " "; // 读取并输出队头，front() 不会删除元素 q.pop(); // 删除刚输出的队头，让下一个元素成为队头 } cout << endl; // 所有元素输出后换行 }

signed main() { ios::sync_with_stdio(false); cin.tie(nullptr);

int tt = 1; // cin>>tt; while (tt--) solve(); return 0; }

// ease2k // eAs1nGG-_- // ```

输入：

```text 5 1 2 3 4 5 ```

输出（忽略行末空格）：

```text 1 2 3 4 5 ```

代码讲解：

1. `q.push(x)` 将读入的整数放到队尾。 2. 全部入队后，最先输入的 `1` 位于队头。 3. `q.front()` 读取当前队头，`q.pop()` 删除当前队头。 4. 删除 `1` 后，`2` 成为队头，重复操作直到队列为空。

每个元素入队、出队各一次，因此时间复杂度为 $O(n)$，额外空间复杂度为 $O(n)$。

## 三、用数组和 vector 模拟栈和队列

除了使用标准库，也可以用数组和下标实现栈、队列。下面均采用从 1 开始存放元素的写法。

这些代码片段假设数组容量足够，并且在访问、删除前已经判断非空。

### 1. 数组模拟栈

用 `a` 存放元素，用 `tt` 表示栈顶下标。由于从 1 开始存放，`tt` 同时也是栈内元素个数。

```cpp const int N = 2e5 + 5; int a[N], tt; ```

每次使用前初始化：

```cpp tt = 0; ```

各项操作：

```cpp a[++tt] = x; // 入栈：先移动栈顶，再存入元素

if (tt > 0) { cout << a[tt] << endl; // 访问栈顶 tt--; // 出栈 }

bool flag = (tt == 0); // 是否为空 int cnt = tt; // 元素个数 ```

例如，依次放入 `10、20、30` 后，`tt = 3`，栈顶为 `a[3] = 30`。执行 `tt--` 后，`tt = 2`，栈顶变为 `a[2] = 20`。

出栈时不需要真的把数组位置清零：有效元素只在 `a[1]` 到 `a[tt]` 中，后面的旧数据不再属于栈。

### 2. 数组模拟队列

用 `a` 存放元素，`hh` 表示队头下标，`tt` 表示队尾下标。

```cpp const int N = 2e5 + 5; int a[N], hh, tt; ```

每次使用前初始化：

```cpp hh = 1; tt = 0; ```

有效元素位于 `a[hh]` 到 `a[tt]` 中；当 `hh > tt` 时，队列为空。

```cpp a[++tt] = x; // 入队：队尾后移，再存入元素

if (hh <= tt) { cout << a[hh] << endl; // 访问队头 cout << a[tt] << endl; // 访问队尾 hh++; // 出队 }

bool flag = (hh > tt); // 是否为空 int cnt = tt - hh + 1; // 元素个数 ```

例如，依次放入 `10、20、30` 后，`hh = 1`、`tt = 3`。执行 `hh++` 后，`hh = 2`，队头变为 `a[2] = 20`，队列还剩 2 个元素。

**这种简单写法不会复用已经出队的位置。** 因此，数组容量要按本次初始化之后的入队总次数预留，而不能只按同时在队列中的最多元素个数预留。需要反复复用空间时，可以使用循环队列，或直接使用 `queue`。

### 3. vector：可以动态调整大小的数组

`vector` 可以理解为一个能够动态调整大小的数组，标准头文件是 `<vector>`。它支持下标访问，也能在末尾添加或删除元素。

固定数组 `int a[N]` 创建后长度就是 `N`，不能直接改变长度；`vector<int> a` 则可以根据需要增加元素。

```cpp vector<int> a; // 创建空 vector，此时 size() 为 0 vector<int> b(6); // 创建 6 个元素，下标为 0～5，整数初值均为 0 vector<int> c(6, 10); // 创建 6 个元素，每个元素初值为 10 ```

如果沿用从 1 开始存放数据的习惯，可以创建 `n + 1` 个元素，把下标 0 留空：

```cpp vector<int> a(n + 1); for (int i = 1; i <= n; i++) { cin >> a[i]; // 使用 a[1] 到 a[n]，a[0] 不存放有效数据 } ```

这里 `a.size()` 是 `n + 1`，因为它也计算了没有使用的 `a[0]`。

| 操作 | 作用 | 时间复杂度 | | --- | --- | --- | | `a[i]` | 访问下标为 `i` 的元素，必须保证下标合法 | $O(1)$ | | `a.push_back(x)` | 在末尾添加 `x` | 均摊 $O(1)$ | | `a.pop_back()` | 删除末尾元素，无返回值，要求非空 | $O(1)$ | | `a.back()` | 访问末尾元素，要求非空 | $O(1)$ | | `a.size()` | 获取当前元素个数，返回无符号整数类型 | $O(1)$ | | `a.empty()` | 判断是否没有元素 | $O(1)$ | | `a.clear()` | 删除所有元素，使 `size()` 变为 0 | $O(n)$，其中 $n$ 为原元素个数 |

`push_back()` 的“均摊 $O(1)$”表示连续执行多次时，平均每次的成本是常数级；单次操作如果触发扩容，可能需要搬移已有元素，耗时为 $O(n)$。

**注意 `resize()` 和 `reserve()` 的区别：**

```cpp vector<int> a; a.resize(6); // 元素个数变为 6，现在可以访问 a[0] 到 a[5] a[1] = 10;

vector<int> b; b.reserve(6); // 仅预留至少能容纳 6 个元素的空间，size() 仍为 0 // b[1] = 10; // 错误：还没有元素，不能通过下标写入 b.push_back(10); // 正确：添加一个元素，此时 b.size() 为 1，b[0] 为 10 ```

`size()` 表示已经存在的元素个数，`capacity()` 表示当前分配的空间能容纳多少个元素。通过下标访问时，要看 `size()`，不能只看 `capacity()`。

### 4. 用 vector 模拟栈

有两种常见写法。

**写法一：保留数组模拟的下标规则。**

如果最多同时存放 `n` 个元素，就创建 `n + 1` 个位置，然后像操作数组一样操作它：

```cpp vector<int> a(n + 1); // 预先创建元素，使用下标 1～n int tt = 0; // tt 表示栈顶下标，也表示有效元素个数

a[++tt] = 10; // 入栈 10 a[++tt] = 20; // 入栈 20，此时栈顶为 a[2]

if (tt > 0) { cout << a[tt] << endl; // 输出栈顶 20 tt--; // 出栈，只移动下标 } ```

此时栈内有效元素只有一个，但 `a.size()` 仍然是 `n + 1`。判断栈是否为空应该用 `tt == 0`，不能用 `a.empty()`。

**写法二：直接用 vector 的末尾作为栈顶。**

这种写法不需要单独维护 `tt`，也不预留下标 0，所有元素都属于栈。

```cpp vector<int> a; // 空 vector 就是空栈

a.push_back(10); // 入栈 10，此时 a 为 [10] a.push_back(20); // 入栈 20，此时 a 为 [10, 20] a.push_back(30); // 入栈 30，此时 a 为 [10, 20, 30]

while (!a.empty()) { cout << a.back() << " "; // 末尾是栈顶，依次输出 30、20、10 a.pop_back(); // 删除末尾元素，元素个数减少 1 } cout << endl; ```

对应关系为：

| 栈操作 | `stack` 写法 | `vector` 末尾模拟写法 | | --- | --- | --- | | 入栈 | `s.push(x)` | `a.push_back(x)` | | 读取栈顶 | `s.top()` | `a.back()` | | 出栈 | `s.pop()` | `a.pop_back()` | | 判断为空 | `s.empty()` | `a.empty()` | | 元素个数 | `s.size()` | `a.size()` |

### 5. 用 vector 模拟队列

可以保留数组模拟队列的思路：在末尾追加元素，用 `hh` 指向当前队头。

下面保留从 1 开始存放的习惯，下标 0 不存放有效数据：

```cpp vector<int> a(1); // 先创建 a[0]，实际入队元素从 a[1] 开始 int hh = 1; // 队头下标 int tt = 0; // 队尾下标

a.push_back(10); // 入队：在末尾追加 10，存放于 a[1] tt++; // 队尾下标变为 1 a.push_back(20); // 入队：在末尾追加 20，存放于 a[2] tt++; // 队尾下标变为 2 a.push_back(30); // 入队：在末尾追加 30，存放于 a[3] tt++; // 队尾下标变为 3

while (hh <= tt) { cout << a[hh] << " "; // 读取队头，依次输出 10、20、30 hh++; // 出队：移动队头下标，不删除 vector 中的元素 } cout << endl;

int cnt = tt - hh + 1; // 有效元素个数，此时为 0 ```

这里的对应关系是：

| 队列操作 | `vector` 模拟写法 | | --- | --- | | 入队 | `a.push_back(x); tt++;` | | 访问队头 | `a[hh]`，要求 `hh <= tt` | | 访问队尾 | `a[tt]`，要求 `hh <= tt` | | 出队 | `hh++`，要求 `hh <= tt` | | 判断为空 | `hh > tt` | | 有效元素个数 | `tt - hh + 1` |

**逻辑上出队不代表 vector 中的元素被删除。** 输出结束后，队列为空，但 `a.size()` 仍然是 4，包括下标 0 和三个已出队元素。因此，不能用 `a.empty()` 判断这个队列是否为空，也不能用 `a.size()` 计算有效元素个数。

这种写法能够动态扩容，但仍保留已经出队的元素，存储空间随入队总次数增长。如果总共入队 $m$ 次，所用空间为 $O(m)$。

不要为了出队反复执行 `a.erase(a.begin() + 1)`：删除靠前的元素需要移动后面的元素，单次可能花费 $O(n)$，连续删除可能达到 $O(n^2)$。用队头下标移动，就能让每次出队保持 $O(1)$。

重新开始一组数据时，可以这样初始化：

```cpp a.clear(); // 删除上一组保留的所有元素 a.resize(1); // 重新创建不使用的 a[0] hh = 1; tt = 0; ```

## 四、常见错误

### 1. 对空容器访问或删除

对空栈调用 `top()`、`pop()`，或对空队列调用 `front()`、`back()`、`pop()`，都会违反这些操作的使用要求，不能依赖它们返回某个默认值。

正确做法是先判断：

```cpp if (!s.empty()) cout << s.top() << endl; if (!q.empty()) cout << q.front() << endl; ```

### 2. 把访问当成删除

`top()`、`front()` 和 `back()` 只访问元素，不删除元素。

下面的写法在队列非空时会不断输出同一个元素，无法结束：

```cpp while (!q.empty()) { cout << q.front() << endl; // 缺少 q.pop(); } ```

### 3. 使用下标访问标准库栈、队列

`stack` 和 `queue` 不支持 `s[i]`、`q[i]`，也不直接提供迭代器供遍历。

如果通过不断 `pop()` 来输出元素，原容器会被清空；需要保留原数据时，可以先复制一份，再操作副本：

```cpp stack<int> t = s; while (!t.empty()) { cout << t.top() << " "; t.pop(); } ```

复制包含 $n$ 个元素的栈或队列，需要 $O(n)$ 的时间和额外空间。

### 4. 清空容器或处理多组数据

`stack` 和 `queue` 没有 `clear()`，可以不断删除元素：

```cpp while (!s.empty()) s.pop(); while (!q.empty()) q.pop(); ```

本文的完整示例把容器定义在 `solve()` 内，每次调用都会得到一个新的空容器。如果使用全局容器，需要注意清空上一次的数据；如果用全局数组模拟，需要重新初始化下标。

另外，本文数组模拟中的全局 `tt` 表示栈顶或队尾；完整模板中 `main()` 内的局部 `tt` 表示测试组数。它们作用域不同，编写代码时要区分各自用途。

## 五、应用场景与对比

| 对比项 | 栈 `stack` | 队列 `queue` | | --- | --- | --- | | 取出顺序 | 后进先出 | 先进先出 | | 插入位置 | 栈顶 | 队尾 | | 删除位置 | 栈顶 | 队头 | | 读取下一个待删除元素 | `top()` | `front()` | | 访问队尾 | 不适用 | `back()` | | 典型用途 | 括号匹配、撤销操作、迭代实现深度优先搜索 | 广度优先搜索、按到达顺序处理任务 |

以括号匹配为例：最近遇到但尚未匹配的左括号，应当最先与右括号匹配，所以适合用栈。

以广度优先搜索为例：先发现的节点先处理，新发现的节点放到队尾，所以适合用队列。

记住两个取出顺序，再结合操作名称，就能区分它们：

```text stack：push 入栈，top 看栈顶，pop 删除栈顶。 queue：push 入队，front 看队头，back 看队尾，pop 删除队头。 ```