1. 核心概念:FIFO#
1.1 基本定义#
#include <queue>
std::queue<int> q;cpp竞赛常用写法:
#include <bits/stdc++.h>
using namespace std;
queue<int> q;cppFIFO:First In, First Out,先进先出。
q.push(10);
q.push(20);
q.push(30);
cout << q.front(); // 10:最早入队
cout << q.back(); // 30:最新入队cpp出队顺序为 10 -> 20 -> 30。
1.2 两端职责#
| 位置 | 操作 |
|---|---|
| 队首 front | front() 读取、pop() 删除 |
| 队尾 back | back() 读取、push()/emplace() 插入 |
queue 不提供随机访问,不能直接访问第 i 个元素,也不能直接遍历中间元素。
2. queue 是容器适配器#
queue 不是独立实现一套存储结构,而是在底层容器上限制接口。默认底层容器为 std::deque<T>:
queue<int> q;
// 近似等价于 queue<int, deque<int>> q;cpp也可指定 list:
queue<int, list<int>> q;cpp底层容器需要支持:
front()、back()。push_back()。pop_front()。
因此通常使用 deque 或 list。vector 没有 pop_front(),不适合作为 queue 的底层容器:
// queue<int, vector<int>> q; // 不要这样使用,相关操作无法满足cpp竞赛中默认 queue<T> 即可,通常没有必要更换底层容器。
3. 核心接口#
3.1 入队:push 与 emplace#
queue<int> q;
q.push(10);
int x = 20;
q.push(x); // 拷贝入队
q.push(move(x)); // 移动入队,之后不要依赖 x 的原值
q.emplace(30); // 在队尾直接构造 intcpp复合类型:
queue<pair<int, int>> qp;
qp.push({1, 2});
qp.emplace(3, 4); // 直接构造 pair<int,int>(3,4)cpp对 int 等基本类型,push 与 emplace 通常没有性能区别。
3.2 访问队首与队尾#
cout << q.front(); // 队首
cout << q.back(); // 队尾cpp可以修改队首元素:
q.front() = 100;cpp但必须保证队列非空。空队列调用 front() 或 back() 是未定义行为。
3.3 出队:pop#
q.pop(); // 删除队首,不返回元素cpp正确读取并出队:
int x = q.front();
q.pop();cpp错误认知:
// int x = q.pop(); // 错:pop() 返回 voidcpp空队列调用 pop() 是未定义行为。
3.4 查询大小与判空#
q.size();
q.empty();cpp典型循环:
while (!q.empty()) {
int x = q.front();
q.pop();
// 处理 x
}cpp3.5 交换#
a.swap(b);
// 或 swap(a, b);cpp交换两个 queue 的内容。通常要求元素类型和底层容器类型一致。
4. queue 没有哪些功能#
queue 刻意只暴露 FIFO 所需接口:
// q[0]; // 错误:没有随机访问
// q.begin(), q.end(); // 错误:没有公开迭代器
// for (int x : q) {} // 错误:不能直接范围遍历
// q.clear(); // 错误:没有 clear 成员
// q.top(); // 错误:top 属于 stack / priority_queue
// q.reserve(n); // 错误:没有 reserve 接口cpp4.1 遍历只能逐个出队#
while (!q.empty()) {
cout << q.front() << ' ';
q.pop();
}cpp此操作会清空原队列。若必须保留原队列,可以先复制:
auto tmp = q; // O(n) 拷贝
while (!tmp.empty()) {
cout << tmp.front() << ' ';
tmp.pop();
}cpp4.2 清空队列#
q = queue<int>();cpp或:
queue<int>().swap(q);cpp也可以逐个 pop:
while (!q.empty()) q.pop();cpp但逐个 pop 只是清空逻辑内容,不一定立即释放底层全部内存;重新赋值为空队列通常更适合表达“重置”。
5. 元素类型与传参#
5.1 常见元素类型#
queue<int> q1; // 图节点
queue<pair<int, int>> q2; // 坐标、状态、{node, dist}
queue<tuple<int,int,int>> q3; // 三维状态
queue<string> q4; // 字符串状态cpp自定义结构体:
struct State {
int x, y, dist;
};
queue<State> q;
q.push({0, 0, 0});cpp5.2 函数传参#
void bfs(queue<int> &q); // 修改原队列
void inspect(queue<int> q); // 使用独立副本,O(n) 拷贝cpp一般 BFS 直接在函数内部创建局部队列,不必把队列作为参数传来传去。
5.3 取出队首对象#
auto cur = q.front(); // 复制队首元素
q.pop();cpp对 pair、tuple、小型 struct 通常足够高效。若元素是大对象,要意识到 auto cur 会复制;不要在 pop() 后再访问先前保存的 front() 引用,因为它已经失效。
6. 复杂度#
以默认 deque 为底层容器:
| 操作 | 时间复杂度 |
|---|---|
push() / emplace() |
均摊 O(1) |
pop() |
O(1) |
front() / back() |
O(1) |
size() / empty() |
O(1) |
| 拷贝整个 queue | O(n) |
| 逐个 pop 清空 | O(n) |
swap |
通常 O(1) |
总成本还包括元素自身的构造、拷贝、移动和析构。queue<string> 与 queue<int> 的单次操作实际成本不能只看容器接口复杂度。
queue 没有 capacity()、reserve(),不能像 vector 一样手动预留容量。
7. 最重要应用:图的 BFS#
7.1 BFS 能解决什么#
在无权图或每条边权值相同的图中,从源点进行 BFS,可以求出最少边数意义下的最短距离。
核心不变量:队列中的节点按距离层次依次扩展,节点第一次被访问时获得最短距离。
7.2 标准模板#
int n, m, s;
// g 为 vector<vector<int>> 邻接表,点编号 1 到 n
vector<int> dist(n + 1, -1);
queue<int> q;
dist[s] = 0;
q.push(s);
while (!q.empty()) {
int u = q.front();
q.pop();
for (int v : g[u]) {
if (dist[v] != -1) continue; // 已访问
dist[v] = dist[u] + 1;
q.push(v);
}
}cpp时间复杂度 O(V+E),空间复杂度 O(V)。
7.3 为什么入队时就标记#
dist[v] = dist[u] + 1; // 入队前标记
q.push(v);cpp如果等出队时才标记,同一节点可能被多个邻居重复加入队列,增加时间和内存,甚至使按层逻辑复杂化。
7.4 普通 queue 不适用于一般正权最短路#
边权不同时,先入队不代表距离最短:
- 一般非负权图:Dijkstra +
priority_queue。 - 只有 0/1 边权:0-1 BFS +
deque。 - 无权或等权图:普通 BFS +
queue。
不要因为算法名称里有“队列”就始终使用同一个容器。
8. 网格 BFS#
int n, m;
cin >> n >> m;
vector<string> a(n);
for (auto &row : a) cin >> row;
const int dx[4] = {-1, 1, 0, 0};
const int dy[4] = {0, 0, -1, 1};
vector<vector<int>> dist(n, vector<int>(m, -1));
queue<pair<int, int>> q;
dist[0][0] = 0;
q.push({0, 0});
while (!q.empty()) {
auto [x, y] = q.front();
q.pop();
for (int k = 0; k < 4; ++k) {
int nx = x + dx[k];
int ny = y + dy[k];
if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
if (a[nx][ny] == '#') continue;
if (dist[nx][ny] != -1) continue;
dist[nx][ny] = dist[x][y] + 1;
q.push({nx, ny});
}
}cpp重点检查:
- 起点和终点是否为障碍。
- 边界条件是否完整。
- 是否在入队时设置距离。
pair的成员含义是否始终为{x,y}。
9. 按层处理与多源 BFS#
9.1 按层处理#
每一轮 while 开始时,队列中恰好保存当前层的所有节点:
dist[s] = 0;
q.push(s);
while (!q.empty()) {
int layerSize = q.size(); // 必须先保存
while (layerSize--) {
int u = q.front();
q.pop();
// 处理当前层节点,并向队列加入下一层
}
}cpp不要直接在层循环条件中反复使用变化的 q.size(),因为处理节点时会 push/pop,size 会变化。
9.2 多源 BFS#
把所有源点以距离 0 初始入队:
queue<int> q;
vector<int> dist(n + 1, -1);
for (int source : sources) {
dist[source] = 0;
q.push(source);
}
while (!q.empty()) {
int u = q.front();
q.pop();
for (int v : g[u]) {
if (dist[v] != -1) continue;
dist[v] = dist[u] + 1;
q.push(v);
}
}cpp最终 dist[v] 表示节点 v 到最近源点的距离。常用于多个火源、多个感染点、多个出口等问题。
10. 拓扑排序:Kahn 算法#
queue 用来维护所有当前入度为 0 的节点:
int n, m;
// g 为有向图邻接表
vector<int> indeg(n + 1, 0);
// 读入每条 u -> v:g[u].push_back(v); ++indeg[v];
queue<int> q;
for (int i = 1; i <= n; ++i) {
if (indeg[i] == 0) q.push(i);
}
vector<int> order;
while (!q.empty()) {
int u = q.front();
q.pop();
order.push_back(u);
for (int v : g[u]) {
if (--indeg[v] == 0) q.push(v);
}
}
if ((int)order.size() != n) {
// 有向图存在环
}cpp时间复杂度 O(V+E)。
若题目要求字典序最小拓扑序,通常把 queue 换成小根堆 priority_queue<int, vector<int>, greater<int>>,每次取编号最小的可用节点。
11. 排队模拟与循环队列操作#
11.1 队首移到队尾#
int x = q.front();
q.pop();
q.push(x);cpp适用于轮转、发牌、约瑟夫类模拟中的“保留并移到末尾”。
11.2 出队并记录答案#
vector<int> ans;
while (!q.empty()) {
ans.push_back(q.front());
q.pop();
}cpp11.3 queue 不是循环数组本身#
“队首移到队尾”是逻辑操作,不代表 queue 内部一定用循环数组实现。默认底层 deque 的具体内存布局由实现决定,不要依赖。
12. queue 与其他容器的选择#
| 需求 | 推荐容器 | 原因 |
|---|---|---|
| 先进先出、BFS、拓扑排序 | queue |
接口最符合逻辑 |
| 后进先出、DFS、括号匹配 | stack 或 vector |
LIFO |
| 两端都可插入删除、0-1 BFS、单调队列 | deque |
双端操作,可访问内部 |
| 每次取优先级最高/最低元素 | priority_queue |
堆序而非 FIFO |
| 已知队列最大容量,追求简洁高效 | vector + head |
连续数组,head 只前进 |
| 需要随机访问、排序或任意遍历 | vector/deque |
queue 不支持这些操作 |
12.1 BFS 的 vector + head 替代写法#
vector<int> q(n);
int head = 0, tail = 0;
q[tail++] = s;
dist[s] = 0;
while (head < tail) {
int u = q[head++];
for (int v : g[u]) {
if (dist[v] != -1) continue;
dist[v] = dist[u] + 1;
q[tail++] = v;
}
}cpp前提:必须能证明入队总数不超过分配容量,否则 tail 越界。每个节点最多入队一次时,容量 n 足够。
12.2 单调队列不能用普通 queue 实现#
滑动窗口最值需要访问和删除队尾,并根据条件维护内部顺序,应使用 deque。普通 queue 不能删除队尾,也不能遍历内部元素。
13. 高频错误与避坑清单#
13.1 空队列执行 front/back/pop#
if (!q.empty()) {
int x = q.front();
q.pop();
}cpp13.2 把 pop 当成返回元素的函数#
// int x = q.pop(); // 错
int x = q.front();
q.pop();cpp13.3 使用 top 而不是 front#
// q.top(); // 错
q.front(); // 对cpppriority_queue 才使用 top()。
13.4 试图下标访问或范围遍历#
queue 不支持 q[i]、迭代器、范围 for。需要这些能力时应换容器,而不是强行模拟。
13.5 BFS 出队时才标记已访问#
可能重复入队。通常应在设置距离或访问标记后立即入队。
13.6 忘记先保存队首再 pop#
// q.pop();
// int u = q.front(); // 已变成下一个元素,逻辑错误
int u = q.front();
q.pop();cpp13.7 pop 后继续使用旧引用#
// int &u = q.front();
// q.pop();
// cout << u; // u 已悬空,危险cpp应在 pop 前复制需要的值。
13.8 按层遍历时使用动态 size#
int sz = q.size();
while (sz--) {
// 当前层
}cpp13.9 用普通 BFS 处理一般带权最短路#
普通 queue 只保证 FIFO,不会按最小距离排序。一般非负权最短路应使用 Dijkstra 与优先队列。
14. 一页速记#
#include <queue>
queue<int> q; // 默认底层 deque<int>
q.push(x); // 队尾入队
q.emplace(x); // 队尾原位构造
q.front(); // 读队首
q.back(); // 读队尾
q.pop(); // 删队首,返回 void
q.size(); q.empty();
if (!q.empty()) {
int x = q.front();
q.pop();
}
queue<pair<int,int>> qp;
qp.push({x, y});
qp.emplace(x, y);
auto [a, b] = qp.front();
qp.pop();
while (!q.empty()) { // 消费式遍历
int x = q.front();
q.pop();
}
q = queue<int>(); // 重置清空
// BFS 核心
vector<int> dist(n + 1, -1);
queue<int> bfs;
dist[s] = 0;
bfs.push(s);
while (!bfs.empty()) {
int u = bfs.front();
bfs.pop();
for (int v : g[u]) {
if (dist[v] != -1) continue;
dist[v] = dist[u] + 1;
bfs.push(v);
}
}
// 按层处理
while (!bfs.empty()) {
int sz = bfs.size();
while (sz--) {
// 处理当前层
}
}cpp最终必须牢牢记住:
- queue 是 FIFO:队尾入,队首出。
front()读取队首,pop()删除队首且不返回值。- 空队列不能调用
front/back/pop。 - queue 没有下标、迭代器、范围遍历和 clear。
- BFS 在入队时设置距离或访问标记。
- 无权图 BFS 用 queue;0-1 BFS 用 deque;Dijkstra 用 priority_queue。
- 按层 BFS 先保存
int sz = q.size()。 - 单调队列、双端操作需要 deque,不是普通 queue。