OI-wiki 队列（Queue）数据结构全解：数组模拟、双栈模拟、STL 容器与特殊队列-平芜编程栈

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 { stack<int> 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::queue

C++ 在 STL 中提供了容器std::queue，使用前需要先引入<queue>头文件。其定义如下：

// clang-format off template< class T, class Container = std::deque<T> > class queue;

T：queue 中要存储的数据类型；
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::queue<int> q1, q2; // 向 q1 的队尾插入 1 q1.push(1); // 将 q1 赋值给 q2 q2 = q1; // 输出 q2 的队首元素 std::cout << q2.front() << std::endl; // 输出: 1

特殊队列：双端队列

双端队列（deque，double-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 以减少空间常数 stack<int, vector<int>> 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() { // 平衡中需要辅助栈实现栈内元素倒置 stack<int, vector<int>> 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); vector<Deque> 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; }

这份实现中的细节值得品味：

stack<int, vector<int>>显式指定底层容器：std::stack默认以std::deque为底层容器，而双端队列场景下本就以栈为核心，改为vector可以减少空间常数，注释中也明确说明了这一动机；
balance()借助辅助栈t完成倒置：将非空栈的前一半元素经t倒置后放入空栈，再交换两栈角色，从而保证任意时刻f（队尾侧）与s（队首侧）栈顶分别对应真实队尾与队首；
多队列支持：主函数用vector<Deque> q(M)一次性维护大量独立双端队列，通过编号a定位，对应题目多队列的操作形态；
配套测试数据 queue_3.in 与 queue_3.ans 覆盖了push_back、push_front、pop_back、size、front、back等混合操作序列，可用于直接验证实现的正确性。

C++ STL 中的 std::deque

C++ 在 STL 中也提供了容器std::deque，使用前需要先引入<deque>头文件。其定义如下：

// clang-format off template< class T, class Allocator = std::allocator<T> > class deque;

T：deque 中要存储的数据类型；
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)$	固定数组复用	空间受限且需要复用数组的场景