OI-wiki 队列Queue数据结构全解数组模拟、双栈模拟、STL 容器与特殊队列【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki队列Queue是 OI / ICPC 竞赛中最基础的线性数据结构之一其「先进先出FIFO」性质是 BFS、拓扑排序、单调队列等经典算法的底层支撑。本文以 OI-wiki 仓库 的队列文档为主体结合仓库内三份可直接运行的参考实现queue_1.cpp、queue_2.cpp、queue_3.cpp与配套测试样例系统讲解队列的数组模拟、双栈模拟、std::queue/std::deque等 STL 容器用法、双端队列的均摊复杂度证明以及循环队列解决「假溢出」的原理读完即可在竞赛和工程场景中灵活选用合适的队列实现。队列的基本概念队列queue是一种具有「先进入队列的元素一定先出队列」性质的表。由于该性质队列通常也被称为先进先出first in first out表简称FIFO 表。与栈后进先出 LIFO恰好相反队列的插入操作入队只发生在队尾rear删除与访问操作出队/查看队首只发生在队首front。这种两端分工、单向流动的约束使得队列天然适合模拟排队等待类问题先到的先服务、后到的排在后面。注意FIFO 描述的是「当前容器内」元素的进出次序。与 栈 文档中强调的 LIFO 语义一样判断一个数据结构是 FIFO 还是 LIFO应当基于容器内部当下的元素状态而非整体进出序列。实现一数组模拟队列最朴素也最高效的实现方式是用一个数组加上两个下标变量来标记队首与队尾int q[SIZE], ql 1, qr;其中ql指向队首元素下标qr指向队尾元素下标初始为 0表示空队列。对应的五种基本操作如下插入元素入队q[qr] x;删除元素出队ql;访问队首q[ql]访问队尾q[qr]清空队列ql 1; qr 0;仓库参考实现仓库在 docs/ds/code/queue/queue_1.cpp 中给出了针对「Luogu B3616【模板】队列」的完整可运行实现用结构体封装了队列的全部操作#include cstdio using namespace std; const int SIZE 10000 5; struct Queue { int q[SIZE], ql, qr; Queue() : ql(1), qr(0) {} bool empty() { return ql qr; } void push(int x) { q[qr] x; } void pop() { ql; } int front() { return q[ql]; } int back() { return q[qr]; } int size() { return qr - ql 1; } int clear() { ql 1; qr 0; } }; int main() { Queue q; int n; scanf(%d, n); while (n--) { int opt; scanf(%d, opt); if (opt 1) { int x; scanf(%d, x); q.push(x); } else if (opt 2) { if (q.empty()) printf(ERR_CANNOT_POP\n); else q.pop(); } else if (opt 3) { if (q.empty()) printf(ERR_CANNOT_QUERY\n); else printf(%d\n, q.front()); } else printf(%d\n, q.size()); } return 0; }这份实现有几个值得借鉴的工程细节empty()用ql qr判断队列中元素个数为qr - ql 1当ql qr时个数为负即队列为空与「初始时ql 1, qr 0」的约定自洽越界保护出队opt 2与查询队首opt 3前都先调用empty()检查空队列下输出ERR_CANNOT_POP/ERR_CANNOT_QUERY而非访问无效下标避免运行时错误size()为常数时间qr - ql 1直接由两个下标相减得到无需遍历。仓库对应的测试数据 queue_1.in 与期望输出 queue_1.ans 覆盖了入队、出队、查队首、查大小以及空队列报错等全部分支例如当队列为空时执行查询会输出ERR_CANNOT_QUERY执行出队会输出ERR_CANNOT_POP验证了上述越界保护逻辑的正确性。实现二双栈模拟队列另一种相对冷门但非常巧妙的思路是使用两个栈来模拟一个队列仓库参考实现位于 docs/ds/code/queue/queue_2.cpp。相关栈的基础知识可参考 栈。方法使用两个栈 $F$ 和 $S$$F$ 是队尾方向的栈负责承接新插入的元素$S$ 代表队首方向的栈负责弹出与读取队首。两个栈合起来模拟一个完整的队列支持 push队尾插入与 pop队首弹出push直接插入到栈 $F$ 中pop如果 $S$ 非空直接让 $S$ 弹栈否则先把 $F$ 中的元素一个一个弹出并压入 $S$完成后 $S$ 中的元素顺序相对 $F$ 是首尾颠倒的此时 $S$ 栈顶恰为原队列的队首再让 $S$ 弹栈。#include cstdio #include stack using namespace std; struct Queue { stackint f, s; bool empty() { return f.empty() s.empty(); } void push(int x) { f.push(x); } void pop() { if (s.empty()) for (; !f.empty(); f.pop()) s.push(f.top()); s.pop(); } int front() { if (s.empty()) for (; !f.empty(); f.pop()) s.push(f.top()); return s.top(); } int size() { return f.size() s.size(); } }; int main() { Queue q; int n; scanf(%d, n); while (n--) { int opt; scanf(%d, opt); if (opt 1) { int x; scanf(%d, x); q.push(x); } else if (opt 2) { if (q.empty()) printf(ERR_CANNOT_POP\n); else q.pop(); } else if (opt 3) { if (q.empty()) printf(ERR_CANNOT_QUERY\n); else printf(%d\n, q.front()); } else printf(%d\n, q.size()); } return 0; }均摊复杂度分析每个元素在整个生命周期中只会经历三种操作各一次进入$F$push 时、转移从 $F$ 弹出压入 $S$仅在 $S$ 为空时成批发生、弹出从 $S$ 出栈。因此单次 pop 的最坏复杂度是 $O(n)$一次性倾倒整个 $F$但把一系列操作放在一起看每个元素恰好只被转移一次总的转移代价被所有操作均摊均摊复杂度为 $O(1)$。这也是「双栈模拟队列」能用于竞赛题的关键虽然存在单次操作峰值但整体摊还下来与数组模拟一样是常数时间且代码量只依赖std::stack非常适合在禁止使用 STL 容器queue或想展示数据结构本质时使用。C STL 中的队列std::queueC 在 STL 中提供了容器std::queue使用前需要先引入queue头文件。其定义如下// clang-format off template class T, class Container std::dequeT class queue;Tqueue 中要存储的数据类型Container用于存储元素的底层容器类型。这个容器必须提供通常语义的下列函数back()front()push_back()pop_front()STL 容器std::deque和std::list满足这些要求。如果不指定则默认使用std::deque作为底层容器——这正说明std::queue是一个容器适配器container adapter它本身不存储数据而是把底层容器的接口重新包装成只能队尾进、队首出的受限接口。常用成员函数STL 中的queue容器提供了一众成员函数常用的有元素访问q.front()返回队首元素q.back()返回队尾元素修改q.push()在队尾插入元素q.pop()弹出队首元素容量q.empty()队列是否为空q.size()返回队列中元素的数量运算符queue还提供了一些运算符最常用的是用赋值运算符为queue赋值完成底层容器的整体拷贝std::queueint q1, q2; // 向 q1 的队尾插入 1 q1.push(1); // 将 q1 赋值给 q2 q2 q1; // 输出 q2 的队首元素 std::cout q2.front() std::endl; // 输出: 1特殊队列双端队列双端队列dequedouble-ended queue是指可以在队首/队尾两个方向插入或删除元素的队列相当于栈与队列功能的结合。具体地双端队列支持 4 个操作在队首插入一个元素在队尾插入一个元素在队首删除一个元素在队尾删除一个元素数组模拟双端队列的方式与普通队列相同——只需再维护一个队首下标支持向前的移动即可。同样地也可以把「双栈模拟队列」的思想推广来维护双端队列但需要注意一个关键陷阱当某个栈为空时交替查询队首和队尾将导致均摊分析失效。考虑在移动元素时只将非空栈的一半元素移动到空栈中并始终保持队首栈与队尾栈的性质这样处理后仍可以做到均摊常数时间的插入和删除。均摊复杂度证明由于插入操作只贡献常数复杂度现在考虑弹出操作。假设初始时队列中有 $m$ 个元素计算将所有元素全部弹出无论首尾的时间复杂度第一次平衡的复杂度是 $O(m)$ 的之后两个栈就各有 $\frac{m}{2}$ 个元素。这时需要 $O(\frac{m}{2})$ 的时间清空其中一个栈随后又可以触发一次复杂度为 $O(\frac{m}{2})$ 的平衡操作以此类推直到所有元素被弹出。因此总复杂度满足递推$$ T(m)T\left(\frac{m}{2}\right)O(m) $$根据主定理解得 $T(m)O(m)$。于是这种维护方式的总复杂度仍是均摊常数的——每次只搬移一半元素代价以几何级数衰减是典型的均摊分析挽救最坏情况的范例。仓库参考实现仓库在 docs/ds/code/queue/queue_3.cpp 中给出了针对「Luogu B3656【模板】双端队列 1」的完整实现其中balance()函数正体现了每次只搬移一半元素的平衡策略#include iostream #include stack #include vector using namespace std; const int M 1000000 5; struct Deque { // 将 stack 的底层容器从 deque 换为 vector 以减少空间常数 stackint, vectorint f, s; bool empty() { return f.empty() s.empty(); } void push_back(int x) { f.push(x); } void push_front(int x) { s.push(x); } void balance() { // 平衡中需要辅助栈实现栈内元素倒置 stackint, vectorint t; if (s.empty()) { int n f.size() / 2; for (; f.size() n; f.pop()) t.push(f.top()); for (; !t.empty(); t.pop()) s.push(t.top()); for (; !f.empty(); f.pop()) t.push(f.top()); f.swap(t); if (!f.empty()) s.swap(f); } else if (f.empty()) { int n s.size() / 2; for (; s.size() n; s.pop()) t.push(s.top()); for (; !t.empty(); t.pop()) f.push(t.top()); for (; !s.empty(); s.pop()) t.push(s.top()); s.swap(t); if (!s.empty()) f.swap(s); } } void pop_front() { if (s.empty()) balance(); s.pop(); } void pop_back() { if (f.empty()) balance(); f.pop(); } int front() { if (s.empty()) balance(); return s.top(); } int back() { if (f.empty()) balance(); return f.top(); } int size() { return f.size() s.size(); } }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); vectorDeque q(M); int n; cin n; while (n--) { string opt; int a; cin opt a; if (opt push_back) { int x; cin x; q[a].push_back(x); } else if (opt pop_back) { if (!q[a].empty()) q[a].pop_back(); } else if (opt push_front) { int x; cin x; q[a].push_front(x); } else if (opt pop_front) { if (!q[a].empty()) q[a].pop_front(); } else if (opt size) cout q[a].size() \n; else if (opt front) { if (!q[a].empty()) cout q[a].front() \n; } else { if (!q[a].empty()) cout q[a].back() \n; } } return 0; }这份实现中的细节值得品味stackint, vectorint显式指定底层容器std::stack默认以std::deque为底层容器而双端队列场景下本就以栈为核心改为vector可以减少空间常数注释中也明确说明了这一动机balance()借助辅助栈t完成倒置将非空栈的前一半元素经t倒置后放入空栈再交换两栈角色从而保证任意时刻f队尾侧与s队首侧栈顶分别对应真实队尾与队首多队列支持主函数用vectorDeque q(M)一次性维护大量独立双端队列通过编号a定位对应题目多队列的操作形态配套测试数据 queue_3.in 与 queue_3.ans 覆盖了push_back、push_front、pop_back、size、front、back等混合操作序列可用于直接验证实现的正确性。C STL 中的 std::dequeC 在 STL 中也提供了容器std::deque使用前需要先引入deque头文件。其定义如下// clang-format off template class T, class Allocator std::allocatorT class deque;Tdeque 中要存储的数据类型Allocator分配器此处不做过多说明一般保持默认即可。deque的常用成员函数如下元素访问q.front()返回队首元素q.back()返回队尾元素修改q.push_back()在队尾插入元素q.pop_back()弹出队尾元素q.push_front()在队首插入元素q.pop_front()弹出队首元素q.insert()在指定位置前插入元素传入迭代器和元素q.erase()删除指定位置的元素传入迭代器容量q.empty()队列是否为空q.size()返回队列中元素的数量deque还提供了一些运算符较为常用的有使用赋值运算符为deque赋值类似queue使用[]访问元素类似vector注意其随机访问是 $O(1)$ 的但并非像vector那样保证元素连续存储。另外queue头文件中还提供了优先队列std::priority_queue因其与 堆 更为相似这里不作过多介绍。在 OI 中如果需要按优先级出队的数据结构应优先考虑优先队列 / 堆。Python 中的双端队列在 Python 中双端队列的容器由collections.deque提供。它同样支持两端 $O(1)$ 的插入与删除from collections import deque # 新建一个 deque并初始化内容为 [1, 2, 3] queue deque([1, 2, 3]) # 在队尾插入元素 4 queue.append(4) # 在队首插入元素 0 queue.appendleft(0) # 访问队列 # queue # deque([0, 1, 2, 3, 4])对应关系append/appendleft分别对应队尾、队首插入而pop/popleft则对应队尾、队首删除。相比 Python 内置的list在头部插入删除是 $O(n)$collections.deque是 Python 中实现 BFS、滑动窗口等需要双端操作算法的推荐容器。特殊队列循环队列使用数组模拟队列会导致一个问题随着时间推移整个队列会向数组的尾部移动一旦到达数组的最末端即使数组前端还有空闲位置再进行入队操作也会导致溢出——这种数组里实际有空闲位置而发生了上溢的现象被称为「假溢出」。解决假溢出的办法是采用循环的方式来组织存放队列元素的数组即将数组下标为 0 的位置看作最后一个位置的后继数组下标为x的元素它的后继为(x 1) % SIZE。这样就形成了循环队列入队时队尾下标前进到(qr 1) % SIZE出队时队首下标前进到(ql 1) % SIZE数组空间被首尾相接复用以循环利用只要队列长度不超过SIZE - 1通常留一个空位区分队空与队满就不会出现假溢出。循环队列是理解「数组下标取模管理环形缓冲区」的核心模型也是操作系统环形缓冲区、通信环形队列等工程场景的经典原型。总结与选择建议实现方式单次操作复杂度空间适用场景数组模拟队列$O(1)$$O(SIZE)$ 静态数组竞赛中最常用代码量最小双栈模拟队列均摊 $O(1)$两个栈仅用栈的场合模拟队列展示数据结构本质std::queue$O(1)$底层为 deque动态工程与竞赛通用封装完善std::deque/collections.deque双端 $O(1)$动态需要双端插入删除滑动窗口、BFS 双端扩展等循环队列$O(1)$固定数组复用空间受限且需要复用数组的场景队列是理解 BFS、拓扑排序、单调队列、宽度优先搜索等更高阶算法的地基。建议读者直接运行仓库中三份参考实现并对照 examples 目录 下的测试数据验证输出再动手实现一次循环队列即可彻底掌握队列的各类形态。参考资料std::queue - zh.cppreference.comstd::deque - zh.cppreference.com【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考