7、基于 deque 的顺序容器适配器

1、stack 的基本概念

Stack 即栈，允许新增元素、移除元素、取得最顶端元素。但除了最顶端外，没有任何其他方法可以存取 stack 的其他元素，换言之，stack 不允许随机访问。可以将 stack 看成是封闭了一端开口的 deque。
将元素插入 stack 的操作称为 push，将元素弹出 stack 的操作称为 pop。Stack 所有元素的进出都必须符合“后进先出”的条件，只有 stack 顶端的元素，才有机会被外界取用。stack 不提供走访功能，也不提供迭代器。

2、堆栈类 stack 的成员函数

stack 实现后进先出的操作，使用时应包含头文件：#include<stack>。
声明一个 stack 对象：std::stack<type,container> stk;
stack 模板类需要两个模板参数，一个是元素类型，一个容器类型，但只有元素类型是必要的。type 为堆栈操作的数据元素类型，container 为实现堆栈所用的容器类型，在不指定容器类型时，默认的容器类型为 deque，还可以为 std::vector 和 std::list。

3、queue 的基本概念

Queue 即普通队列，允许新增元素、移除元素、从最底端加入元素、取得最顶端元素。但除了最底端可以加入、最顶端可以取出，没有任何其他方法可以存取 queue 的其他元素。换言之，queue 不支持随机访问。可以将 queue 看成是封闭了底端的出口和前端的入口的 deque。

4、队列类 queue 的成员函数

Queue 实现先进先出的操作，在使用 queue 时，应包含头文件：#include。
声明一个 queue 对象：std::queue<type,container> que;
与 stack 模板类很相似，queue 模板类也需要两个模板参数，一个是元素类型，一个容器类型，元素类型是必要的，容器类型是可选的，默认为 deque 类型。type 为队列操作的数据类型，container 为实现队列所用的容器类型。

5、priority_queue 的基本概念

在头文件中，还定义了另一个非常有用的模板类，即优先队列 priority_queue。优先队列与队列的差别在于优先队列不是按照入队的顺序出队，而是按照队列中元素的优先权顺序出队（默认为大者优先，也可以通过指定算子来指定自己的优先顺序）。priority_queue 允许用户为队列中存储的元素设置优先级。这种队列不是直接将新元素放置在队列尾部，而是放置在比它优先级低的元素前面，即提供了一种插队策略。标准库默认使用 < 操作符来确定他们之间的优先级关系，即权重大的排在队首。

6、队列类 priority_queue 成员函数

Priority_queue 实现先进先出的操作，优先队列也是队列的一种，在使用 priority_queue 时，应包含头文件：#include<queue>。
priority_queue 的声明：
std::priority_queue<type, container, comp> pri_que;
声明实例：
priority_queue<int, vector<int>, greater<int> > pri_que;
priority_queue 模板类有三个模板参数，第一个是元素类型，第二个是保存数据的容器，第三个是比较方式。其中后两个都可以省略，默认容器为 vector，默认的比较方式是数值上的小于关系，即用 operator<，此时队列中元素由队头到队尾从大到小排列，如果把后面两个参数缺省的话，优先队列就是大根堆，队头元素最大。（注意这里的大根堆并不是数据结构意义上的大根堆。priority_queue 只是保证第一个结点最大）
type 为队列操作的数据类型；container 为实现队列所用的容器类型，必须是用数组实现的容器，比如 vector, deque 但不能用 list；comp 为排队策略。
priority_queue 的基本操作主要有以下几种：

priority_queue<int> q1;  

声明一个优先队列 q1，默认缺省后两个参数即为声明一个大根堆 q1。

typedef pair<long, int> Node;priority_queue< Node, vector< Node >, greater< Node > > Q;

这里可以定义一个结构体或者容器 Node 来存放元素。前两个参数没什么说的，很好理解，其中第三个参数，默认有三种写法，小顶堆：greater、大顶堆：less、如果想自定义优先级而 TYPE 不是基本类型，而是复杂类型，例如结构体、类对象，则必须重载其中的 operator()。
priority_queue 的主要成员函数：

1.priority_queue::empty;

判断队列是否为空（也即是 size 是否为 0），是则返回 true，否则返回 false。优先队列的此成员函数实际上调用底层容器的同名函数。

2.priority_queue::size;

返回队列中元素的个数。此函数实际上调用底层容器的同名函数。这个函数也可以用于判断队列是否为空。

3.priority_queue::top;

返回队头元素的常引用，队头元素是在所设定的比较关系下最大也即优先级最高的元素。此函数实际上调用底层容器的 front 函数。

4.priority_queue::pop;

清除队头元素。

5.priority_queue::push;

给队列插入元素，新元素会按其优先级被排列到适当位置。