stack、queue与priority_queue的用法解析与模拟实现-北京尧图网络

目录一、stack、queue1.1 stack、queue的使用1.1.1 stack栈1.1.2 queue队列1.2 容器适配器1.2.1 vector和list优缺点1.2.2 deque1.3 stack、queue的模拟二、priority_queue2.1 priority_queue的使用2.2 仿函数使用和解释编辑2.3 priority_queue的模拟三、总结stack算法和数据结构实际开发queue算法和数据结构实际开发priority_queue算法和数据结构实际开发一、stack、queue1.1 stack、queue的使用1.1.1 stack栈首先就是对于stack这个栈的介绍可以看我们数据结构队列和栈数据结构-CSDN博客简单介绍就是先进后出。stack构造初始化int main() { stackint st({1,2,3,4,5}); while (!st.empty()) { cout st.top() ; st.pop(); } return 0; }判断栈内是否有元素stackint st2; if (st2.empty()) { cout true; } else { cout false; }计算有效元素个数stackint st3({ 1,2,3,4,5,6 }); cout st3.size() endl;取栈顶元素stackint st3({ 1,2,3,4,5,6 }); cout st3.top() endl;入栈插入元素到栈中stackint st4; st4.push(1); st4.push(2); st4.push(3); st4.push(4); while (!st4.empty()) { cout st4.top() ; st4.pop(); }出栈将栈顶元素删除stackint st3({ 1,2,3,4,5,6 }); cout pop之前 st3.size() endl; st3.pop(); cout pop之后 st3.size() endl;1.1.2 queue队列对于queue队列的介绍同样也可以参考这个博客队列和栈数据结构-CSDN博客简单介绍就是先进先出。queue的初始化queueint q1({ 1,2,3,4,5,6,7 }); while (!q1.empty()) { cout q1.front() ; q1.pop(); }判断队列中是否有元素queueint q2({ 1,2,3,4,5 }); queueint q3; if (q2.empty()) cout q2: true; else cout q2: false; cout endl; cout endl; if (q3.empty()) cout q3: true; else cout q3: false;计算队列中元素个数queueint q4({1,2,3,4,5}); cout q4.size(): q4.size();取对头元素queueint q4({1,2,3,4,5}); cout q4.front(): q4.front();取队尾元素queueint q4({1,2,3,4,5}); cout q4.back(): q4.back();在队尾插入一个元素queueint q5; q5.push(1); q5.push(2); q5.push(3); q5.push(4); q5.push(5); while (!q5.empty()) { cout q5.front() ; q5.pop(); }从对头删一个删数据queueint q6({ 1,2,3,4,5 }); cout q6.pop()之前: q6.size()endl; q6.pop(); cout q6.pop()之后: q6.size();1.2 容器适配器1.2.1 vector和list优缺点vector数组优缺点优点缺点下标随机访问快尾删尾插效率高o(1)头插头删中间插入删除效率低oncpu高速缓存命中率高物理结构是连续的插入过程扩容1.5/2倍导致空间浪费会有性能亏损list链表优缺点优点缺点头查头删中间插入删除效率高o(1)不能支持下标随机访问尾删尾插效率低需要遍历o(n)插入过程不需要扩容创多少申请多少内存节约空间cpu高速缓存命中率低(cpu会先缓存后面高地址但是list是物理结构非连续)1.2.2 deque容器适配器也是一个模板类用于适配对应的容器stack和queue。适配器是一种设计模式(设计模式是一套被反复使用的、多数人知晓的、经过分类编目的、代码设计经验的总结)该种模式是将一个类的接口转换成客户希望的另外一个接口。这里队列和栈在STL里面都是用的一个容器适配器deque。deque是一个双端队列他既有能代替vector数组还能代替list链表相当于是vector和list的结合deque是一种双开口的连续空间的数据结构双开口的含义是可以在头尾两端进行插入和删除操作且时间复杂度为O(1)与vector比较头插效率高不需要搬移元素与list比较空间利用率比较高在stl中源码可参看CSDN代码共享资源: 分享比较常用的源码并介绍展示源码的工作原来里面也简单了解了原理。对于deque既能代替list和vector但是他并不是针对某一个的数据结构而设计的而是既满足list又满足vector但是在某方面性能会不如list和vector所以这个不能完全代替list和vector数据结构。1.3 stack、queue的模拟stack的底层是vector数组queue的底层是list链表但是上面我们说了容器适配器的概念deque能够代替stack和vector的底层所以stack和queue的模拟会很简单实现。stack的模拟namespace bear { templateclass T,class Contain dequeT//T表示栈存储的类型Contain表示容器适配器 class stack { public: //调用自定义类的内部构造函数拷贝、初始化 stack(){} //入栈 void push(const T vaule) { _con.push_back(vaule); } //删栈顶 void pop() { _con.pop_back(); } //计算栈内元素 size_t size() { return _con.size(); } //取栈顶数据非const T top() { return _con.back(); } //取栈顶数据const const T top()const { return _con.back(); } //判断栈内是否有元素 bool empty() { return _con.empty(); } private: //自定义类成员 Contain _con; }; }queue的模拟namespace bear { templateclass T,class Contain dequeT//T表示队列存储类型Contain表示容器适配器存储的数据结构 class queue { public: //入队列 void push(const T vaule) { _con.push_back(vaule); } //出队列 void pop() { _con.pop_front(); } //计算队列元素个数 size_t size() { return _con.size(); } //取对头元素非const T front() { return _con.front(); } //取对头元素const const T front()const { return _con.front(); } //取队尾元素非const T back() { return _con.back(); } //取队尾元素const const T back()const { return _con.back(); } //判读队列是否为空 bool empty()const { return _con.empty(); } private: Contain _con; }; }二、priority_queue2.1 priority_queue的使用priority_queue优先级队列就是和队列一样的使用方法都满足先进后出的原理只不过他这个队列出队列是有升序和降序的其实底层本质就是内部是一个堆数据结构具体可以参考这个堆博客堆数据结构_堆数据结构-CSDN博客)取对头数据这里指排序后的对头priority_queueint pq; pq.push(3132); pq.push(123); pq.push(4000); pq.push(5000); pq.push(1000); pq.push(1); while (!pq.empty()) { cout pq.top() ;//相当于取对头数据 pq.pop(); }改变出对头数据顺序priority_queueint,vectorint,greaterint pq; pq.push(3132); pq.push(123); pq.push(4000); pq.push(5000); pq.push(1000); pq.push(1); while (!pq.empty()) { cout pq.top() ; pq.pop(); }2.2 仿函数使用和解释首先我们先来写一个仿函数namespace bear { //仿函数主体 templateclass T struct less { bool compare(T x, T y) { return x y; } }; //仿函数应用 templateclass T, class compare lessT void BubbleSort(T* arr, int n, compare com) { int flag 0; for (int i 0; i n; i) { for (int j 0; j n - 1 - i; j) { //没仿函数的冒泡 //if (arr[j] arr[j 1]) //{ // swap(arr[j], arr[j 1]); // flag 1; //} //有访函数的冒泡 if (com(arr[j], arr[j 1])) { swap(arr[j], arr[j 1]); flag 1; } } if (flag 0) { break; } } } }这个仿函数功能和实现很简单所以是没有成员变量的但是大部分情况下可能需要自己写成员变量来增加仿函数的功能状态保持成员变量让仿函数可以在多次调用之间保持状态配置灵活性通过构造函数或setter方法配置仿函数的行为信息记录可以记录调用次数、处理的数据等信息参数化行为成员变量可以作为参数影响仿函数的逻辑仿函数用于泛型函数相当于函数指针仿函数是用类封装然后再用模板去泛型而函数指针则是用指针去封装都是做的对应需求判断也可以是需要的类型不一定是bool类型还能是int类型然后进行控制最终结果。仿函数在类包装然后通过在其他类中使用该类模板来调用对应类的函数该里面就和函数指针一样传参这些在外部仿函数是用类封装的所以使用时是需要用匿名对象来传给另一个类仿函数是模板函数其速度比一般函数要慢但是使得代码更加通用简化了代码还能用不同类型通过不同类型代表不同的状态也就是返回类型传模板时候我们只能传类型而不是传对象在传参时候就需要传对象是内部类就不需要传类模板参数而在类外调用类就需要传类模板参数如下图2.3 priority_queue的模拟根据仿函数的使用和priority_queue的介绍知道内部是一个堆结构并通过仿函数来控制priority_queue的顺序。整体结构using namespace std; namespace bear { templateclass T,class Contain vectorT,class Compare lessT class priority_queue { public: private: Contain _con; }; }判断优先级队列是否有元素//判断优先级队列为空 bool empty()const { return _con.empty(); }计算优先级队列的元素个数//计算优先级队列元素个数 size_t size()const { return _con.size(); }取优先级队列的对头元素//取优先级队列对头元素(非const) T top() { return _con.front(); } //const版本 const T top()const { return _con.front(); }向上建堆//非仿函数比较 void adjust_up(size_t child) { size_t parent (child - 1) / 2; while (child 0) { if (_con[parent] _con[child]) { swap(_con[parent], _con[child]); child parent; parent (child - 1) / 2; } else { break; } } } //仿函数 templateclass T //大堆 struct less { bool operator()(T x, T y)const { return x y; } }; //小堆 templateclass T struct greater { bool operator()(T x, T y) { return x y; } }; //仿函数比较 void adjust_up(size_t child) { Compare com; size_t parent (child - 1) / 2; while (child 0) { if (com(_con[parent],_con[child])) { swap(_con[parent], _con[child]); child parent; parent (child - 1) / 2; } else { break; } } }向下建堆//非仿函数比较 void adjust_down(size_t parent) { size_t child (parent * 2) 1;//默认左孩子 while (child size()) { //判断左右孩子哪个大/小(还得防止越界) if (child 1 size() _con[child] _con[child 1]) child; if (_con[parent] _con[child]) { swap(_con[parent], _con[child]); parent child; child parent * 2 1; } else { break; } } } templateclass T //大堆 struct less { bool operator()(T x, T y)const { return x y; } }; //小堆 templateclass T struct greater { bool operator()(T x, T y) { return x y; } }; //仿函数比较 void adjust_down(size_t parent) { Compare com; size_t child (parent * 2) 1;//默认左孩子 while (child size()) { //判断左右孩子哪个大/小(还得防止越界) if (child 1 size() com(_con[child], _con[child 1])) child; if (com(_con[parent],_con[child])) { swap(_con[parent], _con[child]); parent child; child parent * 2 1; } else { break; } } }push入队尾数据会按照堆结构进行排队而不是插入顺序//入优先级队列 void push(const T value) { _con.push_back(value); adjust_up(_con.size()-1); }pop删对头数据通过堆结构进行排序堆顶和堆尾交换进行尾删//删优先级队列对头 void pop() { assert(!empty()); //先交换堆顶和堆尾 swap(_con[0], _con[size() - 1]); //再尾删 _con.pop_back(); if(size() ! 1) //再进行调整堆 adjust_down(0); }初始化迭代器给队列初始化priority_queue() default;//用于调用默认构造 templateclass InputIterator priority_queue(InputIterator first,InputIterator last) :_con(first,last)//调用自定义成员的迭代器初始化 { for (int i (size() - 1-1) / 2; i 0; i--) { adjust_down(i); } }完整代码#pragma once #includevector #includeassert.h using namespace std; namespace bear { templateclass T //大堆 struct less { bool operator()(T x, T y)const { return x y; } }; //小堆 templateclass T struct greater { bool operator()(T x, T y) { return x y; } }; templateclass T,class Contain vectorT,class Compare lessT class priority_queue { public: priority_queue() default;//用于调用默认构造 templateclass InputIterator priority_queue(InputIterator first,InputIterator last) :_con(first,last)//调用自定义成员的迭代器初始化 { for (int i (size() - 1-1) / 2; i 0; i--) { adjust_down(i); } } //判断优先级队列为空 bool empty()const { return _con.empty(); } //计算优先级队列元素个数 size_t size()const { return _con.size(); } //取优先级队列对头元素(非const) T top() { return _con.front(); } //const版本 const T top()const { return _con.front(); } //入优先级队列 void push(const T value) { _con.push_back(value); adjust_up(_con.size()-1); } //删优先级队列对头 void pop() { assert(!empty()); //先交换堆顶和堆尾 swap(_con[0], _con[size() - 1]); //再尾删 _con.pop_back(); if(size() 0) //再进行调整堆 adjust_down(0); } private: Contain _con;//会调用默认自定义类成员的构造函数 //向上调整 //小堆 //大堆 //void adjust_up(size_t child) //{ // size_t parent (child - 1) / 2; // while (child 0) // { // if (_con[parent] _con[child]) // { // swap(_con[parent], _con[child]); // child parent; // parent (child - 1) / 2; // } // else // { // break; // } // } //} void adjust_up(size_t child) { Compare com; size_t parent (child - 1) / 2; while (child 0) { if (com(_con[parent],_con[child])) { swap(_con[parent], _con[child]); child parent; parent (child - 1) / 2; } else { break; } } } //void adjust_down(size_t parent) //{ // size_t child (parent * 2) 1;//默认左孩子 // while (child size()) // { // //判断左右孩子哪个大/小(还得防止越界) // if (child 1 size() _con[child] _con[child 1]) // child; // if (_con[parent] _con[child]) // { // swap(_con[parent], _con[child]); // parent child; // child parent * 2 1; // } // else // { // break; // } // } //} void adjust_down(size_t parent) { Compare com; size_t child (parent * 2) 1;//默认左孩子 while (child size()) { //判断左右孩子哪个大/小(还得防止越界) if (child 1 size() com(_con[child], _con[child 1])) child; if (com(_con[parent],_con[child])) { swap(_con[parent], _con[child]); parent child; child parent * 2 1; } else { break; } } } }; }三、总结stack是一个先进后出数据结构而queue是一个先进先出的数据结构还有一个queue的展开就是优先级队列priority_queue这里priority_queue的知识点较多涉及到了仿函数和综合了堆排列。其次就是栈和队列他们之间的模拟又涉及到了容器适配器deque双端队列以及让我们学习到该如何学习和了解源码。这里最主要的就是stack、queue和priority_queue的应用场景stack算法和数据结构函数调用栈程序执行时的函数调用和返回表达式求值中缀表达式转后缀表达式后缀表达式求值括号匹配检查代码中的括号是否匹配深度优先搜索DFS递归或非递归实现回溯算法如迷宫求解、八皇后问题实际开发撤销/重做功能文本编辑器、图形软件的撤销操作浏览器历史记录前进后退功能递归转迭代将递归算法转换为迭代实现queue算法和数据结构广度优先搜索BFS树和图的层次遍历缓存系统LRU缓存淘汰算法任务调度操作系统进程调度消息队列异步任务处理实际开发打印队列打印机任务管理网络数据包传输TCP协议的数据包排队事件处理GUI应用中的事件队列资源池管理数据库连接池、线程池priority_queue算法和数据结构Dijkstra算法最短路径算法哈夫曼编码数据压缩Top K问题找出前K个最大/最小元素合并K个有序链表/数组A*搜索算法游戏中的路径寻找实际开发任务调度系统按优先级处理任务实时系统处理紧急事件数据流的中位数使用两个堆维护负载均衡选择负载最小的服务器事件模拟按时间顺序处理事件

stack、queue与priority_queue的用法解析与模拟实现

相关推荐

【09】C++实战篇——C++ 生成静态库.lib 及 C++调用lib，及实际项目中的使用技巧

【28】C++错误 C1189 #error: Building MFC application with /MD[d] (CRT dll version) requires MFC shared

【41】C++实战篇——VS2022检测程序内存泄漏， C++内存泄漏检测工具VLD(Visual Leak Detector)，打印C++内存泄漏报告，找具体内存泄漏位置

更多资讯

S7-1200 PUT/GET通信实战：连对、写对、防错三要素

控制器当Git服务器：TwinCAT 3 AdsGitServer版本回退

DeepSeek大模型API接入、流式输出与移动端配置指南

七端口交换板REV 2.1改版拆解：端口拓扑、复位与配置引脚复用

15页5G+VR智慧旅游方案PPT：VR观景台到数据中台的拆解复用

MySQL高阶篇之配置文件详解与各类客户端工具

今日更新

微信个人号API开发案例：图片/语音/视频消息怎么下载解析存到本地？

Python股票自动交易系统源码解析：从行情获取到风控的完整链路

视酷酷信IM源码部署指南：Java 17+MySQL 8.0.33实战配置

本周精选

防幻觉智能体架构：电源硬件设计中的大模型编排与工具化实践

OpenGL面试核心考点：渲染管线、矩阵变换与性能排查全解析

全国计算机二级C语言真题PDF高效刷题指南

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

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