队列竞赛实战指南：从手写循环队列到BFS与单调队列-北京尧图网络

队列这个数据结构在算法竞赛里属于那种看着简单考起来花活最多的类型。FIFO、先进先出、排队模型——说起来人人都能理解但真上场做题BFS 需要队列滑动窗口最大值需要单调队列拓扑排序需要队列做事件模拟恨不得一个队列同时处理十种情况。很多同学以为 queue 就是 STL 里一个现成容器背会 push 和 pop 就万事大吉结果遇到手写队列的性能瓶颈、循环队列判空判满的边界、双端队列的灵活取用才发现自己的队列理解还停留在表面。这篇文章从竞赛实战角度出发把队列从底层实现到高频算法组合完整梳理一遍既适合刚开队列专题的新手也适合想系统性复盘队列套路的选手。我会把代码、原理、踩坑经验全部摆出来尽量讲清楚每一步为什么这么做。1. 队列到底解决了什么问题从排队模型到竞赛考点1.1 FIFO 到底在说什么队列的核心思想就是先进先出英文叫 First In First Out简称 FIFO。你可以把它想成食堂打饭窗口前的那条队先来的人先打到饭后来的人只能排在队尾谁也不能插队。数据结构里入队操作叫 push出队操作叫 pop你只能从队头取出元素、从队尾放入元素不允许从中间任意存取。这种限制听起来很死板但它恰恰保证了处理的顺序和事情发生的先后顺序一致在很多场景里这就是最自然的处理方式。竞赛里为什么频繁用队列因为大量算法都是按照层或步的顺序推进的。比如走迷宫你在起点先走一步能到达的所有格子然后再从这些格子出发走第二步这样一层层扩散天然就需要一个容器能够按存入顺序依次取出待处理的节点。如果用栈后进先出扩散顺序就会变成一条路走到黑再回头那就不再对应广度的语义。可以说只要问题里出现了一轮一轮、一层一层、按先后顺序处理的提示队列基本就跑不掉。1.2 竞赛里队列的高频场景我按出现频率排一下队列在竞赛题中主要有四个用途。第一个是广度优先搜索BFS。最短步数、最少操作次数、迷宫最短路、多源扩散这些题几乎全是 BFS 的天下而 BFS 的辅助数据结构就是队列。第二个是滑动窗口类问题。给一个窗口在数组上滑问窗口内最大值或最小值经典解法是单调队列。第三个是拓扑排序。Kahn 算法用队列维护当前入度为 0 的节点这也是队列在图上的一种典型应用。第四个是模拟题。餐厅排队、进程调度、消息队列、回合制游戏这些题需要严格按照时间顺序处理事件队列和优先队列常常一起上场。上面这四个方向里前两个是必须熟练掌握的后两个虽然不如前两个硬核但模拟题在各类竞赛里从不缺席队列用得不熟很容易在实现细节上翻车。2. 队列的五种实现姿势从纯数组到 STL 容器2.1 纯数组队列的经典写法很多教材教队列都是从链表入手的但竞赛里我几乎没见过谁用链表写队列。原因很简单链表每个节点都要动态分配慢且容易出错。更常见的做法是直接用数组加两个下标一个指向队头 head一个指向队尾 tail像这样const int MAXQ 1000005; int q[MAXQ]; int head 0, tail 0; void push(int x) { q[tail] x; } int front() { return q[head]; } void pop() { head; } bool empty() { return head tail; }这个写法的原理是把数组当成一段连续内存push 时在 tail 位置写入元素并让 tail 后移pop 时直接让 head 后移认为 head 之前的空间已经作废。代码非常简洁速度也很快。但它有一个致命问题head 和 tail 一直在往后走被 pop 过的空间永远不会再被使用一个大小为 N 的数组最多只能容纳 N 次入队操作之后 tail 就越界了。也就是说如果题目数据量不大或者队列总元素数不超过你开的空间这个写法是可以用的。但一旦你的程序要处理几十万次 push同时又有大量 pop这个数组就会很快被耗光。这是初学者最容易踩的坑。2.2 循环队列让空间真正复用要解决数组空间被浪费的问题最经典的做法是循环队列。思路是把数组的尾部和头部在逻辑上接起来tail 到达数组末尾时取模回到开头const int MAXQ 1000005; int q[MAXQ]; int head 0, tail 0; void push(int x) { q[tail] x; tail (tail 1) % MAXQ; } void pop() { head (head 1) % MAXQ; } bool empty() { return head tail; } bool full() { return (tail 1) % MAXQ head; }这里有个非常关键的细节如果用 head tail 表示空那么当队列装满时 head 也会等于 tail这就和空状态冲突了。所以循环队列普遍采用牺牲一个空间的做法让队尾最多走到 head 前一个位置也就是最多存 MAXQ - 1 个元素通过 full() 来单独判断满。这样做虽然浪费了一个单位空间却换来极其干净的边界判断逻辑非常划算。我在实际做题时一般不会在普通 BFS 里手写循环队列因为 STL 的 queue 和 deque 在绝大多数题目里速度已经足够。但如果你碰到那种对常数特别敏感的题目比如上百万状态的搜索手写循环队列能省掉不少动态扩容和封装的开销此时 array 版循环队列是最稳的。2.3 std::queue 的注意事项STL 的 std::queue 是竞赛中最常用的队列实现它默认底层容器是 deque本质上是对双端队列做了一个只让从队尾进、队头出的封装。基本用法是#include queue queueint q; q.push(10); q.push(20); int x q.front(); // 10 q.pop(); bool empty q.empty(); size_t sz q.size();用的时候有两点需要注意。第一pop 不返回被弹出的元素你在 C 里要是写 int x q.pop()编译直接报错。想拿元素得先 q.front() 再把 q.pop() 连起来写。第二调用 front() 或 pop() 之前必须确认队列非空空队列上做这两个操作是未定义行为在本地可能什么都不发生在评测机上可能直接 RE。我见过太多人在 while (!q.empty()) 的条件里漏写了空判断结果调试半天。还有一点关于性能std::queue 在千万级操作量下依然能跑但如果你的题目要求多组测试数据、每组都有大量入队出队频繁构造和析构 queue 对象也有一点开销。一个常用的优化是在每组数据开始时新建一个空的 queue而不是把同一个 queue 里的元素慢慢 pop 完。前者干脆利落后者有可能残留元素影响下一组答案。2.4 手写 vs STL怎么选我总结一下自己的选择逻辑默认用 std::queue它代码可读性好、出 bug 概率低当你确定它成为性能瓶颈时替换成手写数组队列循环队列只在需要严格控制空间复用、或者题目本身就是队列模拟且需要频繁清空操作时才专门使用。有些老选手会硬编码一个非常大的数组队列然后所有题目都用手写版本理由是稳定、快。这也没问题但代价是每次都要多写几个函数。我的建议是把一套手写队列模板存在自己的代码模板里比赛时看情况直接贴。模板不需要花哨就那 20 行能解决大部分问题。3. 单调队列滑动窗口问题的杀手锏3.1 单调队列在维护什么单调队列并不是一个新的数据结构它是在队列的基础上额外维护了内部元素的单调性。以滑动窗口最大值来举例我们维护一个从队头到队尾单调递减的队列队头永远是当前窗口的最大值。当新元素入队时先把队尾所有比它小的元素弹出因为它比它们更大、又比它们更晚过期所以那些小的旧元素在它存在期间永远不可能是最大值留在队列里只会碍事。然后新元素从队尾入队。窗口滑动时队头元素如果已经滑出窗口范围就直接弹掉。这里有一个重要经验单调队列里存的不是元素值而是元素在数组中的下标。节省空间只是其次更关键是只有存下标你才能判断一个元素是否已经滑出窗口。只存值的话你无法知道它什么时候过期。代码实现用 std::deque 最自然因为滑动窗口既要处理队头过期又要从队尾弹出比新元素小的值这涉及双端操作普通 queue 做不到#include bits/stdc.h using namespace std; int n, k; int a[1000005]; dequeint dq; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin n k; for (int i 0; i n; i) cin a[i]; // 维护单调递减队列队头是窗口最大值 for (int i 0; 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 - 1) cout a[dq.front()] ; } return 0; }3.2 为什么复杂度是 O(n)很多新手看不懂为什么每个元素只被弹出一次复杂度就能到 O(n)。理由其实很简单窗口滑过每一个下标时这个下标最多被 push 一次也最多被 pop 一次无论是从队头过期弹出还是从队尾被更大元素淘汰。总体来看 n 个元素各进出一次均摊复杂度 O(1)总复杂度 O(n)。对比暴力法的 O(nk)数据量一大就立刻体现出优势。我一开始写单调队列时最别扭的就是从队尾弹出这一步。常规队列里不允许弹出队尾但单调队列借助了 deque 的能力队尾既可以入也可以出。你要理解它本质上是一个带淘汰机制的滑动窗口而不是标准的 FIFO 队列。当你把它想成一个时刻保持有序的候选集就顺了。3.3 单调队列的其他应用滑动窗口最值只是单调队列最入门的用法。它还能配合 DP 优化比如形如 dp[i] max(dp[j] cost(j))其中 j 的取值范围是一个不断滑动的区间这时就可以用单调队列把 DP 转移从 O(n^2) 优化到 O(n)。这种优化在动态规划题里经常出现算是单调队列的进阶考法。初学者先把滑动窗口最值吃透再碰到转移式里出现区间的 max/min就能条件反射地想起单调队列。写单调队列还有一个细节多组测试数据时每组数据开始前要清空 deque。有些人习惯复用同一个 deque不清空就直接跑第二次窗口会混入上一组的残留下标答案乱七八糟。最稳妥的方式是每组数据新建一个 deque或者 dq.clear() 一下。4. 队列在竞赛中的经典组合拳BFS、拓扑排序与模拟4.1 BFS 层序遍历与最短步数BFS 的核心逻辑先用代码摆出来queueint q; vectorint dist(n 1, -1); dist[s] 0; q.push(s); while (!q.empty()) { int u q.front(); q.pop(); for (int v : e[u]) { if (dist[v] -1) { dist[v] dist[u] 1; q.push(v); } } }这里有三个关键点。第一dist[v] 初始化为 -1 表示未访问同时它又能直接当距离数组用。第二在把节点推入队列时就要立刻标记 dist[v]而不是等它弹出队列后再标记否则同一个节点可能被多个父节点重复入队既浪费时间又可能让距离更新出问题。第三每次从队列取出节点时它的距离就是最短距离因为 BFS 是按层扩展的第一次访问到这个节点时入队顺序保证步数最少。我在刚练 BFS 时犯过一个典型错误把 vis 标记写在弹出节点之后。结果一个格子被四个邻居各推入一次队列里塞了一堆重复状态虽然答案碰巧对了但数据一大就超时。这个教训值得反复强调——标记状态一定要在入队时完成。4.2 拓扑排序入度为 0 的流动处理拓扑排序的 Kahn 算法也是队列的经典表演。算法思路是不断找出当前入度为 0 的节点把它输出然后删除它所有出边每删除一条边就把目标节点的入度减 1如果目标节点的入度变成 0就加入队列继续处理queueint q; vectorint order; for (int i 1; i n; i) { if (indeg[i] 0) q.push(i); } while (!q.empty()) { int u q.front(); q.pop(); order.push_back(u); for (int v : g[u]) { indeg[v]--; if (indeg[v] 0) q.push(v); } } if ((int)order.size() ! n) { // 存在环无法完成拓扑排序 }这里有一个容易忽略的细节一个节点的入度可能在多个环节中被慢慢消减它只会在入度恰好减到 0 的那一刻入队且只会入队一次。所以不需要额外的访问数组。还有一个常见用法当题目要求输出字典序最小的拓扑序时把普通队列换成小根堆即可也就是优先队列。这个变体在拓扑相关的模拟题里很常见比如安排课程、处理依赖关系要求同等条件下优先处理编号小的任务。从 queue 到 priority_queue 的切换也就一行代码的事但对答案顺序影响很大。4.3 事件模拟时间的天然推进器模拟题里最考验队列功底的是时间片类的题目。比如一条生产线上同时有多个任务每个任务需要不同的处理时间完成时间早的先出结果。这种题表面上是队列但只要任务之间不是严格的先到先服务就要把普通队列换成优先队列以结束时间做键值。我举个例子假设系统初始有 n 个任务每个任务有个提交时间和一个处理耗时处理器同一时刻只能做一件事每次从所有已提交未处理的任务里选最短的来做问每个任务的完成时间。这种问题如果不理解优先队列就只能暴力扫复杂度 O(n^2)。正确姿势是每次处理完当前任务后把所有已提交任务依次入堆每次取耗时最短的。这里当前时间不断跳跃队列的入队时机也是动态的非常考验对时间轴的理解。普通队列在这种模拟里的作用也很明确维护按提交顺序排队的任务。如果题目强调先来先服务那普通队列就够了。如果强调优先处理某个属性那优先队列是主角。两者经常组合使用先按提交顺序入普通队列再按优先级入优先队列两个队列互相配合。5. 双端队列与优先队列queue 家族的另外两员5.1 deque 的左右开弓双端队列 deque 支持在头部和尾部都能插入、弹出相当于把栈和队列的能力合二为一。它最基本的操作包括 push_back、push_front、pop_back、pop_front、front、back。单看这些接口deque 就是 STL 里最灵活的线性容器之一。竞赛里 deque 最常见的使用场景有三个。第一个就是上面提到的单调队列它需要从队尾弹出元素这是普通 queue 给不了的。第二个是 BFS 求 0-1 最短路边权只有 0 和 1 时可以把边权为 0 的节点插入队头边权为 1 的节点插入队尾这样双端队列 BFS 依然能保证节点按距离升序处理复杂度 O(n)。第三个是回文相关的模拟题比如两端轮流取数deque 比数组自己去维护 head 和 tail 直观得多。需要提醒的是deque 并不是完全没有代价的。它内部通常是分段存储下标访问比数组慢一点迭代器也不是普通指针。但在竞赛题目范围内这些差异几乎可以忽略。你完全不用在效率上纠结优先考虑代码的正确和清晰。5.2 优先队列不只是会排序的队优先队列 priority_queue 在 C 里默认是大根堆也就是队头永远是最大元素。想用最小堆要写这样一行priority_queueint, vectorint, greaterint pq;如果你存的是自定义结构体想按某个字段排序可以用自定义比较器struct Node { int t, w; }; struct cmp { bool operator()(const Node a, const Node b) { return a.t b.t; // 小顶堆t 小的优先 } }; priority_queueNode, vectorNode, cmp pq;注意这里的比较函数语义和 sort 里的比较函数是反过来的。在 sort 里return a.t b.t 表示从小到大排在 priority_queue 里return a.t b.t 才让堆顶是 t 最小的。这个反向是 C 新手最喜欢踩的坑我第一次用自定义比较器时也在这里翻过车调试了半天才意识到两个地方符号习惯相反。优先队列在竞赛里经常扮演贪心队列的角色。比如合并果子每次取两堆最小的合并再把合并结果放回堆里循环 n - 1 次这就是堆贪心的经典组合。再比如 Dijkstra 最短路算法用优先队列维护当前距离最小的节点从而保证每次扩展都是最优的。可以说优先队列是每次都要从候选集中取最值这一类问题的统一答案。6. 实战避坑指南队列题最容易犯的错和调试技巧6.1 高频错误速查表我把这些年遇到的队列相关错误整理成一张表你在自查时可以对照着看。错误类型具体现象根本原因解决办法空队列访问本地正常评测 RE没判断 empty 就调用 front/pop访问前检查 while (!q.empty())标记时机错误BFS 节点重复入队超时vis 写在弹出后而非入队时在 push 时立即标记 dist/vis循环队列满空混淆数据丢失或死循环head tail 同时表示空和满牺牲一格空间用 full() 判断多组数据未清空第二组答案混入旧数据复用 queue/deque 未清空每组数据重新定义容器或调用 clear优先队列比较方向反堆顶取错元素自定义比较器符号写反记住堆顶是 cmp 眼中的最小值单调队列存值不存下标过期元素无法删除不知道元素在窗口内还是窗口外队列里存下标比较时用数组值数组队列空间不足无符号数字越界变负数head/tail 一直增加不回收改循环队列或换 STL这张表里的每一条我基本都亲手踩过。最气人的是空队列访问本地开 debug 的时候能正常运行一交上去就是 RE因为评测环境里对未定义行为的处理方式不同。养成写任何队列处理前都检查 empty 的习惯能少浪费大量调试时间。6.2 几个实用的调试技巧队列题的调试我常用的技巧有三个。第一个是打印队列状态。在关键位置输出当前 head、tail 或者 STL queue 的 size看看入队出队是否按预期进行。特别是滑动窗口题把每一步的队列下标和对应值都打印出来很容易看出什么时候过期判断写错了。第二个是小数据暴力对拍。写一个 O(n^2) 的暴力版本再和你的单调队列版本同时对一个小数组跑随机生成几十组数据逐一比对输出。这个方法看起来笨但对队列这种边界问题多的题型特别有效。我不止一次靠对拍找出窗口还没滑满就开始输出这种细节错误。第三个是检查下标的闭开区间。滑动窗口的下标范围通常是 [i - k 1, i]过期条件是 dq.front() i - k 1写成 i - k 也行但思路要统一。我习惯统一写成队头下标小于窗口左端点就弹出避免每次临时推公式。6.3 输入输出与性能的隐藏约束队列题如果数据量大输入输出也可能成为瓶颈。千万级别的 n用 cin 默认同步模式会明显拖慢速度。我一般在所有需要大量读入的题目开头写上ios::sync_with_stdio(false); cin.tie(nullptr);这两行的作用是关闭 C 标准流和 C 标准 IO 的同步绑定以及取消 cin 和 cout 的自动 flush能显著提升输入效率。需要注意的是如果输入里有混合使用 cin 和 scanf 的情况关闭同步之后可能会出问题所以要么统一用 scanf/printf要么统一用 cin/cout不要混着来。另外C 标准里并没有规定 std::queue 底层一定用 deque不同编译器可能有差异。竞赛环境一般用 GNU 系列的 STL默认是 deque如果你非常担心底层开销也可以显式写成 queueint, list 但在实际竞赛里几乎没人这么干默认就好。6.4 最后再分享一个小经验队列相关题目只要题型识别正确实现难度通常不高真正容易丢分的地方全在细节。我个人习惯在做每道队列题之前先问自己三个问题这个队列存的是值还是下标什么时候需要判断空多组测试数据下容器怎么重置这三个问题想清楚代码写起来又快又稳。特别是单调队列存下标这个点我希望你读完这篇文章后就彻底记住——这会让你少走很多弯路。还有一点队列不是孤立的它经常要和其他数据结构配合。BFS 里可能配合哈希表压缩状态拓扑排序可能配合小根堆控制顺序事件模拟可能配合优先队列提高效率。所以你练习的时候不要把队列当成一个单独的知识点而是把它当成一套基础工具和别的算法灵活组合起来用。把这一步想通了你的队列水平才算是真正到达了竞赛需要的程度。

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

相关推荐

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

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

SCIP Python接口实战：从建模到性能调优的完整指南

更多资讯

基于YOLOv8的溺水检测告警系统：从环境搭建到部署避坑

英语作文批改工具，老师们现在都在用啥？

实例详解Python的进程,线程和协程

Paritok 成本测算指南：从 25% 到 85% 的省钱曲线，团队一年能省多少钱

滑块验证码识别的YOLO缺口检测实战：从数据合成到部署推理

仿贝壳房产系统源码二次开发：环境搭建、房源模块优化与权限设计

今日更新

交通拥堵预测毕设：基于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 成本测算与选型避坑（附配置）

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