目录
1. stack和queue的介绍和使用
1.1 stack
1.1.1 stack的定义方式
1.1.2 stack的使用
1.2 queue
1.2.1 queue的定义方式
1.2.2 queue的使用
2. stack和queue的模拟实现
2.1 容器适配器
2.2 stack的模拟实现
2.3 queue的模拟实现
3. priority_queue的使用
3.1 priority_queue的介绍
3.2 priority_queue的定义方式
3.3 priority_queue的使用
4. priority_queue的模拟实现
4.1 堆的向上调整算法
4.2 堆的向下调整算法
4.3 priority_queue的模拟实现
1. stack和queue的介绍和使用
1.1 stack
stack是一种容器适配器，专门用在具有后进先出操作的上下文环境中，其只能从容器的一端进行元素的插入与提取操作。
1.1.1 stack的定义方式
1.1.2 stack的使用
#include <iostream>
#include <vector>
#include <stack>
using namespace std;int main()
{stack<int, vector<int>> st;st.push(1);st.push(2);st.push(3);st.push(4);cout << st.size() << endl; //4while (!st.empty()){cout << st.top() << " ";st.pop();}cout << endl; //4 3 2 1return 0;
}
1.2 queue
队列是一种容器适配器，专门用在具有先进先出操作的上下文环境中，其只能从容器的一端插入元素，另一端提取元素。
1.2.1 queue的定义方式
1.2.2 queue的使用
#include <iostream>
#include <list>
#include <queue>
using namespace std;
int main()
{queue<int, list<int>> q;q.push(1);q.push(2);q.push(3);q.push(4);cout << q.size() << endl; //4while (!q.empty()){cout << q.front() << " ";q.pop();}cout << endl; //1 2 3 4return 0;
}2. stack和queue的模拟实现
2.1 容器适配器
stack和queue有一点需要注意的是，虽然stack和queue中也可以存放元素，但在STL中并没有将其划分在容器的行列，而是将其称为容器适配器，这是因为stack和queue只是对其他容器的接口进行了包装，STL中stack和queue默认使用deque容器。
在stack和queue的类模板声明当中我们就可以看到，它们的模板参数有两个，第一个是stack和queue当中所存储的元素类型，而另一个就是指定使用的容器类型。只不过当我们不指定使用何种容器的情况下，stack和queue都默认使用deque作为指定容器。
这里简单介绍一下deque这个容器：
deque(双端队列)：是一种双开口的"连续"空间的数据结构，双开口的含义是：可以在头尾两端 进行插入和删除操作，且时间复杂度为O(1)，与vector比较，头插效率高，不需要搬移元素；与 list比较，空间利用率比较高。
关于deque，大家了解即可，它的底层结构比较复杂，这里不做赘述。
我们借此来说明一下vector、list、deque三种容器的优缺点及联系。
简单理解： 学过数据结构后我们都知道，stack和queue既可以使用顺序表实现，也可以使用链表实现。在这里我们若是定义一个stack，并指定使用vector容器，则定义出来的stack实际上就是对vector容器进行了包装。
2.2 stack的模拟实现
namespace cl //防止命名冲突
{template<class T, class Container = std::deque<T>>class stack{public://元素入栈void push(const T& x){_con.push_back(x);}//元素出栈void pop(){_con.pop_back();}//获取栈顶元素T& top(){return _con.back();}const T& top() const{return _con.back();}//获取栈中有效元素个数size_t size() const{return _con.size();}//判断栈是否为空bool empty() const{return _con.empty();}//交换两个栈中的数据void swap(stack<T, Container>& st){_con.swap(st._con);}private:Container _con;};
}
2.3 queue的模拟实现
namespace cl //防止命名冲突
{template<class T, class Container = std::deque<T>>class queue{public://队尾入队列void push(const T& x){_con.push_back(x);}//队头出队列void pop(){_con.pop_front();}//获取队头元素T& front(){return _con.front();}const T& front() const{return _con.front();}//获取队尾元素T& back(){return _con.back();}const T& back() const{return _con.back();}//获取队列中有效元素个数size_t size() const{return _con.size();}//判断队列是否为空bool empty() const{return _con.empty();}//交换两个队列中的数据void swap(queue<T, Container>& q){_con.swap(q._con);}private:Container _con;};
}
3. priority_queue的使用
3.1 priority_queue的介绍
优先级队列默认使用vector作为其底层存储数据的容器，在vector上又使用了堆算法将vector中的元素构造成堆的结构，因此priority_queue就是堆，所有需要用到堆的位置，都可以考虑使用priority_queue。
注意：priority_queue默认状态下是大堆。
3.2 priority_queue的定义方式
3.3 priority_queue的使用
#include <iostream>
#include <queue>
#include<vector>
using namespace std;
int main()
{priority_queue<int> q;//priority_queue<int,vector<int>,greater<int>> q;q.push(3);q.push(6);q.push(0);q.push(2);q.push(9);q.push(8);q.push(1);while (!q.empty()){cout << q.top() << " ";q.pop();}cout << endl; //9 8 6 3 2 1 0return 0;
}4. priority_queue的模拟实现
priority_queue的底层实际上就是堆结构，实现priority_queue之前，我们先认识两个重要的堆算法。（下面这两种算法我们均以大堆为例）。
4.1 堆的向上调整算法
以大堆为例，堆的向上调整算法就是在大堆的末尾插入一个数据后，经过一系列的调整，使其仍然是一个大堆。
调整的基本思想如下：
1、将目标结点与其父结点进行比较。
2、若目标结点的值比父结点的值大，则交换目标结点与其父结点的位置，并将原目标结点的父结点当作新的目标结点继续进行向上调整；若目标结点的值比其父结点的值小，则停止向上调整，此时该树已经是大堆了。
例如，现在我们在该大堆的末尾插入数据88。
我们先将88与其父结点54进行比较，发现88比其父结点大，则交换父子结点的数据，并继续进行向上调整。
此时将88与其父结点87进行比较，发现88还是比其父结点大，则继续交换父子结点的数据，并继续进行向上调整。
这时再将88与其父结点89进行比较，发现88比其父结点小，则停止向上调整，此时该树已经就是大堆了。
代码实现：
//堆的向上调整（大堆）
void AdjustUp(vector<int>& v, int child)
{int parent = (child - 1) / 2; //通过child计算parent的下标while (child > 0)//调整到根结点的位置截止{if (v[parent] < v[child])//孩子结点的值大于父结点的值{//将父结点与孩子结点交换swap(v[child], v[parent]);//继续向上进行调整child = parent;parent = (child - 1) / 2;}else//已成堆{break;}}
}
4.2 堆的向下调整算法
以大堆为例，使用堆的向下调整算法有一个前提，就是待向下调整的结点的左子树和右子树必须都为大堆。
调整的基本思想如下：
1、将目标结点与其较大的子结点进行比较。
2、若目标结点的值比其较大的子结点的值小，则交换目标结点与其较大的子结点的位置，并将原目标结点的较大子结点当作新的目标结点继续进行向下调整；若目标结点的值比其较大子结点的值大，则停止向下调整，此时该树已经是大堆了。
例如，将该二叉树从根结点开始进行向下调整。（此时根结点的左右子树已经是大堆）
将60与其较大的子结点88进行比较，发现60比其较大的子结点小，则交换这两个结点的数据，并继续进行向下调整。
此时再将60与其较大的子结点87进行比较，发现60比其较大的子结点小，则再交换这两个结点的数据，并继续进行向下调整。
这时再将60与其较大的子结点54进行比较，发现60比其较大的子结点大，则停止向下调整，此时该树已经就是大堆了。
代码实现：
//堆的向下调整（大堆）
void AdjustDown(vector<int>& v, int n, int parent)
{//child记录左右孩子中值较大的孩子的下标int child = 2 * parent + 1;//先默认其左孩子的值较大while (child < n){if (child + 1 < n&&v[child] < v[child + 1])//右孩子存在并且右孩子比左孩子还大{child++;//较大的孩子改为右孩子}if (v[parent] < v[child])//左右孩子中较大孩子的值比父结点还大{//将父结点与较小的子结点交换swap(v[child], v[parent]);//继续向下进行调整parent = child;child = 2 * parent + 1;}else//已成堆{break;}}
}
4.3 priority_queue的模拟实现
namespace cl //防止命名冲突
{//比较方式（使内部结构为大堆）template<class T>struct less{bool operator()(const T& x, const T& y){return x < y;}};//比较方式（使内部结构为小堆）template<class T>struct greater{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){int parent = (child - 1) / 2; //通过child计算parent的下标while (child > 0)//调整到根结点的位置截止{if (_comp(_con[parent], _con[child]))//通过所给比较方式确定是否需要交换结点位置{//将父结点与孩子结点交换swap(_con[child], _con[parent]);//继续向上进行调整child = parent;parent = (child - 1) / 2;}else//已成堆{break;}}}//插入元素到队尾（并排序）void push(const T& x){_con.push_back(x);AdjustUp(_con.size() - 1); //将最后一个元素进行一次向上调整}//堆的向下调整void AdjustDown(int n, int parent){int child = 2 * parent + 1;while (child < n){if (child + 1 < n&&_comp(_con[child], _con[child + 1])){child++;}if (_comp(_con[parent], _con[child]))//通过所给比较方式确定是否需要交换结点位置{//将父结点与孩子结点交换swap(_con[child], _con[parent]);//继续向下进行调整parent = child;child = 2 * parent + 1;}else//已成堆{break;}}}//弹出队头元素（堆顶元素）void pop(){swap(_con[0], _con[_con.size() - 1]);_con.pop_back();AdjustDown(_con.size(), 0); //将第0个元素进行一次向下调整}//访问队头元素（堆顶元素）T& top(){return _con[0];}const T& top() const{return _con[0];}//获取队列中有效元素个数size_t size() const{return _con.size();}//判断队列是否为空bool empty() const{return _con.empty();}private:Container _con; //底层容器Compare _comp; //比较方式};
}
这里的模拟实现用到了仿函数（less，greater），仿函数本质上是一个类，重载了operator()。当我们插入或者弹出数据时，我们都不能破坏其底层的堆结构，所以我们在插入弹出后需要进行调整保证其结构一直是一个堆。