【C++】stack和queue的使用及模拟实现

stack就是栈的意思，这个结构遵循后进先出(LIFO)的原则，可以将栈想象为一个子弹夹，先进去的子弹后出来。

queue就是队列的意思，这个结构遵循先进先出(FIFO)的原则，可以将对列想象成我们排队买饭的场景，先排队的人先买饭。

STL将satck和queue归为容器这一类了，但其实它们是容器适配器(容器适配器会在下面模拟实现的部分会讲到，如果不懂的话可以先忽略这一概念)，它们的使用非常简单，接口相比于vector，list容器要少的多，我们接下来一起来学习一下吧！

一、stack基本介绍和使用

stack是类模板，第一个模板参数是T就是栈中数据元素的类型，第二个模板参数就是容器适配器，稍后会讲，在讲它之前，请大家忽略它，只传第一个参数，第二个用缺省参数。 

它的逻辑结构如下：

成员函数名称	功能介绍
push()	在栈顶位置添加新元素
pop()	删除栈顶元素
top()	返回栈顶元素
empty()	判断栈是否为空
size()	返回栈中数据个数

以上5个接口是比较常用到的，我们针对以上5个接口写一段代码来介绍它们的使用及效果：

#include <iostream>
#include <stack>
using namespace std;int main()
{stack<int> st;  //定义一个栈，栈中的数据元素的类型是int//向栈中压入3个元素(压栈)st.push(1);st.push(2);st.push(3);//打印栈中数据个数cout << "size of st:" << st.size() << endl;//利用循环打印栈中元素，注意打印结果的顺序(遵循LIFO)while (!st.empty()){cout << st.top() << " ";  //打印栈顶元素st.pop(); //删除栈顶元素(出栈)}cout << endl;//栈中元素出完后，此时size()应该为0cout << "size of st:" << st.size() << endl; return 0;
}

运行结果：

 从打印结果上看，栈遵循后进先出原则。

二、queue基本介绍和使用 

queue也是类模板，它的参数和stack一模一样，表达的意思也一样，这里就不多啰嗦了。

它的结构如下：

成员函数名称	功能介绍
push()	在队尾位置添加新元素
pop()	删除队头元素
front()	返回队头元素
back()	返回队尾元素
empty()	判断队列是否为空
size()	返回队列中数据个数

以上6个接口是比较常用到的，我们针对以上6个接口写一段代码来介绍它们的使用及效果：

#include <iostream>
#include <queue>  
using namespace std;int main()
{queue<int> q;  //定义一个队列，队列中的数据元素的类型是int//向队列中添加3个元素q.push(1);q.push(2);q.push(3);//打印队列中数据个数cout << "size of q:" << q.size() << endl;//打印队列中队头数据cout << "front element of q:" << q.front() << endl;//打印队列中队尾数据cout << "back element of q:" << q.back() << endl;//利用循环打印队列中元素，注意打印结果的顺序(遵循FIFO)while (!q.empty()){cout << q.front() << " ";  //打印队头元素q.pop(); //删除队头元素}cout << endl;//队列中元素出完后，此时size()应该为0cout << "size of q:" << q.size() << endl;return 0;
}

运行结果：
 

从打印结果上看，队列遵循先进先出原则。 

三、模拟实现

在前文中提到过stack和queue不是真正意义上的容器，它们是容器适配器。容器适配器到底是什么意思？我们先来了解一下适配器。

适配器是一种设计模式(设计模式是一套被反复使用的、多数人知晓的、经过分类编目的、代码设
计经验的总结)，该种模式是将一个类的接口转换成客户希望的另外一个接口。

适配器就相当于一个转换接口，把一个东西转换成另外一个进行使用。顺便说一下，迭代器也是一种设计模式。

讲到这可能大家听不懂，不要担心，下面在模拟实现stack和queue时会让大家领略到适配器的作用的。

1、stack的模拟实现

栈的核心要求就是后进先出，那我们能不能用其他容器封装转换一下实现栈的效果呢？

因为栈是后进先出，如果容器支持在一端插入和删除，就可以实现栈的效果！vector和list都可以支持在一端插入和删除，所以用vector或list封装一下就可以实现栈的效果，如果我们显示写vector或list就把栈给写死了，要么栈是数组栈，要么栈是链式栈。我们可以多加一个模板参数，来控制输入的容器类型。

请看代码：

//用blue这个命名空间包起来是为了防止和库中的stack发生冲突
namespace blue
{//T是栈中元素类型，Container适配转换出stacktemplate<class T,class Container>class stack{public:void push(const T& x){_con.push_back(x);}void pop(){_con.pop_back();}const T& top() const{return _con.back(); //这里不能用[]来获取数据，因为Contain有可能是list类型的容器，vector和list都有back接口，所以我们直接调用back接口即可}size_t size() const{return _con.size();}bool empty() const{return _con.empty();}private:Container _con;};
}

有了适配器模式，就不需要手动实现一个栈了，直接调用其他容器的接口即可，也不用单独写构造函数了，因为_con是自定义类型，会调自定义类型的构造函数。 这里的Container既可以传vector<T>又可以传list<T>，这就是写成模板参数的好处。

我们就可以这样调用：

int main()
{blue::stack<int, vector<int>> st; //数组栈blue::stack<int, list<int>> st;	 //链式栈return 0;
}

这样写是没问题的，但每次实例化出一个栈时类型名都要写那么长，有点累，所以我们可以给第二个模板参数缺省值：

template<class T,class Container = vector<T>> //给一个缺省值
class stack
{};

实例化时就可以缩短代码：

int main()
{blue::stack<int> st; //默认是数组栈，如果就想要是链式栈，我们也可以传参return 0;
}

库里的stack其实也是这样定义的，但它给的缺省值是deque<T>，至于deque是什么，为什么要用deque做缺省值，我们下面会讲到。

stack已经模拟完毕，我们来写一段代码测试一下：

int main()
{blue::stack<int,vector<int>> st;st.push(1);st.push(2);st.push(3);cout << "size of st:" << st.size() << endl;while (!st.empty()){cout << st.top() << " ";  st.pop();}cout << endl;cout << "size of st:" << st.size() << endl; return 0;
}

运行结果： 

用链式栈也来验证一下：

int main()
{blue::stack<int,list<int>> st; //这里换为listst.push(1);st.push(2);st.push(3);cout << "size of st:" << st.size() << endl;while (!st.empty()){cout << st.top() << " ";  st.pop();}cout << endl;cout << "size of st:" << st.size() << endl; return 0;
}

运行结果： 

照样没问题，这就是模板参数的优点，同样地也体会到了适配器的优点。 

2、queue的模拟实现

queue与stack的不同点显而易见，queue是先进先出，stack是后进先出，我们只需在stack的基础上进行修改即可：

namespace blue
{ //T是栈中元素类型，Container适配转换出queuetemplate<class T, class Container = list<T>>class queue{public:void push(const T& x){_con.push_back(x);}void pop(){_con.pop_front(); //vector没有这个接口}const T& front() const{return _con.front();}const T& back() const{return _con.back();}size_t size() const{return _con.size();}bool empty() const{return _con.empty();}private:Container _con;};
}

这里需要注意的是，队列在删除时是在头部位置删除的，而vector容器没有直接的头删接口，其次vector头删的效率没有list的好，所以我们尽量用list来适配而不用vector。 

queue已经模拟完毕，我们来写一段代码测试一下：

int main()
{blue::queue<int> q;q.push(1);q.push(2);q.push(3);cout << "size of q:" << q.size() << endl;cout << "front element of q:" << q.front() << endl;cout << "back element of q:" << q.back() << endl;while (!q.empty()){cout << q.front() << " ";q.pop();}cout << endl;cout << "size of q:" << q.size() << endl;return 0;
}

运行结果：

 

结果没有任何问题。

stack和queue是没有迭代器的，因为它们在添加或删除元素是有规则的，如果有迭代器，那就可能会乱了规则！其次严格上它们并不是容器，而是容器适配器，只有容器才有迭代器。

四、deque容器

deque是一个容器，它被称为双端队列，但它与queue没有关系，它是一种双开口的"连续"空间的数据结构，双开口的含义是：可以在头尾两端进行插入和删除操作，且时间复杂度为O(1)，与vector比较，头插效率高，不需要搬移元素；与list比较，空间利用率比较高。

它是一个模板，第一个模板参数是T表示容器内数据类型，第二个模板参数是空间配置器，我们本篇不涉及空间适配器，使用时暂时只传第一个参数，第二个参数用缺省值。 

deque其实就是一个"缝合怪"，它将vector和list的接口融合起来，形成一个新的容器，它既支持下标随机访问，又直接支持头尾数据的插入和删除。

产生deque的原因是由于vector和list的优缺点明显：

vector

优点：

1、尾插尾删效率不错，支持高效的下标随机访问

2、物理空间连续，所以高速缓存利用率高

缺点：

1、空间需要扩容，越到后面扩容代价越大(效率和空间浪费)

2、头部和中间的插入或删除效率低

 list

优点：

1、按需申请释放空间，不需要扩容

2、任意位置插入删除效率挺高

缺点：

1、不支持下标随机访问

2、物理空间不连续，所以高速缓存利用率低

deque试图将它们两个的优缺点融合起来，最终deque的结局肯定是失败的，如果成功了还会有vector和list吗？我们来看一下它是怎么失败的：

deque底层结构：

deque并不是真正连续的空间，而是由一段段连续的小空间拼接而成的，像这样：

它不像vector那样是一整片连续的空间，也不像list那样是一个个短小的空间，那它是怎么管理这篇空间的呢？

它是用一个中控数组来进行管理的，它是一个指针数组，它有个特点是从中间开始存储(第一个buff在中间位置，后面会讲到这样做的好处)，每个指针指向不同的buff，它的大致过程是：添加数据会开一个buff，buff如果满了再开另外一个buff，这样就减少了空间申请的频率，它这么做就是尽量弥补vector和list的缺点。

当中控数组满了，它也会扩容的，会另外开辟一块更大的空间，将原先的中控数组的数据拷贝给新开辟的空间，中控数组里面存放的是指针，所以拷贝起来效率也不低。

那么deque是如何支持随机访问，头插尾插等这些操作呢？

要想完成这些功能，靠的就是它的迭代器，它的迭代器比较复杂，我们往下来看：

 它的迭代器由4部分组成，cur指向当前buff中某个数据的位置，first和last分别指向当前buff的起始位置(第一个数据的位置)和结束位置(最后一个数据的下一位置)，用first和last来管理当前buff，node则是保存当前buff的地址(数组中当前指针的地址)。

如果数据的类型是T，那么cur、first、last的类型是T*，node的类型是T**。

它是这样管理这片空间的：

它有一个start和finish分别是第一个buff和最后一个buff的迭代器， first和last是管理当前的buff的，start中的cur是指向第一个数据的位置，finish中的cur是指向最后一个数据的下一位置(last是指向整个buff的最后位置，此时的cur和last指向一样)。

如果定义一个迭代器it，那么*it底层就是*cur，++it底层就是++cur。如果当前cur指向当前buff的最后一个位置了，再进行++，那么cur就到了下一个buff的起始位置了(因为知道当前node，所以node+1就是下一个buff的位置，解引用就是下一个buff的起始位置，然后更新cur，first，last，node)。

deque主要是靠start和finish这两个迭代器维持的，还有一个size，用来记录中控数组的元素个数，如果满了需要扩容。

尾插的逻辑，先看finish中cur是否等于last，如果不相等，那么直接尾插即可，如果相等，再看中控数组有没有满，如果没满，就在当前buff的下一位置(node+1)处开辟一个新的buff，更新finish，插入数据。如果插入前中控数组满了，就需要扩容了。

头插的逻辑，我们在上面说到第一个buff是在中控数组的中间位置，这就有利于进行头插操作，提前预留一部分空间，专门用于进行头插。它的过程就是，首次头插时，需要在当前buff的上一位置(node-1)处开辟一个新的buff，更新start，注意此时是从当前buff(更新后start管理的buff)的最后位置(last)前开始插入，如果cur不等于first就可以不断地头插。

因为deque是支持下标随机访问的，所以它的底层肯定是重载了下标访问操作符[]，它的[]的实现，其实是依靠迭代器的[]来实现的，而迭代器的[]，又是依靠重载+实现的，重载+又是依靠重载+=实现的，这里放上一段源码供大家参考一下，细节不懂的地方暂且可以不用深究：

deque在进行下标访问时会有一定的消耗，首先它要确定第一个buff数据是否满了，其次还要它是在哪个具体的buff中的第几个数据，这和vector相比那就差远了。 

deque的头插和尾插的效率要比vector和list要好的多。

list在头插和尾插时要不断的申请空间，而deque当finish的buff没有满时直接插入，若finish的buff满了只用申请一次即可。好比一共要申请40字节的空间，一次申请40个字节要比分10次申请4个字节的效率更高，它的缓存利用率也比list要好。

对于vector而言，它的扩容代价比较大(越到后面数据量越大，扩容的代价随之增大)，对于deque而言，当finish的buff没有满时直接插入，若finish的buff满了申请空间，只有当中控数组满了才进行扩容，它扩容的代价也不大，因为中控数组里面都是指针，只拷贝些许指针。

但当deque进行erase和insert操作时那就麻烦了，在指定位置插入和删除数据时，有两个选择：1、挪动所有buff，假设在第一个buff删除数据时，所有buff中的数据统统向前挪动一次，这样的效率和vector没有区别，效率很低，在第一个buff插入数据时，所有buff中的数据统统向后挪动一次，这样的效率和vector没有区别，效率很低。

2、只挪动当前buff，假设在第一个buff删除数据时，当前buff中的数据统统向前挪动一次，在第一个buff插入数据时，当前buff中的数据统统向后挪动一次，结果是每个buff的数据个数会不一致，这会导致调用[]时的效率进一步下降，如果每个buff数据个数一样(假设都为10个)，要想算第25个数据的位置那是比较容易的，先用25/10算出来在第几个buff中，再用25%10算出来在buff中的具体哪个位置，如果每个buff数据不一致，那算起来就非常麻烦。所以大多数厂商在实现库中的deque的是保持buff数据个数一致进行erase和insert的。

总结：

1. deque头插尾插效率很高，更甚于vector和list
2. 下标随机访问的效率也不错，但比不上vector
3. 中间插入删除效率很低，要挪动数据，时间复杂度是O(N)

deque也不适合遍历，因为在遍历时，deque的迭代器要频繁的去检测其是否移动到某段小空间的边界，导致效率低下，而序列式场景中，可能需要经常遍历，因此在实际中，需要线性结构时，大多数情况下优先考虑vector和list，deque的应用并不多，而目前能看到的一个应用就是，STL用其作为stack和queue的底层数据结构。

stack是一种后进先出的特殊线性数据结构，因此只要具有push_back()和pop_back()操作的线性
结构，都可以作为stack的底层容器，比如vector和list都可以；queue是先进先出的特殊线性数据
结构，只要具有push_back和pop_front操作的线性结构，都可以作为queue的底层容器，比如
list。但是STL中对stack和queue默认选择deque作为其底层容器，主要是因为：

1. stack和queue不需要遍历(因此stack和queue没有迭代器)，只需要在固定的一端或者两端进行操作。
2. 在stack中元素增长时，deque比vector的效率高(扩容时不需要搬移大量数据)；queue中的元素增长时，deque不仅效率高，而且内存使用率高。结合了deque的优点，而完美的避开了其缺陷。
3. stack和queue在进行数据操作时不需要再中间位置插入删除

我们在模拟实现时并没有将deque作为缺省值是因为当时我们还没学习到deque，从现在开始我们统一将deque作为stack和queue的第二个模板参数进行使用。

接下来我们来写一段代码测试deque中的[]和vector中的[]的效率对比：

测试性能在release环境下测，因为在release环境下双方优化最大

#include <iostream>
#include <list>
#include <vector>
#include <deque>
#include <algorithm>
using namespace std;void test_op1()
{srand((unsigned int)time(0));const int 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);
}int main()
{test_op1();return 0;
}

运行结果：

在数据相同，排序算法相同的条件下，deque的效率不如vector。 (排序算法的底层是快排，快排会用到大量的[])。

我们再来看下一组测试：

void test_op2()
{srand((unsigned int)time(0));const int N = 1000000;deque<int> dq1;deque<int> dq2;for (int i = 0; i < N; ++i){auto e = rand() + i;dq1.push_back(e);dq2.push_back(e);}int begin1 = clock();sort(dq1.begin(), dq1.end());int end1 = clock();int begin2 = clock();// 拷贝到vectorvector<int> v(dq2.begin(), dq2.end());sort(v.begin(), v.end()); //在vector中进行排序dq2.assign(v.begin(), v.end()); //排完序在拷贝回去int end2 = clock();printf("deque sort:%d\n", end1 - begin1);printf("deque copy vector sort, copy back deque:%d\n", end2 - begin2);
}int main()
{test_op2();return 0;
}

运行结果： 

 从结果上看，deque的[]效率明显比vector的[]低。

五、优先级队列

1、基本使用

优先队列也是一种容器适配器(它和queue和deque没有关系)，它的优先级体现在top和pop上，当取元素时(top)默认大的元素优先原则，当删除元素时(pop)默认大的元素先删除的优先原则。这个优先原则是根据第三个模板参数的缺省值决定的，这个缺省值是仿函数，下面会讲到，讲此之前可以先忽略不看。

下面是它常用的接口：

成员函数名称	功能介绍
size()	返回优先级队列中元素个数
empty()	检测优先级队列是否为空，是返回true，否则返回false
top()	默认返回优先级队列中最大元素
pop()	默认删除优先级队列中最大元素
push()	在优先级队列中插入一个元素

以上5个接口是比较常用到的，我们针对以上5个接口写一段代码来介绍它们的使用及效果：

#include <iostream>
#include <queue>  //使用priority_queue要包<queue>这个头文件
using namespace std;int main()
{priority_queue<int,vector<int>> pq;pq.push(4);pq.push(1);pq.push(5);pq.push(7);pq.push(9);cout << "size of pq:" << pq.size() << endl;while (!pq.empty()){cout << pq.top() << " ";pq.pop();}cout << endl;cout << "size of pq:" << pq.size() << endl;return 0;
}

运行结果：

默认优先取大数，默认优先出大数。

它能做到默认取大数或删除大数是因为它的底层是堆，用堆进行选数的效率高，大家如果不了解堆这一数据结构可以先去看看这篇文章 -> 数据结构---堆 ，如果没有看，可能会看不懂下面的代码。

建大堆或者建小堆，可以实现优先取大数或者小数。

堆的底层是数组，所以priority_queue的默认适配容器是vector，也可以用deque但我们上面验证过了，deque在进行排序时(要进行下标访问)的效率不及vector，所以用vector容器作为优先级队列(priority_queue)的默认适配容器。

2、模拟实现

优先级队列的核心在于top，pop和push这三个成员函数，我们先看模拟实现的代码：

#include <iostream>
#include <list>
#include <vector>
#include <deque>
#include <algorithm>
using namespace std;namespace blue
{template<class T,class Container = vector<T>>class priority_queue{public://向上调整算法，算法逻辑是建大堆void AdjustUp(int child){int parent = (child - 1) / 2;//利用父节点和子节点的关系，求得父节点的下标while (child > 0){if (_con[parent] > _con[child])break;else{std::swap(_con[child], _con[parent]);child = parent;parent = (child - 1) / 2;}}}void push(const T& x){//插入数据前，原先数据已经是堆了_con.push_back(x);//向上调整AdjustUp(_con.size() - 1);}//向下调整算法，算法逻辑是建大堆void AdjustDown(int parent){size_t child = parent * 2 + 1; //找出左孩子节点的下标while (child < _con.size()) //看是否越界，若越界则不进入循环{if (child + 1 < _con.size() && _con[child + 1] > _con[child]) //保证右孩子也在界内++child;if (_con[parent] > _con[child])  //此时a[child]就是两个子节点的较小值break;else{std::swap(_con[parent], _con[child]);parent = child;child = parent * 2 + 1;}}}void pop(){std::swap(_con[0], _con[_con.size() - 1]);_con.pop_back();//向下调整AdjustDown(0);}const T& top(){return _con[0];}size_t size() const{return _con.size();}bool empty() const{return _con.empty();}private:Container _con;};
}

内容整体是在一个名为blue的命名空间下完成的，其目的是防止和库中的priority_queue发生名称冲突。

我们来测试一下：

int main()
{blue::priority_queue<int> pq; //调用我们自己实现的优先级队列pq.push(4);pq.push(1);pq.push(5);pq.push(7);pq.push(9);cout << "size of pq:" << pq.size() << endl;while (!pq.empty()){cout << pq.top() << " ";pq.pop();}cout << endl;cout << "size of pq:" << pq.size() << endl;return 0;
}

运行结果： 

结果没有问题，唯一一点不同的是：库中的priority_queue它的模板中有第三个模板参数，而我们实现的时候并没有提供第三个模板参数，没有提供的坏处就是我们把代码写"死"了，上面模拟实现的代码底层只能是大堆，优先出大数或优先删大数，如果想要优先出小数或优先删小数，那就必须修改代码，这在实际生活中可是不行的，比如上网购物，默认价格是从低到高，你却想价格是从高到低，难不成客服会给你说，“你等一下，我让相关程序员修改一下代码”，这种话吗？显然是不行的，如果实现两个堆会有大量的代码重复，所以库中的priority_queue提供了第三个模板参数，它就是仿函数，接下来就看一看仿函数的用法吧！

3、仿函数

仿函数本质是一个类，它的典型特点就是重载了()，这里的()是函数调用时的括号，它的对象可以像函数一样使用。它的基本写法如下：

class Less
{
public:bool operator()(int x, int y){return x < y;}
};

大多数情况下，这个类中没有成员变量。我们也可以将它变成模板，使其适应更多类型：

template <class T>
class Less
{
public:bool operator()(const T& x, const T& y){return x < y;}
};

我们可以这样调用：

int main()
{Less<int> LessFunc;cout << LessFunc(1, 2) << endl; //LessFunc被称为函数对象//本质上是这样调用的cout << LessFunc.operator()(1,2) << endl; return 0;
}

只看第二行代码，是不是觉得它像一个函数调用，所以说这个类的对象可以像函数一样使用，但它不是真正意义上的函数，所以它被称为仿函数。

那它到底用在什么地方呢？

我们以冒泡排序为例，来说明仿函数的用处：

//冒泡排序，升序
void BubbleSort(int* a, int n)
{for (int i = 0;i < n - 1;i++){int flag = 1;for (int j = 0;j < n - 1 - i;j++){if (a[j] > a[j + 1]) // "> 排升序"、"< 排降序"{std::swap(a[j], a[j + 1]);flag = 0;}}if (flag == 1)break;}
}

这是一个简单的冒泡排序，这里排的是升序，现在如果想要排降序，总不能修改代码或者再写一份吧，所以这里就要使用仿函数来达到控制">"和"<"的目的。请看代码：

#include <iostream>
using namespace std;template <class T>
class Less
{
public:bool operator()(const T& x, const T& y){return x < y;}
};template <class T>
class Greater
{
public:bool operator()(const T& x, const T& y){return x > y;}
};template <class Compare>
void BubbleSort(int* a, int n, Compare com)
{for (int i = 0;i < n - 1;i++){int flag = 1;for (int j = 0;j < n - 1 - i;j++){//if (a[j] > a[j + 1]) // "> 排升序"、"< 排降序"if (com(a[j], a[j + 1])) // "> 排升序"、"< 排降序"{std::swap(a[j], a[j + 1]);flag = 0;}}if (flag == 1)break;}
}int main()
{int a[] = { 2,3,7,1,4,6,9,0,5,8 };int sz = sizeof(a) / sizeof(a[0]);BubbleSort(a, sz, Greater<int>()); //第三个参数可以直接传匿名对象for (auto e : a)cout << e << " ";cout << endl;BubbleSort(a, sz, Less<int>()); //第三个参数可以直接传匿名对象for (auto e : a)cout << e << " ";cout << endl;return 0;
}

运行结果：

我们通过控制第三个参数为不同的仿函数对象，就可以达到同一份代码既可以排升序，又可以排降序。

4、改进

了解了仿函数我们就可以对刚刚模拟的优先级队列的代码进行改进，使它产生第三个模板参数来控制大数优先还是小数优先。只修改向上调整算法和向下调整算法即可，因为只有它们中有比较逻辑。

改进后代码：

#include <iostream>
#include <list>
#include <vector>
#include <deque>
#include <algorithm>
using namespace std;namespace blue
{template <class T>class Less{public:bool operator()(const T& x, const T& y){return x < y;}};template <class T>class Greater{public:bool operator()(const T& x, const T& y){return x > y;}};template<class T,class Container = vector<T>,class Compare = Less<T>>class priority_queue{public://向上调整算法，算法默认逻辑是建大堆void AdjustUp(int child){Compare com;int parent = (child - 1) / 2;while (child > 0){//if (_con[parent] > _con[child])//if ( _con[child] <  _con[parent])if (com(_con[child], _con[parent]))break;else{std::swap(_con[child], _con[parent]);child = parent;parent = (child - 1) / 2;}}}void push(const T& x){_con.push_back(x);AdjustUp(_con.size() - 1);}//向下调整算法，算法默认逻辑是建大堆void AdjustDown(int parent){Compare com;size_t child = parent * 2 + 1; while (child < _con.size()) {//if (child + 1 < _con.size() && _con[child + 1] > _con[child]) if (com(child + 1, _con.size()) && com(_con[child], _con[child + 1])){++child;}//if (_con[parent] > _con[child]) if (com(_con[child], _con[parent]))break;else{std::swap(_con[parent], _con[child]);parent = child;child = parent * 2 + 1;}}}void pop(){std::swap(_con[0], _con[_con.size() - 1]);_con.pop_back();//向下调整AdjustDown(0);}const T& top(){return _con[0];}size_t size() const{return _con.size();}bool empty() const{return _con.empty();}private:Container _con;};
}

测试代码：

int main()
{blue::priority_queue<int,vector<int>,blue::Less<int>> pq; //大数优先pq.push(4);pq.push(1);pq.push(5);pq.push(7);pq.push(9);cout << "size of pq:" << pq.size() << endl;while (!pq.empty()){cout << pq.top() << " ";pq.pop();}cout << endl;cout << "size of pq:" << pq.size() << endl;return 0;
}

运行结果：

上面的测试代码是大数优先，接下来看看小数优先：

int main()
{blue::priority_queue<int,vector<int>,blue::Greater<int>> pq; //小数优先pq.push(4);pq.push(1);pq.push(5);pq.push(7);pq.push(9);cout << "size of pq:" << pq.size() << endl;while (!pq.empty()){cout << pq.top() << " ";pq.pop();}cout << endl;cout << "size of pq:" << pq.size() << endl;return 0;
}

运行结果： 

 

实现大数优先或者小数优先只需更改第三个模板参数即可，这就是仿函数的作用。

我们平时可以不用单独写Less和Greater这两个仿函数，C++标准库已经给我们实现了，我们直接用就行。

template <class T> struct less : binary_function <T,T,bool> {bool operator() (const T& x, const T& y) const {return x<y;}
};

template <class T> struct greater : binary_function <T,T,bool> {bool operator() (const T& x, const T& y) const {return x>y;}
};

5、再探仿函数

 库里已经实现了greater和less这两个仿函数，那我们在任何情况下还需要单独再写吗？

我们先来看一段代码：

#include <iostream>
#include <queue>
using namespace std;class Date
{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){}bool operator<(const Date& d)const{return (_year < d._year) ||(_year == d._year && _month < d._month) ||(_year == d._year && _month == d._month && _day < d._day);}bool operator>(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;
}int main()
{priority_queue<Date> q1;q1.push(Date(2018, 10, 29));q1.push(Date(2018, 10, 28));q1.push(Date(2018, 10, 30));cout << q1.top() << endl;return 0;
}

这段代码可以跑通吗？答案是可以的，因为默认的less缺省参数不支持自定义类型比较大小，但我们在Date类中重载了大于号和小于号所以这段代码也没问题，但如果类中没重载大于号和小于号那么程序就跑不起来。 如果自定义类中没有实现重载大于和小于，那就需要我们自己写，强制去重载一个大于和小于，前提是可以获取到类中的成员变量。

现在将上述测试代码补充一些，看看还能跑通吗：

int main()
{priority_queue<Date> q1;q1.push(Date(2018, 10, 29));q1.push(Date(2018, 10, 28));q1.push(Date(2018, 10, 30));cout << q1.top() << endl;q1.pop();cout << q1.top() << endl;q1.pop();cout << q1.top() << endl;q1.pop();cout << "--------------------" << endl;priority_queue<Date*> q2;q2.push(new Date(2018, 10, 29));q2.push(new Date(2018, 10, 28));q2.push(new Date(2018, 10, 30));cout << *q2.top() << endl;q2.pop();cout << *q2.top() << endl;q2.pop();cout << *q2.top() << endl;q2.pop();return 0;
}

q1中存放的是Date类型数据，q2中存放的是Date*类型的数据，看一下运行结果：

代码可以跑通，但打印的数据有点问题，再运行一次看看：

 

不难发现，q2在打印数据时每次打印的结果不一样，这是由于在new的过程中分配的地址是不固定的，可能先new的地址大也可能先new的地址小，所以通过底层仿函数less比较，会出现每次打印结果不同的效果。这样是不行的，所以我们必须自己写仿函数。代码如下：

class DateLess
{
public:bool operator()(Date* p1, Date* p2){return *p1 < *p2; //这里用了Date类中的operator<}
};

再次调用：

int main()
{priority_queue<Date*, vector<Date*>, DateLess> q2;q2.push(new Date(2018, 10, 29));q2.push(new Date(2018, 10, 28));q2.push(new Date(2018, 10, 30));cout << *q2.top() << endl;q2.pop();cout << *q2.top() << endl;q2.pop();cout << *q2.top() << endl;q2.pop();return 0;
}

运行结果：

这样，每次打印结果都是一致的。 

需要我们自己实现仿函数的场景：

1、类类型不支持比较大小 

2、支持比较大小，但是比较的逻辑不符合我们需求

六、结语

本篇内容到这里就结束了，主要讲了stack和queue的使用和模拟实现以及deque容器和优先级队列，希望对大家有所帮助，祝大家天天开心！