算法竞赛中的队列：BFS、单调队列与优先队列实战指南-北京尧图网络

平时刷题的时候很多朋友对队列的态度是“这不就是个先进先出的容器吗会用push和pop就够了”。但真到比赛现场队列的用法远比你想的宽广。BFS、拓扑排序、滑动窗口最值、堆优化Dijkstra这些高频套路背后全是队列的影子。这篇就好好聊聊算法竞赛里的队列和queue不同队列形态怎么选、手写库函数怎么取舍以及那些题解里很少明说的细节与坑。1. 队列在竞赛里的定位不只是“先进先出”那么简单队列的核心语义是FIFOFirst In First Out先进入的元素先被取出就像食堂排队打饭先来的先打菜。计算机科学里很多问题天然具备“按顺序处理”的形态最典型的就是宽度优先搜索从起点出发先到的状态先被扩展一层一层向外推进这时候队列就是最自然的容器。但竞赛里出现的“队列”其实不止一种我一般把它们分成三类队列形态对应容器核心特性典型场景普通队列queue先进先出从队尾进、队首出BFS、拓扑排序、层序遍历双端队列deque两端都能进出支持随机访问单调队列、01BFS、滑动窗口优先队列priority_queue出队顺序按优先级本质是堆Dijkstra、贪心合并、对顶堆很多人学到这里会有一个误区觉得普通队列就是STL里的queue容器单调队列就是deque优先队列就是priority_queue。这个对应关系大体没错但更重要的是想清楚“这道题为什么需要这种队列”而不是“这道题应该用哪个容器”。BFS用queue是因为广搜要求严格按层号递增的顺序处理节点单调队列用deque是因为既要维护窗口范围又要随时从两端删掉失去价值的数据Dijkstra用优先队列是因为每次要取出当前距离最小的点而不是最早入队的点。这三个场景内部的“为什么”如果搞明白了面试和比赛里遇到变形题就不慌。比如有些图题表面上是求最短路但边权只有0和1这时候就不需要priority_queue一个deque就能解决复杂度还能从O(m log n)降到O(m)。这种优化就属于典型的“看穿本质”。1.1 常用接口与效率先把接口捋一遍这是基本功。queue的操作很少push(x)从队尾入队pop()弹出队首元素无返回值front()访问队首元素back()访问队尾元素empty()判空size()返回元素个数deque在queue的基础上增加了push_front(x) / pop_front()push_back(x) / pop_back()front() / back()operator[]可以直接按下标访问O(1)priority_queue的操作类似但语义不同push(x)插入元素top()访问堆顶优先级最高元素pop()弹出堆顶默认是大根堆即top()返回最大值这里提一个新手经常忽略的点queue的pop()设计成不返回元素Java的poll()会返回C的不会。很多初学者写int x q.pop()然后编译报错卡在那里心态崩掉。竞赛环境里为了少写一行代码有人会自封装一个pop_front返回值的函数但标题党的思路是能忍住就忍别为了省事增加出错面。效率方面STL的queue底层是dequepush和pop都是均摊O(1)但常数比手写数组大。priority_queue的push和pop是O(log n)top是O(1)。数据量上了百万、千万级别手写队列的优势就出来了。1.2 竞赛里三种队列的“分工”上面那张表已经给了大致分工这里再补充几个容易混淆的点。普通queue解决的核心问题是“层序”也就是按步数/距离从近到远处理状态前提是每条边的代价一致。如果边权不同queue就管不住了得用带优先级的容器。deque解决的核心问题是“两端决策”。最典型的是单调队列你要在窗口移动时快速淘汰掉已经不在窗口里的旧元素或者在队尾维护单调性没有双端操作就做不到。01BFS也是边权为0的点要尽量往前插边权为1的点往后放这样才能保证第一次取出时距离已经最小。priority_queue解决的核心问题是“即时取最值”而且这个最值是动态变化的。堆排序、贪心选最小、最短路松弛、合并果子全都是“重复取当前集合中的最小/最大值”这个模型。所以看到题里说要不断取最大或最小第一反应就应该是优先队列而不是排序后取首元素——因为集合在动态增长变化。2. 手写队列还是直接用STL容器这是很多刚开始刷题的人纠结的问题。我会给出明确建议一般题目直接用STL完全够。但如果你追求极限常数或者题目数据量特别大、时间限制特别紧手写是更好的选择。2.1 手写数组队列的模板手写普通队列的思路其实很简单用数组模拟“环形缓冲”。const int MAXN 200010; int q[MAXN]; int head 0, tail 0; // tail 指向下一个入队位置 void push(int x) { q[tail] x; } int pop() { return q[head]; } bool empty() { return head tail; } int front() { return q[head]; } int size() { return tail - head; }这个写法里head和tail都是下标tail永远指向下一个空位。出队就是head往后挪数组里被“跳过”的元素其实还在但已经不会再被访问到逻辑上就算删除了。为什么预留200010而不是动态增长因为手写队列追求的就是“省去STL的封装开销”通常题目给的元素总数是明确的你只要保证数组开得足够大就行。我一般会开成数据规模上限再加10到20防止下标越界。如果题目有多组数据要重置队列直接head tail 0即可不需要真正清空数组效率很高。有人问如果一直入队tail会不会把数组写爆会的。所以竞赛里有一招叫“循环队列”当tail到达数组末尾时折回开头再用取模操作判断队空/队满。但说实话绝大多数竞赛题的数据量不会让你在队列里塞超过N个元素开双倍空间已经足够安全循环队列那个写法调试起来繁琐不值得。我把这段写完顺带提一下另一个常见写法int q[MAXN]; int head 0, tail -1; // tail 指向队尾元素 // 判空 head tail两种写法都能跑通但我自己习惯tail从0开始因为上面那种填充语句读起来更自然。关键是别在代码里混用这是学习时的常见事故现场。2.2 STL容器使用的几个关键细节直接讲坑。第一个坑queue没有clear()。这是个让无数人抓狂的设计。C的queue容器并没有提供清空成员函数你要清空要么重新构造q queueint();要么借助swapqueueint emptyQ; q.swap(emptyQ);多组测试的时候最容易在这里出错——上一组数据的残留元素没有清掉下一组BFS结果自然不对。而且这种错误非常隐蔽数据量小的时候跑样例一遍过数据量稍大就出奇怪答案。第二个坑priority_queue默认是大根堆。想要小根堆时必须写全模板参数priority_queueint, vectorint, greaterint pq;注意greater 这里的int类型要和你存的元素类型一致。有人偷懒写成priority_queueint, vector , greater在C17下能跑但老版本的编译器会报错比赛环境不一定支持建议老老实实写全。第三个坑结构化绑定不要乱用。C17之后可以写auto [d, u] pq.top();这在本地编译很爽但一些比赛环境可能还在用C14代码会直接编译失败。参加比赛前一定先确认编译器版本别拿本地环境的标准去套评测机。2.3 选型建议我的判断规则很简单数据规模在10^5级别以下STL随便用常数影响小数据规模到10^6级别或者BFS状态总数特别大手写数组队列更稳需要队列存复杂结构体时优先用STL queue手写反而容易越界单调队列一定用deque别自己造轮子优先队列一定用priority_queue手写堆很难写对当然这里说的“用STL”不是让你完全不管底层。理解数组模拟对调试很有帮助尤其当你需要打印队列内部状态时直接遍历q[head..tail-1]比通过STL接口方便得多。3. 队列的主场BFS的模板化思路BFS宽度优先搜索是队列在竞赛里最重要的应用场景。很多刚接触的人会把BFS写成DFS的回溯形式或者干脆换一种堆栈写法结果代码越写越乱。其实BFS就是一个固定范式背下来往里填状态就行。3.1 最朴素的BFS模板以下是最常用的图BFS模板#include bits/stdc.h using namespace std; const int MAXN 100010; vectorint adj[MAXN]; int dist[MAXN]; queueint q; void bfs(int start) { memset(dist, -1, sizeof(dist)); dist[start] 0; q.push(start); while (!q.empty()) { int u q.front(); q.pop(); for (int v : adj[u]) { if (dist[v] ! -1) continue; dist[v] dist[u] 1; q.push(v); } } }几个重点dist数组不仅在记录距离同时充当了“是否访问过”的标记因为初始化为-1一旦被赋值就说明已经入队过。这比单独开一个vis数组少一个维度的状态。为什么第一次访问到某个点时dist就是最短距离因为BFS按层扩展。起点在第0层它所有邻居在第1层第一层的所有邻居在第2层……队列天然维护了这个顺序当你取出一个第k层的节点时队列里剩下的要么是第k层的其他节点要么是第k1层的节点不可能出现第k2层的节点比第k1层更早被取出的情况。所以第一次扩展到的距离一定就是最短距离。这其实是最朴素也最重要的正确性证明很多人会做但说不清。面试或者写题解的时候能把这段话写出来观感完全不一样。3.2 BFS的经典变种与适配模板掌握之后来看高频变种。第一种是多源BFS。比如题目给了多个起点要求每个格子到最近起点的距离。做法是把所有起点一次性全部入队并设dist0然后正常跑BFS。核心逻辑是把所有起点当成一个虚拟超级源点的邻居这个源点连接到所有起点然后从源点出发BFS。等效于把所有起点push进去之后的扩展顺序依然是严格的近到远。第二种是01BFS。当边权只有0或1时普通BFS不能保证第一次出队就是最短距离因为走0权边可以“免费”前进普通队列会破坏这个严格分层。解法是用deque遇到0权边时把节点放到队首遇到1权边时放到队尾。dequeint dq; dist[st] 0; dq.push_front(st); while (!dq.empty()) { int u dq.front(); dq.pop_front(); for (auto [v, w] : edges[u]) { if (dist[v] dist[u] w) { dist[v] dist[u] w; if (w 0) dq.push_front(v); else dq.push_back(v); } } }注意这个写法里没有“只访问一次”的continue逻辑了因为后到达的节点可能通过更短的0权路径更新。这也体现了“为什么不是所有图都能用BFS求最短路”——边权一旦不统一队列的天然顺序就失效了。第三种是双向BFS。适用于已知终点、状态空间很大的搜索题比如一些字符串变换题。思路是从起点和终点同时出发交替扩展状态两边相遇时就算出答案。复杂度可以从单向的指数级降到近似两个半程的分叉相乘。实现时通常维护两个vis数组或两个map记录距离每次取当前队列较小的一端扩展。第四种是隐式图BFS。状态不是现成的图节点而是棋盘、数组、数字组合。典型如八数码、华容道、推箱子每次从当前状态生成所有可达状态用dist数组记录到达该状态的步数。有时候为了判重会用一个整数编码状态或者直接用map/哈希。这类题最检验对BFS的理解是否到位因为所有代码都得自己写没有任何图论模板可以直接套。3.3 BFS的三个高频失误我在排练队友的代码时发现最常见的三个失误如下其一入队和标记不同步。常见写法是取出节点时才标记vis但问题在于同一个节点可能在它入队之前就已经被另一个邻居入队了如果不在此前标记就会出现重复入队甚至死循环。正确做法是一旦决定push立刻更新dist/vis。其二状态边界判断顺序写错。比如迷宫题有些朋友先访问数组再判断坐标是否越界数组越界访问直接崩溃。正确的是先判断越界再访问。其三多组测试忘记重置队列和dist。这个我在前边已经提过但值得单独重复因为它真的能浪费一小时去查“明明样例都对为什么提交全错”。4. 单调队列滑动窗口的利器单调队列是“队列”这个知识点里含金量最高的一块。很多新手看到“单调队列”四个字就害怕其实它就是个运行中不断维护单调性的双端队列。它的出现场景很明确在滑动窗口里快速找最值。4.1 单调队列到底在干嘛假设给一个数组a[1..n]和一个定长窗口k对于每个i求a[i-k1..i]的最大值。暴力做法是O(nk)窗口每次右移一位重新扫描一遍。单调队列能把这优化到O(n)原理是利用元素在窗口内的“新旧关系”淘汰不可能成为答案的元素。怎么淘汰比如求最大值我们维护一个从队首到队尾单调递减的队列队列里存的是元素下标。新来一个元素a[i]时先把队首那些已经滑出窗口的下标弹掉判断条件是q.front() i - k 1从队尾开始把所有值小于等于a[i]的元素弹出因为它们在a[i]还存在于窗口期间永远不可能是最大值把当前下标i放入队尾队首下标对应的值就是当前窗口最大值“从队尾弹出较小元素”这一步写起来只有两行但它是整个算法正确性和效率的核心。可以这样理解a[i]比前面那些元素都新而且比它们大那么在窗口继续向右滑的过程中只要a[i]还在窗口里那些旧且小的元素就永远没有出头之日留着纯属浪费。这体现了单调队列的另一个重要特性——单调性维护的是“未来可能成为答案”的候选集合。4.2 滑动窗口最大值模板直接给一份可AC的模板#include bits/stdc.h using namespace std; const int MAXN 1000010; int a[MAXN]; dequeint dq; // 存下标 int main() { int n, k; cin n k; for (int i 1; i n; i) cin a[i]; for (int i 1; i n; i) { // 弹出不在窗口内的队首 while (!dq.empty() dq.front() i - k 1) 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()] ; } return 0; }细节一队列里存的是下标而不是值。因为判断元素是否出窗口必须用到下标光存值无法得知该元素是否还“活着”。这是绝大多数新手会踩的第一个坑。细节二队首弹出和队尾弹出的顺序。一般建议先处理队首过期元素再维护单调性插入新元素。某些题目顺序调换也可以但统一用“先删过期再维护单调”更不容易错。细节三比较符号取“”而不是“”。求最大值时遇到相等的旧元素我们宁可直接弹出因为新元素更晚过期价值更大。这个细节直接决定单调队列是否能正确处理重复值不少题解都忽视这一点。4.3 单调队列的进阶用法滑动窗口只是个引子单调队列在DP优化里同样是大杀器。比如经典的“烽火传递”问题在一条道路上每个烽火台有一定代价你要保证连续k个烽火台至少有一个被点燃求最小代价。这个题的状态转移是dp[i] w[i] min(dp[i-k]..dp[i-1])而那个“区间最小值”正是滑动窗口最值问题可以用单调队列把每次O(k)的转移优化到O(1)。再比如环状数组问题环形数组的区间和最大值需要把数组复制一份变成长度2n的线性数组再配合前缀和与单调队列来做。这类题变化多但万变不离其宗——你永远在处理“限制范围内的最值”这个核心诉求。单调队列和单调栈的对比也值得说一句。单调栈通常用于找某个位置的左右第一个更大/更小元素解决“之前/之后比自己大多少”的问题单调队列则侧重于“窗口内最值”这种滑动范围查询。它们底层思想相通都是维护一个候选序列区别只在于是否受“窗口右移”影响是否需要从队首弹出过期元素。面试时被问到这两个数据结构能把区别讲清楚是加分项。5. 优先队列隐形的“队列”核心优先队列说白了就是堆的STL封装。它并不满足队列的FIFO特性出队顺序由优先级决定但在竞赛语境里大家习惯把它和队列放在一起讨论因为很多“队列思想”题最终要靠它实现。比如多个进程排队每个进程有优先级优先级高的先执行这就是典型优先队列场景。换到算法里Dijkstra的每个“当前最短路径的点”就是最高优先级。5.1 三个经典应用场景第一个堆优化Dijkstra。这是优先队列在竞赛里出现频率最高的地方。朴素Dijkstra每次要遍历所有点找距离最小的复杂度O(n²)面对1e5级别的图直接爆炸。堆优化思路是把(dist[u], u)二元组丢进小根堆每次取出堆顶如果这个距离已经过时则跳过。模板如下#include bits/stdc.h using namespace std; typedef pairint, int PII; const int MAXN 100010; const int INF 0x3f3f3f3f; vectorPII adj[MAXN]; int dist[MAXN]; void dijkstra(int s) { memset(dist, 0x3f, sizeof(dist)); dist[s] 0; priority_queuePII, vectorPII, greaterPII pq; pq.push({0, s}); while (!pq.empty()) { auto [d, u] pq.top(); pq.pop(); if (d ! dist[u]) continue; // 过时节点跳过 for (auto [v, w] : adj[u]) { if (dist[v] dist[u] w) { dist[v] dist[u] w; pq.push({dist[v], v}); } } } }这段代码最值得讲的就是if (d ! dist[u]) continue;。因为在松弛过程中同一个节点可能被不同长度路径多次压入堆如果你不检查就直接处理会做很多无用功。这一行行话叫“延迟删除”比维护一个vis数组保险而且简洁。第二个哈夫曼合并。题目背景一般是“合并果子”每次选两堆最小的堆合并耗费等于两堆之和求最小总耗费。每次取最小、合并后放回去这种“动态取最小”恰好是优先队列的本职工作。如果脑子被“从小到大排序”占据一上来就先排序那就坏了——每次合并完的堆大小是新的仍需要重新挑选排序解法会退化到O(n² log n)而优先队列版本是O(n log n)。第三个对顶堆求动态中位数。维护一个大根堆放较小那一半和一个小根堆放较大那一半插入时先放到大根堆然后根据两边大小平衡调整中位数就是某一堆的堆顶。这个应用很能展示“两个队列配合”的设计思路也是区分“会背模板”和“真正理解优先级”的标志性题目。5.2 排序规则的那些坑priority_queue的自定义排序是比赛里出问题最多的地方之一很多人一写就错。C的priority_queue默认是大根堆也就是top()返回最大元素。想改成小根堆模板参数是priority_queueint, vectorint, greaterint pq;如果是自定义结构体需要重载operator注意方向是反的struct Node { int dist, id; bool operator(const Node other) const { return dist other.dist; // 越小优先级越高 } };为什么是小根堆却要重载大于号因为priority_queue的底层堆排序规则是“等价于默认大根堆”它通过operator判断两个元素的优先级a排在b前面当且仅当a b为true。堆顶是“认为最大的元素”。你希望dist最小的在堆顶那就要让“dist更小的元素”被视为更大的那个因此operator里用反而让dist小的认为自己比较大。我第一次接触这个逻辑时也绕了很久把它理解为“reverse sort 的比较器”就行。另外如果你要在priority_queue里存pair记住pair本身自带字典序比较所以priority_queuepairint,int, vectorpairint,int, greaterpairint,int就是按first升序、再按second升序的小根堆。这正好满足Dijkstra的需求。6. 常见问题与调试技巧实录队列相关的题目看着简单实际写起来翻车点挺多。我把自己在训练中遇到的经典问题整理成一个速查表方便自查。现象可能原因解决方法队列里出现重复元素标记dist/vis的时机不对入队时立刻标记不要等出队时再标记结果与样例一致但提交TLE用了STL queue但状态量极大换手写数组队列减少常数开销滑动窗口最大值错两三个弹出队尾用了而不是重复值时弹出旧元素保留新元素多组测试结果串数据queue没有清空q queue ()或swap空队列Dijkstra结果部分正确没有跳过过期堆节点出队时判断d ! dist[u]则continue01BFS结果偏大用了普通queue换成deque0权时push_front手写队列访问越界数组开小了或tail一直增长开2倍空间或改用循环队列除了这些有两个调试技巧值得分享。第一个是打印队列调试法。当BFS结果不对时很多人喜欢盯代码干瞪眼其实效率很低。我的习惯是写一个debug输出比如手写队列时直接遍历head..tail区间打印队列内容或者STL queue时临时用queue的副本弹出打印。看一眼队列里的元素顺序变化就能判断是不是标记时机错了、是不是状态生成错了。第二个是构造边界数据。比如窗口大小为1或者kn的滑动窗口、只有1个点或没有边的图、起点和终点相同的题。这些极端情况最容易暴露空指针和越界问题而且往往是样例没有覆盖的。竞赛题的测试点设计就是喜欢卡这些边界自己提前测一遍能省很多罚时。7. 训练路线与最后一点心得队列这个知识点最大的特点是入门容易精通难。你可以用一个下午学会BFS模板但把单调队列、01BFS、双向BFS、对顶堆这些小套路全部吃透前后需要刷几十道题去喂。我建议按这个路线推进第一阶段手写数组队列把BFS在网格图上的题刷明白比如迷宫最短步数、岛屿数量第二阶段学多源BFS和双向BFS找几道字符串变换题练状态编码和判重第三阶段学单调队列先用滑动窗口刷熟再做区间最值和DP优化题第四阶段学01BFS重点对比“为什么普通BFS失败”和“为什么deque能保持距离单调”第五阶段学优先队列应用从Dijkstra到哈夫曼从对顶堆到贪心选最大/最小我个人带过几届训练队见到最多的情况是模板题能过变形题懵。原因是大家只背了“怎么写队列、怎么调deque”没有建立“在什么场景下为什么用队列”的思维。数据结构从来不是目的它是你表达算法思想的工具。当你看到一道题能迅速判断“这个状态转移需要先进先出”或者“这个是动态最值”那对队列的领悟才算真正到位。最后说一个我自己写了多年代码才养成的习惯任何queue、deque、priority_queue的代码写完先检查所有操作是否都在非空状态下进行。front()、pop()、top()在容器为空时都是未定义行为本地可能侥幸跑通评测机上直接RE。这个习惯比任何debug技巧都管用希望你能一开始就养成。

算法竞赛中的队列：BFS、单调队列与优先队列实战指南

相关推荐

队列竞赛实战指南：从手写循环队列到BFS与单调队列

内存碎片整理实战：从原理到自建内存池方案

DeepSeek学Python全攻略：AI辅助编程学习的八周实战方案

更多资讯

从无标题文档到正式发布：先定内核再取标题的创作流程

斯纳克图书馆管理系统PHP版v6.0实战部署与优化指南

易支付运营版源码部署与支付通道轮询、投诉进件实战解析

基于调频能力裕度的风电场一次调频策略解析

HDFS存储优化实战：纠删码、压缩与小文件治理策略

Oracle 12c SQL查询实战：从v$session到AWR追溯历史执行记录

今日更新

交通拥堵预测毕设：基于Python+LSTM的车辆流量预测系统全流程解析

MATLAB/Simulink搭建10机39节点电力系统暂态稳定仿真实战

无人机航拍三维重建全流程：从SfM到网格生成的避坑指南

本周精选

交通拥堵预测毕设：基于Python+LSTM的车辆流量预测系统全流程解析

MATLAB/Simulink搭建10机39节点电力系统暂态稳定仿真实战

无人机航拍三维重建全流程：从SfM到网格生成的避坑指南

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？