C STL 队列详解queue 的使用、经典应用与简单模拟实现 星恒随风个人主页❄️ 个人专栏《指针合集》《C语言基础》《数据结构》《机器学习导论》《前端基础》《python基础》《C从入门到入土》✨ 数据即知识压缩即智能文章目录C STL 队列详解queue 的使用、经典应用与简单模拟实现前言一、什么是队列二、queue 也是容器适配器三、queue 的常用接口四、front 和 back 分别表示什么五、queue 的 pop 同样不返回元素六、如何遍历 queue七、队列和栈有什么区别栈队列八、经典应用广度优先搜索九、经典应用二叉树层序遍历十、用两个栈实现队列十一、简单模拟实现 queue十二、使用 list 作为底层容器十三、为什么默认选择 deque十四、queue 和 priority_queue 不一样十五、常见错误整理1. 对空队列调用 front、back 或 pop2. 认为 pop 会返回队头元素3. 混淆 front 和 back4. 使用 vector 频繁删除头部元素5. BFS 中入队后才忘记标记十六、queue 的常见使用场景总结前言生活中排队是一件很常见的事。先到的人先接受服务后到的人排在队尾等待。数据结构中的队列也是按照类似的规则工作先进先出 First In First Out FIFOC 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::queueint近似于std::queueint,std::dequeint也可以指定liststd::queueint,std::listintq;普通vector不适合作为标准队列的底层容器因为它没有pop_front()在头部删除元素通常还要搬移后面的数据。三、queue 的常用接口使用队列需要包含#includequeue常见接口如下接口作用queue()构造空队列empty()判断队列是否为空size()返回队列中的元素个数front()返回队头元素的引用back()返回队尾元素的引用push(x)从队尾插入元素pop()删除队头元素emplace(...)在队尾直接构造元素swap()交换两个队列基本示例#includeiostream#includequeueusingnamespacestd;intmain(){queueintq;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 同样不返回元素下面的写法是错误的intvalueq.pop();和栈一样queue::pop()只负责删除元素不返回被删除的值。如果需要得到队头元素应该先调用front()intvalueq.front();q.pop();完整写法if(!q.empty()){intvalueq.front();q.pop();coutvalue\n;}六、如何遍历 queuequeue没有提供begin()end()也不能直接使用范围for遍历。原因和stack相同队列是容器适配器只允许按照先进先出的规则访问元素。如果允许任意访问中间位置就破坏了队列的接口约束。想按出队顺序查看队列可以不断读取front()while(!q.empty()){coutq.front() ;q.pop();}这会清空原队列。如果想保留原队列可以先复制queueintcopyq;while(!copy.empty()){coutcopy.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开始先把0入队处理0将1、2入队接着处理1、2再处理它们扩展出的3、4。代码如下#includeiostream#includequeue#includevectorusingnamespacestd;vectorintbfs(constvectorvectorintgraph,intstart){vectorintresult;vectorboolvisited(graph.size(),false);queueintq;q.push(start);visited[start]true;while(!q.empty()){intcurrentq.front();q.pop();result.push_back(current);for(intnext:graph[current]){if(!visited[next]){visited[next]true;q.push(next);}}}returnresult;}intmain(){vectorvectorintgraph{{1,2},{3},{4},{},{}};vectorintorderbfs(graph,0);for(intnode:order){coutnode ;}return0;}输出0 1 2 3 4队列保证先加入的相邻节点先被处理因此搜索会一层一层向外扩展。九、经典应用二叉树层序遍历层序遍历同样依赖队列。基本过程是根节点入队取出队头节点访问当前节点将当前节点的左右孩子入队重复以上过程。代码如下#includequeue#includevectorusingnamespacestd;structTreeNode{intval;TreeNode*left;TreeNode*right;TreeNode(intvalue):val(value),left(nullptr),right(nullptr){}};vectorintlevelOrder(TreeNode*root){vectorintresult;if(rootnullptr){returnresult;}queueTreeNode*q;q.push(root);while(!q.empty()){TreeNode*currentq.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负责出队入队时直接压入_inpush(1) push(2) push(3) _in 栈顶 3 2 1出队时如果_out为空就把_in中的元素全部转移到_out_out 栈顶 1 2 3这时_out的栈顶就是最早进入的元素1。实现如下#includecassert#includestackusingnamespacestd;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:stackint_in;stackint_out;};这里不要每次出队都来回倒腾元素。只有_out为空时才把_in的元素转移过去。这样每个元素最多经历一次进入_in、一次转入_out和一次弹出。十一、简单模拟实现 queue队列需要底层容器支持队尾插入 队头删除 访问队头 访问队尾因此不能直接使用普通vector实现高效队列。如果用vector.erase(vector.begin());删除队头后后面的所有元素通常都需要向前移动效率较低。更合适的底层容器包括deque list下面使用默认的deque进行简单封装#includecassert#includecstddef#includedequenamespacebit{templateclassT,classContainerstd::dequeTclassqueue{public:queue()default;voidpush(constTvalue){_container.push_back(value);}voidpop(){assert(!_container.empty());_container.pop_front();}Tfront(){assert(!_container.empty());return_container.front();}constTfront()const{assert(!_container.empty());return_container.front();}Tback(){assert(!_container.empty());return_container.back();}constTback()const{assert(!_container.empty());return_container.back();}std::size_tsize()const{return_container.size();}boolempty()const{return_container.empty();}private:Container _container;};}测试代码#includeiostreamintmain(){bit::queueintq;q.push(10);q.push(20);q.push(30);while(!q.empty()){std::coutq.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支持高效头删和尾插也可以用来封装队列#includelistbit::queueint,std::listintq;队列模拟实现本身不需要知道底层究竟是deque还是list。只要底层容器具备需要的接口push_back()pop_front()front()back()size()empty()队列适配器就可以正常工作。这也是模板和容器适配器结合后的好处上层数据结构依赖接口而不是依赖某一种固定实现。十三、为什么默认选择 dequequeue需要在两端进行操作队尾插入 队头删除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错误queueintq;coutq.front();应先判断if(!q.empty()){coutq.front();}2. 认为 pop 会返回队头元素错误intvalueq.pop();正确intvalueq.front();q.pop();3. 混淆 front 和 backfront最早进入、即将出队的元素 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 容器适配器最核心的设计思路。