C++ STL 队列详解：queue 的使用、经典应用与简单模拟实现

C++ STL 队列详解：queue 的使用、经典应用与简单模拟实现

前言

生活中排队是一件很常见的事。

先到的人先接受服务，后到的人排在队尾等待。数据结构中的队列，也是按照类似的规则工作：

先进先出 First In First Out FIFO

C++ STL 提供了queue容器适配器，可以直接实现队尾入队、队头出队。

它的接口看起来很简单，但在算法和工程中使用非常广泛，例如：

• 广度优先搜索
• 二叉树层序遍历
• 任务调度
• 消息缓冲
• 请求排队
• 打印任务管理
• 生产者和消费者模型

本文从queue的基本接口开始，逐步讲解它的底层要求、典型应用、两个栈实现队列，以及一个简化版queue的模拟实现。

一、什么是队列？

队列是一种操作受限的线性数据结构。

假设依次执行：

push(1);push(2);push(3);

队列中的顺序是：

队头 -> 1 2 3 <- 队尾

执行一次pop()后，最先进入的1被删除：

队头 -> 2 3 <- 队尾

因此：

入队顺序：1 2 3 出队顺序：1 2 3

这就是先进先出。

二、queue 也是容器适配器

和stack一样，queue也不是一个独立的序列容器，而是容器适配器。

它通过封装底层容器，只提供符合队列规则的操作：

push()pop()front()back()empty()size()

队列需要从队尾插入，从队头删除，所以底层容器至少要支持：

front()back()push_back()pop_front()empty()size()

deque和list都能满足这些要求。

默认情况下：

std::queue<int>

近似于：

std::queue<int,std::deque<int>>

也可以指定list：

std::queue<int,std::list<int>>q;

普通vector不适合作为标准队列的底层容器，因为它没有pop_front()，在头部删除元素通常还要搬移后面的数据。

三、queue 的常用接口

使用队列需要包含：

#include<queue>

常见接口如下：

基本示例：

#include<iostream>#include<queue>usingnamespacestd;intmain(){queue<int>q;q.push(10);q.push(20);q.push(30);cout<<"队头："<<q.front()<<'\n';cout<<"队尾："<<q.back()<<'\n';cout<<"元素个数："<<q.size()<<'\n';q.pop();cout<<"出队后的队头："<<q.front()<<'\n';return0;}

运行结果：

队头：10 队尾：30 元素个数：3 出队后的队头：20

四、front 和 back 分别表示什么？

队列有两个重要位置：

front：队头 back ：队尾

例如：

队头 队尾 ↓ ↓ [10] [20] [30] [40]

调用：

q.front()

得到：

10

调用：

q.back()

得到：

40

新元素会从队尾加入：

q.push(50);

结果：

[10] [20] [30] [40] [50]

出队时删除的是队头：

q.pop();

结果：

[20] [30] [40] [50]

这两个方向不能混淆。

五、queue 的 pop 同样不返回元素

下面的写法是错误的：

intvalue=q.pop();

和栈一样，queue::pop()只负责删除元素，不返回被删除的值。

如果需要得到队头元素，应该先调用front()：

intvalue=q.front();q.pop();

完整写法：

if(!q.empty()){intvalue=q.front();q.pop();cout<<value<<'\n';}

六、如何遍历 queue？

queue没有提供：

begin()end()

也不能直接使用范围for遍历。

原因和stack相同：队列是容器适配器，只允许按照先进先出的规则访问元素。

如果允许任意访问中间位置，就破坏了队列的接口约束。

想按出队顺序查看队列，可以不断读取front()：

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

这会清空原队列。

如果想保留原队列，可以先复制：

queue<int>copy=q;while(!copy.empty()){cout<<copy.front()<<" ";copy.pop();}

七、队列和栈有什么区别？

栈和队列都属于操作受限的线性结构，但规则不同。

栈

后进先出 同一端插入和删除

示意：

push ↓ ┌───┐ │ 3 │ ← top / pop ├───┤ │ 2 │ ├───┤ │ 1 │ └───┘

队列

先进先出 队尾插入，队头删除

示意：

pop ← [1][2][3] ← push ↑ ↑ front back

八、经典应用：广度优先搜索

队列最典型的算法应用之一是广度优先搜索，也就是 BFS。

BFS 的特点是：

先处理距离起点较近的节点，再处理距离更远的节点。

假设图的连接关系如下：

0 -> 1, 2 1 -> 3 2 -> 4

从节点0开始：

1. 先把0入队；
2. 处理0，将1、2入队；
3. 接着处理1、2；
4. 再处理它们扩展出的3、4。

代码如下：

#include<iostream>#include<queue>#include<vector>usingnamespacestd;vector<int>bfs(constvector<vector<int>>&graph,intstart){vector<int>result;vector<bool>visited(graph.size(),false);queue<int>q;q.push(start);visited[start]=true;while(!q.empty()){intcurrent=q.front();q.pop();result.push_back(current);for(intnext:graph[current]){if(!visited[next]){visited[next]=true;q.push(next);}}}returnresult;}intmain(){vector<vector<int>>graph{{1,2},{3},{4},{},{}};vector<int>order=bfs(graph,0);for(intnode:order){cout<<node<<" ";}return0;}

输出：

0 1 2 3 4

队列保证先加入的相邻节点先被处理，因此搜索会一层一层向外扩展。

九、经典应用：二叉树层序遍历

层序遍历同样依赖队列。

基本过程是：

1. 根节点入队；
2. 取出队头节点；
3. 访问当前节点；
4. 将当前节点的左右孩子入队；
5. 重复以上过程。

代码如下：

#include<queue>#include<vector>usingnamespacestd;structTreeNode{intval;TreeNode*left;TreeNode*right;TreeNode(intvalue):val(value),left(nullptr),right(nullptr){}};vector<int>levelOrder(TreeNode*root){vector<int>result;if(root==nullptr){returnresult;}queue<TreeNode*>q;q.push(root);while(!q.empty()){TreeNode*current=q.front();q.pop();result.push_back(current->val);if(current->left!=nullptr){q.push(current->left);}if(current->right!=nullptr){q.push(current->right);}}returnresult;}

队列中的元素顺序始终与节点所在层次相对应，因此很适合层序遍历。

十、用两个栈实现队列

这是一个很经典的问题：

只能使用栈，怎样实现先进先出的队列？

可以准备两个栈：

_in ：负责入队 _out：负责出队

入队时直接压入_in：

push(1) push(2) push(3) _in 栈顶 3 2 1

出队时，如果_out为空，就把_in中的元素全部转移到_out：

_out 栈顶 1 2 3

这时_out的栈顶就是最早进入的元素1。

实现如下：

#include<cassert>#include<stack>usingnamespacestd;classMyQueue{public:voidpush(intvalue){_in.push(value);}intfront(){moveIfNeeded();assert(!_out.empty());return_out.top();}voidpop(){moveIfNeeded();assert(!_out.empty());_out.pop();}boolempty()const{return_in.empty()&&_out.empty();}private:voidmoveIfNeeded(){if(!_out.empty()){return;}while(!_in.empty()){_out.push(_in.top());_in.pop();}}private:stack<int>_in;stack<int>_out;};

这里不要每次出队都来回倒腾元素。

只有_out为空时，才把_in的元素转移过去。这样每个元素最多经历一次进入_in、一次转入_out和一次弹出。

十一、简单模拟实现 queue

队列需要底层容器支持：

队尾插入 队头删除 访问队头 访问队尾

因此不能直接使用普通vector实现高效队列。

如果用：

vector.erase(vector.begin());

删除队头后，后面的所有元素通常都需要向前移动，效率较低。

更合适的底层容器包括：

deque list

下面使用默认的deque进行简单封装：

#include<cassert>#include<cstddef>#include<deque>namespacebit{template<classT,classContainer=std::deque<T>>classqueue{public:queue()=default;voidpush(constT&value){_container.push_back(value);}voidpop(){assert(!_container.empty());_container.pop_front();}T&front(){assert(!_container.empty());return_container.front();}constT&front()const{assert(!_container.empty());return_container.front();}T&back(){assert(!_container.empty());return_container.back();}constT&back()const{assert(!_container.empty());return_container.back();}std::size_tsize()const{return_container.size();}boolempty()const{return_container.empty();}private:Container _container;};}

测试代码：

#include<iostream>intmain(){bit::queue<int>q;q.push(10);q.push(20);q.push(30);while(!q.empty()){std::cout<<q.front()<<" ";q.pop();}return0;}

输出：

10 20 30

接口对应关系非常清楚：

queue::push->container::push_back queue::pop->container::pop_front queue::front->container::front queue::back->container::back

十二、使用 list 作为底层容器

因为list支持高效头删和尾插，也可以用来封装队列：

#include<list>bit::queue<int,std::list<int>>q;

队列模拟实现本身不需要知道底层究竟是deque还是list。

只要底层容器具备需要的接口：

push_back()pop_front()front()back()size()empty()

队列适配器就可以正常工作。

这也是模板和容器适配器结合后的好处：上层数据结构依赖接口，而不是依赖某一种固定实现。

十三、为什么默认选择 deque？

queue需要在两端进行操作：

队尾插入 队头删除

vector的尾插很快，但头删通常需要搬移后续元素。

list的头删和尾插都很方便，但每个节点都要额外保存指针，内存布局也比较分散。

deque采用分段连续存储，具有几个适合队列的特点：

支持高效头插、头删 支持高效尾插、尾删 扩展时通常不需要整体搬移全部元素 空间利用率通常比链表更好

另一方面，queue本身不需要遍历，也不提供迭代器，因此deque复杂迭代器带来的遍历成本并不是主要问题。

可以说，deque的优点正好符合队列需要，而它的不足又基本不会暴露出来。

十四、queue 和 priority_queue 不一样

queue和priority_queue名字相似，但规则完全不同。

普通队列：

按照进入顺序出队 先进先出

优先队列：

按照优先级出队 默认最大元素优先

例如依次插入：

3 1 8 2

普通队列的队头是：

3

默认大堆优先队列的堆顶是：

8

因此，不要把queue和priority_queue当成同一种结构。

十五、常见错误整理

1. 对空队列调用 front、back 或 pop

错误：

queue<int>q;cout<<q.front();

应先判断：

if(!q.empty()){cout<<q.front();}

2. 认为 pop 会返回队头元素

错误：

intvalue=q.pop();

正确：

intvalue=q.front();q.pop();

3. 混淆 front 和 back

front：最早进入、即将出队的元素 back ：最后进入的元素

4. 使用 vector 频繁删除头部元素

下面这种实现可以工作，但效率通常不好：

v.erase(v.begin());

队列更适合使用deque或list。

5. BFS 中入队后才忘记标记

在图的 BFS 中，通常应该在节点入队时立即标记：

visited[next]=true;q.push(next);

如果等到出队时再标记，同一个节点可能被重复加入队列。

十六、queue 的常见使用场景

队列适合处理“先到先处理”或者“按层扩展”的问题，例如：

广度优先搜索 二叉树层序遍历 任务调度 消息队列 网络请求缓冲 打印任务 事件循环 生产者消费者模型 排队叫号系统

判断一个问题是否适合队列，可以问：

先进入的数据，是否应该优先处理？

如果答案是肯定的，通常可以考虑队列。

总结

queue是一种规则简单、应用广泛的数据结构。

学习时需要重点掌握：

1. 队列遵循先进先出规则 2. push 从队尾插入 3. pop 从队头删除 4. front 访问队头，back 访问队尾 5. pop 不返回被删除元素 6. queue 是容器适配器，没有公开迭代器 7. 默认底层容器是 deque 8. BFS 和层序遍历是队列的典型应用

通过简单模拟实现可以看到，队列同样没有重新发明底层存储结构，而是把已有容器的接口重新组织成：

队尾进入 队头离开

理解了这个过程，也就理解了 STL 容器适配器最核心的设计思路。