麦地

Back

1. 核心概念:FIFO#

1.1 基本定义#

#include <queue>
std::queue<int> q;
cpp

竞赛常用写法:

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

queue<int> q;
cpp

FIFO: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);      // 在队尾直接构造 int
cpp

复合类型:

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() 返回 void
cpp

空队列调用 pop() 是未定义行为。

3.4 查询大小与判空#

q.size();
q.empty();
cpp

典型循环:

while (!q.empty()) {
    int x = q.front();
    q.pop();
    // 处理 x
}
cpp

3.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 接口
cpp

4.1 遍历只能逐个出队#

while (!q.empty()) {
    cout << q.front() << ' ';
    q.pop();
}
cpp

此操作会清空原队列。若必须保留原队列,可以先复制:

auto tmp = q; // O(n) 拷贝
while (!tmp.empty()) {
    cout << tmp.front() << ' ';
    tmp.pop();
}
cpp

4.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});
cpp

5.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 标准模板#

时间复杂度 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#

重点检查:

  1. 起点和终点是否为障碍。
  2. 边界条件是否完整。
  3. 是否在入队时设置距离。
  4. 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 初始入队:

最终 dist[v] 表示节点 v 到最近源点的距离。常用于多个火源、多个感染点、多个出口等问题。


10. 拓扑排序:Kahn 算法#

queue 用来维护所有当前入度为 0 的节点:

时间复杂度 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();
}
cpp

11.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();
}
cpp

13.2 把 pop 当成返回元素的函数#

// int x = q.pop(); // 错
int x = q.front();
q.pop();
cpp

13.3 使用 top 而不是 front#

// q.top();   // 错
q.front();    // 对
cpp

priority_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();
cpp

13.7 pop 后继续使用旧引用#

// int &u = q.front();
// q.pop();
// cout << u; // u 已悬空,危险
cpp

应在 pop 前复制需要的值。

13.8 按层遍历时使用动态 size#

int sz = q.size();
while (sz--) {
    // 当前层
}
cpp

13.9 用普通 BFS 处理一般带权最短路#

普通 queue 只保证 FIFO,不会按最小距离排序。一般非负权最短路应使用 Dijkstra 与优先队列。


14. 一页速记#

最终必须牢牢记住:

  1. queue 是 FIFO:队尾入,队首出。
  2. front() 读取队首,pop() 删除队首且不返回值。
  3. 空队列不能调用 front/back/pop。
  4. queue 没有下标、迭代器、范围遍历和 clear。
  5. BFS 在入队时设置距离或访问标记。
  6. 无权图 BFS 用 queue;0-1 BFS 用 deque;Dijkstra 用 priority_queue。
  7. 按层 BFS 先保存 int sz = q.size()。
  8. 单调队列、双端操作需要 deque,不是普通 queue。
Comment seems to stuck. Try to refresh?✨