【C++ STL栈和队列下】deque(双端队列) 优先级队列的模拟实现与仿函数的介绍
🔥个人主页：爱和冰阔乐
📚专栏传送门：《数据结构与算法》 、C++
🐶学习方向：C++方向学习爱好者
⭐人生格言：得知坦然 ，失之淡然
博主简介
文章目录
前言
本文聚焦STL双端队列（deque）与优先级队列的底层实现，深度剖析deque如何融合vector与list的优势，通过中控数组与分段缓存实现高效头尾操作；结合优先级队列的堆结构，详解仿函数在自定义排序规则中的核心作用。通过模拟实现代码与性能对比，让大家容器适配器，,希望读完本文可以让大家对栈和队列有更深刻理解
一、deque（双端队列）
1.1 list和vector的优缺点
在前面介绍栈和队列的原型时我们为deque埋下了伏笔，那么deque是什么？
deque就是大家在生活中所说的缝合怪，是vector和list的缝合
在deque的官方文档的接口中，我们发现deque既有vector的下标随机访问也有list的头插/头删两种容器的独特接口，因此我们认为deque是vector和list的缝合怪，存在deque的原因便是list和vector有着鲜明的优缺点
vector的优点：
1.尾插尾删效率不错，支持高效的下标随机访问
2.物理空间连续，所以高速缓存利用率高
缺点：
1.空间需要扩容，扩容有一些代价（效率和空间浪费）
2.头部和中间的插入删除效率低
list的优点：
1.按需申请释放空间，不需要扩容
2.支持任意位置的插入删除
缺点：
1.不支持下标的随机访问
1.2 deque的原理介绍
deque(双端队列)：是一种双开口的"连续"空间的数据结构，双开口的含义是：可以在头尾两端进行插入和删除操作，且时间复杂度为O(1)，与vector比较，头插效率高，不需要搬移元素；与list比较，空间利用率比较高
deque并不是真正连续的空间，而是由一段段连续的小空间拼接而成的，实际deque类似于一个动态的二维数组，其底层结构如下图所示：
图1：
图2：
我们定义一段一段的buff小数组，当buff满了再开辟buff数组，这样便可以解决链表的缓存效率低下的问题，我们再定义一个中控数组(本质是指针数组)ptr，在该数组中我们将第一个buff数组的地址存放在其的中间，因为我们如果头插时便可以直接在中控数组中间位置的前一个位置存放新的buff地址即可，同理尾插也是如此。当中控数组满了再进行扩容
当我们定义好了deque的大框架后，那么怎么获取第i个数据？
我们可以用 i / N 就知道该数据是存放在哪个buff里面，再将 i % N就知道了在该buff的哪个位置,在图1中，假设我们要寻找的数据在ptr中的第x位置，那么我们便可以ptr[x]便知道了该数据存放在第x个buff里面，ptr[x][y]便可以知道其存放在buff的哪个位置了
双端队列底层是一段假象的连续空间，实际是分段连续的，为了维护其“整体连续”以及随机访问的假象，落在了deque的迭代器身上（也就是operator++ 和 operator-- 两个运算符重载身上），因此deque的迭代器设计就比较复杂
deque的缓存区，中控器和迭代器的关系如下：
那deque是如何借助其迭代器维护其假想连续的结构呢？
deque::begin()传回迭代器start，deque::end()传回迭代器finish，迭代器由cur（指向当前位置），first（指向当前buff的开始位置），last（当前buff的的结束位置），node（指向中控区存放该数组的地址）组成，如下图：
实现operator++时，我们需要判断当前buff有没有走完，如果没有走完，直接++cur即可，走完，我们则需找到下一个buff，通过node+1再解引用就找到了下一个buff的开始位置，因此我们将迭代器的first指向找到的新的buff即可，由于buff的大小是固定的，因此last也找到了，再让cur指向第一个位置便大功告成了！
分析：deque的头插尾插效率高于vector和list，在list中，每次开辟空间只开一个，而deque每次开一段空间（一次申请40个字节的空间比10次申请4个字节的效率高），而vector的扩容代价太大（在后期扩容时，需要将原来的大量数据拷贝下来，并且还需要释放旧空间），在deque中如果buff没满插入数据即可，满了就新开buff，再将迭代器的四个指针指向的位置改下即可，只有在中控区满的时候需要扩容（扩容代价很低，只拷贝指针）
总结：
1.deque的头插尾插效率很高，更甚于vector和list
2.下标随机访问效率还不错，但是比不上vector（需要调用几个函数并且还有运算）
3.在中间插入删除数据（所有的buff均向前/向后移动，效率和vector一样，如果只让当前buff移动，那么就需要对当前buff扩容，导致每个buff大小都不一样，会导致下标+[ ]效率更低）的效率为O（n）
但正是因为栈和队列不需要对中间元素进行处理，所以我们使用deque作为其的默认适配容器便很合理了
1.3 deque和vector的性能对比
我们在release版本下，对比100w数据下，deque和vector的排序
voidtest_op1(){srand(time(0));constint N =1000000; deque<int> dq; vector<int> v;for(int i =0; i < N;++i){auto e =rand()+ i; v.push_back(e); dq.push_back(e);}int begin1 =clock();sort(v.begin(), v.end());int end1 =clock();int begin2 =clock();sort(dq.begin(), dq.end());int end2 =clock();printf("vector:%d\n", end1 - begin1);printf("deque:%d\n", end2 - begin2);}
总结：在release下，大量访问数据时，deque的性能约vector的1/2
二、优先级队列
2.1 定义及其作用
优先级队列官方链接：https://cplusplus.com/reference/queue/priority_queue/
我们根据官方文档便知道优先级队列也是一个容器适配器，那么其是什么及其作用又是什么？
在官方文档中定义优先级队列为：
总结·：优先级队列是一种抽象数据类型（ADT），它类似普通队列，但核心特性是：元素的处理顺序不由插入顺序决定（与普通队列不同），而是由元素的 “优先级” 决定。每次从队列中取出的，总是当前优先级最高的元素（优先级可自定义，例如 “数值大的优先” 或 “数值小的优先”），由于其核心的特性类似于堆，而堆的底层是vector实现的（不断地需要根据父亲节点算孩子即下标访问），且deque的随机访问效率低于vector，因此容器默认vector
在这些接口中我们需要注意top和pop接口，其要取优先级高的数据（默认是大的数据优先级高，如果想让小的数据优先级高，可以使用仿函数）
2.2 模拟实现优先级队列
由于其的机制类似于堆，那么我们将用堆来实现优先级队列
以下代码便是其的基本框架：
namespace hxx {template<classT,classContainer=vector<int>>classPriorityQueue{public:voidpush(const T& x){}voidpop(){}voidtop(){}private: Container _con;};}实现插入数据的底层逻辑和堆的插入数据一模一样(物理结构是数组，逻辑结构是堆，因此我们需要把数组的元素一层一层放到堆上，即完全二叉树，其节点下标关系满足 left child=parent*2+1)：
1.现将元素插入到堆的末尾，即最后一个孩子之后
2.插入之后如果堆的性质遭到破坏，将新插入节点顺着其双亲往上调整到合适位置即可(向上调整算法)
向上调整算法
voidAdjustUp(int child){int parent =(child -1)/2;while(child >0){if(_con[child]>_con[parent]){swap(_con[child], _con[parent]); child = parent; parent =(child -1)/2;}else{break;}}}那么向上调整算法搞定了，push接口便轻松实现了，当然2向上调整算法也不需要我们进行底层的搭建，在C++算法库中便已经实现了
删除接口：
同理删除接口也要调用堆的向下调整算法
1.将堆顶元素与堆中最后一个元素进行交换
2.删除堆中的最后一个元素
3.将堆顶元素向下调整到满足堆的特性为止
向下调整算法
//向下调整算法voidAdjustDown(int parent){// 先假设左孩子小 size_t child = parent *2+1; Compare com;while(child < _con.size())// child >= n说明孩子不存在，调整到叶子了{// 找出小的那个孩子if(child +1< _con.size()&&_con(_con[child+1]>_con[child ])){++child;}if(_con[child]>_con[parent]){swap(_con[child], _con[parent]); parent = child; child = parent *2+1;}else{break;}}}这些接口实现完后，那么简单的优先级队列便已经实现好了
注意：如果对二叉树的性质不熟悉的，可以阅读我C语言数据结构的文章：【数据结构】长幼有序：树、二叉树、堆排序与TOP-K问题的层次解析（含源码）
2.3 仿函数
可是如果按照上面的写法，那么优先级队列也就写死了，只允许大的优先级高。那么是否要实现两个堆，这样是否过于冗余，因此在前面官方文档的介绍中埋下的伏笔——仿函数便起到了点睛之笔
仿函数（也称为函数对象）并不是函数，本质是一个重载了 operator() 的类—— 它的对象可以像普通函数一样被调用，因此得名 “仿函数”。
//仿函数：本质是类template<classT>classLess{public://仿函数这个类只要有operator（）就可以booloperator()(int x,int y){return x<y;}};intmain(){ Less<int> lessFunc;//在没有看到上面的类模板实例化前，我们会把lessfunc当成函数名或者函数指针，但是这里是对象 cout<<lessFunc(1,2)<<endl; cout<<lessFunc.operator()(1,2)<<endl;}仿函数的核心作用：
1.在 STL 算法（如 sort、priority_queue）中，替代普通函数作为比较 / 操作规则。例如在代码中的 Less 和 Greater，用于控制优先级队列的堆结构（最大堆 / 最小堆）
classGreater{public:booloperator()(int a,int b)const{return a > b;// 降序排序}}; vector<int> v ={3,1,4,1,5,9};sort(v.begin(), v.end(),Greater());// 排序后：9 5 4 3 1 12.普通函数无法携带成员变量（状态），但仿函数可以通过类的成员变量保存状态，在多次调用中共享信息
classCounter{private:int _count =0;public:voidoperator()(){ _count++; cout <<"调用次数："<< _count << endl;}}; Counter cnt;cnt();// 输出：调用次数：1cnt();// 输出：调用次数：23.仿函数可以作为模板参数，让算法 / 数据结构的行为更具通用性（如priority_queue 模板中通过 Compare 仿函数支持自定义比较）
在实际实现优先级队列时，我们并不需要实现仿函数，直接用即可
intmain(){ priority_queue<int, vector<int>, greater<int>> pq; pq.push(4); pq.push(1); pq.push(5); pq.push(7); pq.push(9);while(!pq.empty()){ cout << pq.top()<<" ";} cout << endl;return0;}一般场景仿函数不需要我们写，那么既然有一般情况，就会有特殊情况需要我们写仿函数，这里特殊情况分为两种：
1.类类型不支持比较大小
2.支持比较大小，但是比较的逻辑不是你想要的
在之前学类和对象的过程我们便模拟实现了日期类这个小项目，这里优先级队列里仿函数是支持日期内里面实现的比大小
classDate{friend ostream&operator<<(ostream& _cout,const Date& d);public:Date(int year =1900,int month =1,int day =1):_year(year),_month(month),_day(day){}booloperator<(const Date& d)const{return(_year < d._year)||(_year == d._year && _month < d._month)||(_year == d._year && _month == d._month && _day < d._day);}booloperator>(const Date& d)const{return(_year > d._year)||(_year == d._year && _month > d._month)||(_year == d._year && _month == d._month && _day > d._day);}private:int _year;int _month;int _day;}; ostream&operator<<(ostream& _cout,const Date& d){ _cout << d._year <<"-"<< d._month <<"-"<< d._day;return _cout;}classDateLess{public:booloperator()(Date* p1, Date* p2){return*p1 <*p2;}};intmain(){ priority_queue<Date> q1; q1.push(Date(2025,12,7)); q1.push(Date(2025,12,7)); q1.push(Date(2025,12,7)); cout << q1.top()<< endl;while(!q1.empty()){ cout << q1.top()<<" ";} cout << endl;return0;}因此哪怕是自定义类型，但是只要我们在该类中实现了内部的比大小即可，但是如果我们在自定义类中没有重载比大小，那么我们就需要自己实现仿函数
如果比较的逻辑不是我们所想要的，如下：
//Date类和上一样intmain(){ priority_queue<Date*>q2; q2.push(newDate(2025,12,7)); q2.push(newDate(2025,12,7)); q2.push(newDate(2025,12,7)); cout <<*q2.top()<< endl; q2.pop(); cout <<*q2.top()<< endl; q2.pop(); cout <<*q2.top()<<endl;}
欧吼，我们发现两次输出的结构并不相同，我们思考下为什么每次比较大小的结果不一样，仔细观察下代码，我们发现，由于每次new的地址每个大小是随机的，所以比较结果各不相同，那么这时候我们就需要自己写仿函数实现我们想要的比大小的逻辑
classDateLess{booloperator()( Date* d1, Date* d2){//我们不需要自己实现比大小逻辑，只需要解引用其对象，其自己重载了比较大小return*d1 <*d2;}};intmain(){ priority_queue<Date*,vector<Date*>>q2; q2.push(newDate(2025,12,7)); q2.push(newDate(2025,8,25)); q2.push(newDate(2025,9,30)); cout <<*q2.top()<< endl; q2.pop(); cout <<*q2.top()<< endl; q2.pop(); cout <<*q2.top()<<endl;return0;}
如上便是按照我们想法所实现的比大小逻辑
三、总结
坚持到这里，已经很棒啦，希望读完本文可以帮读者大大更好了解栈和队列的底层逻辑！！！如果喜欢本文的可以给博主点点免费的攒攒，你们的支持就是我前进的动力🎆
资源分享：双端队列与优先级队列源码
