在之前的章节我们学习了C++当中string、vector和list三种容器并且试着模拟实现这三种容器，那么接下来在本篇当中我们将STL当中的stack和queue，并且在学习stack和queue的使用之后和之前一样还会试着模拟实现stck和queue。由于stck和queue的模拟实现较为简单因此就不另在其他篇章中讲解。在此我们还要了解到stack和queue是一种容器适配器，那么在这之前就要了解容器适配器是什么。最后我们还要了解一种双端队列的容器，并且分析其与vector和list的区别，那么接下来就开始本篇的学习吧！！！

 1.stack使用介绍

stack - C++ Reference

通过文档就可以看出stack也是C++当中STL当中提供的一种容器，该容器其实就是之前我们在数据结构当中学习到的栈，在此在C++当中是将栈的结构和各种功能实现好，之后我们需要使用时就只需要调用模板库内的stack即可这样就不需要像之前C语言一样显示的自己实现，这样可以大大提升我们的效率

在stack当中提供了以下函数，在此这些函数和之前在数据结构就已经学习过，那么在此就不做讲解，如果你还对栈有疑惑可以数据结构之《栈》通过来查缺补漏

函数说明	接口说明
stack()	构造空的栈
empty()	检测stack是否为空
size()	返回stack中元素的个数
top()	返回栈顶元素的引用
push()	将元素val压入stack中
pop()	将stack中尾部的元素弹出

那么在了解了stack的相关知识点之后接下来就来通过几道算法题来试着使用stck

最小栈

首先实现该算法题的代码之前我们先来分析该如何实现该算法题

该算法题其实就是要我们实现一个类在这个类当中实现以上的成员函数，在此可以看出要在这个类当中除了要实现栈通常的操作还要实现一个函数能完成将栈当中最小的数据返回，接下来就要分析要实现这样的功能要运用什么方法呢？

其实在此要实现一个最小栈的结构我们就可以使用两个stack来实现，其中一个栈PushSt来存储入栈所有的元素，另一个栈MinSt来存储PushSt内的最小元素

那么MinSt怎么才能实现存储PushSt内的最小元素呢？接下来我们就通过一个示例来分析看看

​

 例如以上示例所示要将 4 7 3 5 2 2依次入栈，那么就需要进行以下的操作
 1. 每次数据入栈时都先将元素入PushSt栈

 2.完成1之后查看MinSt内的栈顶元素是否比新插入PushSt内的元素的值要大，若大或者相等就也将插入PushSt内的元素的值插入到MinSt。在此还会有一种特殊情况是当MinSt为空时，无论插入到PushSt内的元素是什么都要再将该元素插入到MinSt

完成了以上操作之后所有元素入栈后两个栈PushSt和MinSt内的情况如下所示：

那么接下来如果要进行最小栈出栈的操作时MinSt内部又应该如何变化呢？
继续来对以上的示例进行出栈的分析

1.当进行出栈操作时候，无论要进行出栈的元素的值是多大都要将PushSt内的栈顶元素出栈

2.之后再比较进行此次出栈时PushSt内的栈顶元素的值是否和PushSt内的栈顶元素值相等，相等就需要也将MinSt内的栈顶元素出栈

通过以上的最小栈需要出栈时的操作就可以保证出栈之后在MinSt内的栈顶元素是PushSt内的最小值
 

完成了算法实现的分析之后接下来就来实现该算法题的代码：

class MinStack 
{
public://构造函数MinStack() {}//入栈void push(int val) {if(MinSt.empty() || val<=MinSt.top()){MinSt.push(val);}PushSt.push(val);}//出栈void pop() {if(PushSt.top()==MinSt.top()){MinSt.pop();}PushSt.pop();}//取栈顶元素int top() {return PushSt.top();}//得到最小的元素值int getMin() {return MinSt.top();}private:std::stack<int> PushSt;std::stack<int> MinSt;
};/*** Your MinStack object will be instantiated and called as such:* MinStack* obj = new MinStack();* obj->push(val);* obj->pop();* int param_3 = obj->top();* int param_4 = obj->getMin();*/

注：在以上的代码当中由于MinStack的成员变量都是自定义类型的变量，那么就就不需要我们显示的写MinStack的构造函数，这是由于在MinStack对象定义时会自动调用stck的构造函数

栈的压入、弹出序列

接下来我们继续来看以下算法题

通过以上的题目描述就可以看出该算法题要我们实现一个函数能判断两个vector对象内的第一个vector内存储的为入栈序列时，第二个序列能为第一个序列的出栈序列，如果能满足条件函数就返回true，否则就返回flase

接下来在实现该算法题代码之前就先来分析这个题的解题思路是什么

在此我们来通过一个示例来分析
当我们要判断[1,2,3,4,5],[4,5,3,2,1]这两个序列第二个序列是否为第一个序列的一种出栈序列时就可以借助栈来判断，具体过程如下所示：

首先创建一个栈st，在分别创建一个变量pushi和popi分别指向第一个和第二个序列的首个元素，接下来进行重复进行以下操作

1.当栈st为空时或者是栈st的栈顶元素不和popi指向的元素相等时就将pushi指向的元素插入到栈st中，之后再pushi++，直到不符合以上为空或者相等的要求为止

2.之后当popi指向的元素和栈st的栈顶元素相等时就将st栈顶元素出栈，之后再将popi++，重复该操作直到不匹配为止，之后再进行以上的操作1

3.以上的操作的结束条件是当pushi走到第一个序列的末尾时就结束操作，这时看栈st是否为空；为空就说明第二个序列不是为第一个序列的一种出栈序列，否则则是

完成了以上操作之后以上示例使用以上方法的判断过程如下所示：

 先是直到pushi指向5为止都没未出现st栈顶的元素和popi指向的元素匹配，那么就要把1到4都入栈

之后st栈顶的元素4和popi指向的元素4匹配，就将st的栈顶元素出栈，之后再将popi++

之后st栈顶的元素和popi指向的元素不匹配就继续将pushi指向的元素入栈

之后st栈顶的元素4和popi指向的元素4匹配，popi++，之后一直符合要求就一直重复该操作

由以上栈st最后再pushi走到第一个序列的末尾时st为空就说明第二个序列是为第一个序列的一种出栈序列

完成了算法实现的分析之后接下来就来实现该算法题的代码：

class Solution {
public:/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param pushV int整型vector * @param popV int整型vector * @return bool布尔型*/bool IsPopOrder(vector<int>& pushV, vector<int>& popV) {std::stack<int> st;int pushi=0,popi=0;while(pushi<pushV.size()){st.push(pushV[pushi]);while(!st.empty() && st.top()==popV[popi]){st.pop();++popi;}++pushi;}return st.empty();}
};

逆波兰表达式求值

通过以上的题目描述就知道了该算法题要我们实现的是对一个逆波兰表达式进行运算，在此的逆波兰表达式其实就是中缀表达式，这时你可能就会有疑惑那么中缀表达式是什么呢？

来看以下示例：
在以下示例当中就是这两个中缀表达式的后缀表达式的形式

在此中缀表达式转后缀表达式的技巧是运算数的顺序不变，运算符按照对应的优先级插入到运算数之后，每个运算符对其前面的两个运算数进行运算，并且在使用后缀表达式计算时是按照从左到右对操作符前面的操作数进行运算的

在了解了中缀表达式以及后缀表达式之后接下来我们就来思考该使用什么方式来解答这道算法题呢？
其实在此还是要用到栈来解决，在此先创建一个栈，之后遇到操作数则入栈；遇到操作符则取出栈顶两个操作数进行计算，并将结果压入栈中

实现的代码如下所示：

class Solution {
public:int evalRPN(vector<string>& tokens) {stack<int> st;for(auto& x:tokens){//当是操作符时if(x=="+" || x=="-" || x=="*" ||x=="/"){int right=st.top();st.pop();int left=st.top();st.pop();switch(x[0]){case('+'):st.push(left+right);break;case('-'):st.push(left-right);break;case('*'):st.push(left*right);break;case('/'):st.push(left/right);break;         }}//当是操作数时else{st.push(stoi(x));}}return st.top();}
};

2.queue使用介绍

queue - C++ Reference

通过文档就可以看出queue也是C++当中STL当中提供的一种容器，该容器其实就是之前我们在数据结构当中学习到的队列，在此在C++当中是将队列的结构和各种功能实现好，之后我们需要使用时就只需要调用模板库内的queue即可这样就不需要像之前C语言一样显示的自己实现，这样可以大大提升我们的效率

在queue当中提供了以下函数，在此这些函数和之前在数据结构就已经学习过，那么在此就不做讲解，如果你还对栈有疑惑可以通过数据结构之《队列》来查缺补漏

函数说明	接口说明
queue()	构造空的队列
empty()	检测队列是否为空，是返回true，否则返回false
size()	返回队列中有效元素的个数
front()	返回队头元素的引用
back()	返回队尾元素的引用
push()	在队尾将元素val入队列
pop()	将队头元素出队列

 那么在了解了stack的相关知识点之后接下来就来通过几道算法题来试着使用queue

用队列实现栈

​

以上的算法题其实在数据结构就写过了，不过在之前我们是使用C语言实现的，那时要解决这道算法题需要我们先自己实现队列的结构，之后才能使用创建两个队列来解决。但在C++中就不用这么繁琐了，我们可以直接调用STL当中的queue来实现，因此我们就只需要实现Mystack内的代码即可，并且该类内的构造函数还不需要我们显示的写

代码如下所示：

class MyStack {
public:MyStack() {}void push(int x) {if(!q1.empty()){q1.push(x);}else{q2.push(x);}}int pop() {int tmp=0;if(!q1.empty()){int n=q1.size();while(--n){q2.push(q1.front());q1.pop();}tmp=q1.front();q1.pop();}else{int n=q2.size();while(--n){q1.push(q2.front());q2.pop();}tmp=q2.front();q2.pop();}return tmp;}int top() {if(!q1.empty()){return q1.back();}else{return q2.back();}}bool empty() {return q1.empty() && q2.empty();}private:queue<int> q1;queue<int> q2;
};/*** Your MyStack object will be instantiated and called as such:* MyStack* obj = new MyStack();* obj->push(x);* int param_2 = obj->pop();* int param_3 = obj->top();* bool param_4 = obj->empty();*/

3.stack和queue的模拟实现

在了解了STL内的stack和queue的使用之后接下来我们来试着模拟实现stack和queue，但在此之前我们要了解什么是容器适配器，这时由于STL内的stack和queue都是容器适配器

什么是适配器

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

例如电脑的充电器其实就是一种电源适配器

​

我们可以通过文档看到STL标准库中stack和queue的底层结构

虽然stack和queue中也可以存放元素，但在STL中并没有将其划分在容器的行列，而是将其称为
容器适配器，这是因为stack和队列只是对其他容器的接口进行了包装，STL中stack和queue默认
使用deque，比如：

​

 ​

 那么在此stack内使用到的deque是什么容器呢，接下来我们就来简单了解一下

1.deque的原理介绍：

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

​

其实deque并不是真正连续的空间，而是由一段段连续的小空间拼接而成的，实际deque类似于一个动态的二维数组，其底层结构如下图所示：

​

双端队列底层是一段假象的连续空间，实际是分段连续的，为了维护其“整体连续”以及随机访问
的假象，落在了deque的迭代器身上，因此deque的迭代器设计就比较复杂，如下图所示：

​

 2.deque的缺陷

那么在了解了deque之后你可能就会有疑惑了，deque这个容器相比vector在中间和头部插入数据有优势，又相比list空间利用率较高，那么是不是用deque就可以替代vector和list了呢？

确实与vector比较，deque的优势是：头部插入和删除时，不需要搬移元素，效率特别高，而且在扩容时，也不需要搬移大量的元素，因此其效率是必vector高的。与list比较，其底层是连续空间，空间利用率比较高，不需要存储额外字段。

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

3.为什么选择deque作为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作为stack和queue的底层默认容器结合了deque的优点，而完美的避开了其缺陷。

了解deque接下来我们就来模拟实现stack和queue

stack：

#include<iostream>
#include<deque>
using namespace std;namespace zhz
{template<class T,class container =deque<T>>class stack{public:size_t size()const{return _st.size();}bool empty()const{return _st.empty();}void push(const T& val){_st.push_back(val);}void pop(){_st.pop_back();}T& top(){return _st.back();}const T& top()const{return _st.back();}private:container _st;};
}

queue：

#include<iostream>
#include<deque>
using namespace std;namespace zhz
{template<class T, class container = deque<T>>class queue{public:size_t size()const{return _qe.size();}bool empty()const{return _qe.empty();}void push(const T& val){_qe.push_back(val);}void pop(){_qe.pop_front();}T& front(){return _qe.front();}T& back(){return _qe.back();}const T& front()const{return _qe.front();}const T& back()const{return _qe.back();}private:container _qe;};
}

4.priority_queue的介绍和使用

4.1 priority_queue的介绍

在queue的文档当中可以看到除了queue还有priority_queue

​

那么priority_queue是什么呢？

其实priority_queue是一种优先队列； 优先队列也是一种容器适配器，根据严格的弱排序标准，它的第一个元素总是它所包含的元素中最大的。并且优先队列类似于堆，在堆中可以随时插入元素，并且只能检索最大堆元素(优先队列中位于顶部的元素)。

并且优先队列和queue一样被实现为容器适配器，容器适配器即将特定容器类封装作为其底层容器类，queue提供一组特定的成员函数来访问其元素。元素从特定容器的“尾部”弹出，其称为优先队列的顶部。

4.2 priority_queue的使用

优先级队列默认使用vector作为其底层存储数据的容器，在vector上又使用了堆算法将vector中
元素构造成堆的结构，因此priority_queue就是堆，所有需要用到堆的位置，都可以考虑使用
priority_queue。注意：默认情况下priority_queue是大堆。

例如以下示例：

#include <vector>
#include <queue>
#include <functional>   // greater算法的头文件void TestPriorityQueue()
{// 默认情况下，创建的是大堆，其底层按照小于号比较vector<int> v{ 3,2,7,6,0,4,1,9,8,5 };priority_queue<int> q1;for (auto& e : v)q1.push(e);cout << q1.top() << endl;// 如果要创建小堆，将第三个模板参数换成greater比较方式priority_queue<int, vector<int>, greater<int>> q2(v.begin(), v.end());cout << q2.top() << endl;
}

接下来来看以下的算法题：

数组中第K个大的元素

通过以上的题目描述可以看出该算法题要我们实现的是将数组当中的第k大的元素找出来，并且实现时间复杂度为 O(n) 的算法解决此问题 

其实在此使用priority_queue就能很轻松的解决该算法题，代码如下所示：
 

class Solution {
public:int findKthLargest(vector<int>& nums, int k) {priority_queue<int> pq;for(auto x:nums){pq.push(x);}while(--k){pq.pop();}return pq.top();}
};

4.3 priority_queue的模拟实现 

在了解了优先队列的使用方式之后接下来就来试着模拟实现priority_queue，并且我们知道优先队列类似于堆，在堆中可以随时插入元素，并且只能检索最大堆元素(优先队列中位于顶部的元素)

那么优先队列的结构以及入队和出队的操作，在此就要用到之前数据结构当中堆相应的知识，代码如下所示

namespace zhz
{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[child] > _con[parent]){swap(_con[child], _con[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}}//向上调整法算法void AdjustDown(int parent){//以上为大堆时的向下调整法算法int child = 2 * parent + 1;while (child < _con.size()){if (child + 1 < _con.size() && _con[child + 1] > _con[child]){child++;}if (_con[child] > _con[parent]){swap(_con[child], _con[parent]);parent = child;child = 2 * parent + 1;}else{break;}}}//入队列void push(const T& x){_con.push_back(x);AdjustUp(_con.size() - 1);}//出队列void pop(){swap(_con[0], _con[_con.size() - 1]);_con.pop_back();AdjustDown(0);}private://底层为vectorcontainer _con;};
}

注：以上使用到向上和向下调整算法以及堆元素的插入和堆顶元素的删除在之前的数据结构堆章节有详细了解过，在此就不再讲解其的原理

注：如果你还对以上的堆相关知识有疑惑看一看之前的数据结构之《二叉树》(中)

在以上的代码我们是实现了默认情况下priority_queue为大堆时的入队列和出队列，但是我们知道STL内实现的priority_queue还可以通过实现对小堆的操作，那么我们该如何修改我们实现的代码呢？
其实在此就要使用到仿函数来实现队列的底层结构是小堆还是大堆，在此实现两个类less和greater类分别实现大堆和小堆构建，并且在这两个类内都实现()的运算符重载函数

实现代码如下所示：
 

template<class T>
struct less
{bool operator()(const T& x1, const T& x2){return x1 < x2;}
};template<class T>
struct greater
{bool operator()(const T& x1, const T& x2){return x1 > x2;}
};

在此我们实现的priority_queue的类模板也要加上第三个参数，在此将该参数命名为compare，并且缺省参数为less<T>。实现了类模板的修改之后在函数内部向上调整和向下调整的函数也要作出修改，修改完的代码如下所示：
 

namespace zhz
{template<class T>struct less{bool operator()(const T& x1, const T& x2){return x1 < x2;}};template<class T>struct greater{bool operator()(const T& x1, const T& x2){return x1 > x2;}};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[child] > _con[parent])if (com( _con[parent],_con[child])){swap(_con[child], _con[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}}void AdjustDown(int parent){compare com;int child = 2 * parent + 1;while (child < _con.size()){//if (child + 1 < _con.size() && _con[child + 1] > _con[child])if(child + 1 < _con.size() && com(_con[child], _con[child + 1])){child++;}//if (_con[child] > _con[parent])if(com(_con[parent], _con[child])){swap(_con[child], _con[parent]);parent = child;child = 2 * parent + 1;}else{break;}}}void push(const T& x){_con.push_back(x);AdjustUp(_con.size() - 1);}void pop(){swap(_con[0], _con[_con.size() - 1]);_con.pop_back();AdjustDown(0);}private:container _con;};
}

之后在对以上代码补充一些构造函数以及取队头元素的代码之后就实现了完整的优先队列模拟实现代码

完整代码 

#pragma once
#include<iostream>
#include<vector>
//#include<queue>
using namespace std;namespace zhz
{template<class T>struct less{bool operator()(const T& x1, const T& x2){return x1 < x2;}};template<class T>struct greater{bool operator()(const T& x1, const T& x2){return x1 > x2;}};template<class T, class container = vector<T>, class compare = less<T>>class priority_queue{public:priority_queue() = default;template<class InputIterator>priority_queue(InputIterator first, InputIterator last):_con(first, last){for (int i = _con.size() - 1 - 1 / 2; i <= 0; i--){AdjustDown(i);}}void AdjustUp(int child){compare com;int parent = (child - 1) / 2;while (child > 0){//if (_con[child] > _con[parent])if (com( _con[parent],_con[child])){swap(_con[child], _con[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}}void AdjustDown(int parent){compare com;int child = 2 * parent + 1;while (child < _con.size()){//if (child + 1 < _con.size() && _con[child + 1] > _con[child])if(child + 1 < _con.size() && com(_con[child], _con[child + 1])){child++;}//if (_con[child] > _con[parent])if(com(_con[parent], _con[child])){swap(_con[child], _con[parent]);parent = child;child = 2 * parent + 1;}else{break;}}}void push(const T& x){_con.push_back(x);AdjustUp(_con.size() - 1);}void pop(){swap(_con[0], _con[_con.size() - 1]);_con.pop_back();AdjustDown(0);}size_t size(){return _con.size();}bool empty(){return _con.empty();}const T& top(){return _con.front();}private:container _con;};
}

对以上代码我们来实现以下代码来测试看看是否正确

#include"priority_queue.h"
class Date
{
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);}friend ostream& operator<<(ostream& _cout, const Date& d){_cout << d._year << "-" << d._month << "-" << d._day;return _cout;}private:int _year;int _month;int _day;
};int main()
{zhz::priority_queue<Date, vector<Date>, zhz::greater<Date>> pq1;pq1.push(Date(2014,11,1));pq1.push(Date(2024,11,5));pq1.push(Date(2024,11,10));pq1.push(Date(2014,9,20));pq1.push(Date(2024,7,1));while (!pq1.empty()){cout << pq1.top() << " ";pq1.pop();}return 0;
}

 在此我们实现的是日期类对象小堆实现，不断取堆顶元素输出结果如下所示：

通过以上输出结果为升序的就说明我们实现的priority_queue的代码没问题

在此我们还有可能会使用以上的形式来创建日期类对象，那么这时是否能实现正确的排序呢？

int main()
{zhz::priority_queue<Date*, vector<Date*>, zhz::greater<Date*>> pq1;pq1.push(new Date{ 2014, 11, 1 });pq1.push(new Date{ 2024, 11, 5 });pq1.push(new Date{ 2024, 11, 10 });pq1.push(new Date{ 2014, 9, 20 });pq1.push(new Date{ 2024, 7, 1 });while (!pq1.empty()){cout << *pq1.top() << " ";pq1.pop();}return 0;
}

我们通过运行该程序就会发现每次输出结果都是不同的，这时为什么呢？

这其实是由于以上是按照地址比较的，但每次new的对象在堆区的存储位置都不一样这就使得会出现每次输出结果都是不同的，那么要怎么才能解决呢？

这就需要我们再显示的相应的类，如下所示：

struct less_dest
{bool operator()(const Date* x1, const Date* x2){return *x1 < *x2;}
};struct greater_dest
{bool operator()(const Date* x1, const Date* x2){return *x1 > *x2;}
};

这时main函数内的代码就变为以下形式：

int main()
{zhz::priority_queue<Date*, vector<Date*>,greater_dest> pq1;//zhz::priority_queue<Date*, vector<Date*>, zhz::greater<Date*>> pq1;pq1.push(new Date{ 2014, 11, 1 });pq1.push(new Date{ 2024, 11, 5 });pq1.push(new Date{ 2024, 11, 10 });pq1.push(new Date{ 2014, 9, 20 });pq1.push(new Date{ 2024, 7, 1 });while (!pq1.empty()){cout << *pq1.top() << " ";pq1.pop();}return 0;
}

这时输出结果就是正确的了：