c++中的Stack与Queue
目录
一·queue与stack：
1.queue介绍：
2.queue模拟实现：
3stack介绍：
4stack模拟实现：
二·priority_queue（优先队列）：
1·介绍：
2·仿函数：
3·模拟实现：
三.容器适配器：
四.deque：
一·queue与stack：
1.queue介绍：
①队列作为容器适配器实现，容器适配器即将特定容器类封装作为其底层容器类，queue提供 一组特定的成员函数来访问其元素。元素从队尾入队列，从队头出队列。
②只要是能满足对队列功能函数实现的容器，都可以作为它的底层容器。
底层容器具备条件：
empty：检测队列是否为空.
size：返回队列中有效元素的个数.
front：返回队头元素的引用.
back：返回队尾元素的引用.
push_back：在队列尾部入队列.
pop_front：在队列头部出队列.
③但是默认的是deque（一种双端队列，后续讲到）。
2.queue模拟实现：
#pragma once
namespace sq {template<class T, class Con = deque<T>>class queue{public:queue() {}void push(const T& x) {_c.push_back(x);}void pop() {_c.pop_front();}T& back() {return _c.back();}const T& back()const {return _c.back();}T& front() {return _c.front();}const T& front()const {return _c.front();}size_t size()const {return _c.size();}bool empty()const {return _c.empty();}private:Con _c;};
}3stack介绍：
同上面queue也是容器适配器，本身不是容器，但是有底层容器，像list，vector这样的容器都可以做，但是默认是deque。
4stack模拟实现：
#pragma once
namespace sq {template<class T, class Con = deque<T>>class stack{public:stack() {}void push(const T& x) {_c.push_back(x);}void pop() {_c.pop_back();}T& top() {return _c.back();}const T& top()const {return _c.back();}size_t size()const {return _c.size();}bool empty()const {return _c.empty();}private:Con _c;};
}二·priority_queue（优先队列）：
1·介绍：
①容器适配器，它的第一个元素是最大的元素。
②理想结构类似于堆，只能访问它的top（访问队头，删队头时候与队尾互换，再删除）。
③底层容器用vector和list都可以，但是一般默认为vector。
④含有的接口函数：
priority_queue()与priority_queue(first, last) 构造一个空的优先级队列，也可以用迭代器区间初始化。
empty( ) 检测优先级队列是否为空，是返回true，否 则返回false。
top( ) 返回优先级队列中最大(最小元素)，即堆顶元 素。
push(x) 在优先级队列中插入元素x。
pop() 删除优先级队列中最大(最小)元素，即堆顶元 素。
2·仿函数：
即一种模版，它重载了operator()；使得该模版类的对象可以像函数一样使用。如：
template<class T>class Great {public:bool operator()(const T& a, const T& b) {return a > b;}};template<class T>class Less {public:bool operator()(const T& a, const T& b) {return a < b;}};
仿函数特性：
在同一时间里，由某个仿函数所代表的单一函数，可能有不同的状态。
仿函数即使定义相同，也可能有不同的类型。
仿函数通常比一般函数速度慢。
仿函数使程序代码变简单。
3·模拟实现：
#pragma once
#include<vector>
namespace pq{template<class T>class Great {public:bool operator()(const T& a, const T& b) {return a > b;}};template<class T>class Less {public:bool operator()(const T& a, const T& b) {return a < b;}};template <class T, class Container = vector<T>, class Compare = pq::Less<T> >//默认less大堆class priority_queue{public://保证原来堆都是有一定大小堆序的，故上调void upadjust(int child) {int parent = (child-1)/2;while (child > 0) {if (com(c[parent],c[child])) {swap(c[child] ,c[parent]);child = parent;parent = (child - 1) / 2;}else {break;}}}void downadjust(int parent) {int child = 2 * parent + 1;while (child<c.size()) {if (child+1<c.size()&&com(c[child], c[child + 1])) {child++;}if (com( c[parent],c[child])) {swap(c[child], c[parent]);parent=child;child = 2 * parent + 1;}else {break;}}}priority_queue() {}template <class InputIterator>priority_queue(InputIterator first, InputIterator last) {while (first != last) {c.push_back(*first);upadjust(c.size() - 1);first++;}}const bool empty() const {return c.empty();}const size_t size() const {return c.size();}const T& top() const {return c.front();}void push(const T& x) {c.push_back(x);upadjust(c.size() - 1);}void pop() {swap(c[0], c[c.size() - 1]);c.pop_back();downadjust(0);}private:Container c;Compare com;};}
三.容器适配器：
适配器是一种设计模式(设计模式是一套被反复使用的、多数人知晓的、经过分类编目的、代码设 计经验的总结)，该种模式是将一个类的接口转换成客户希望的另外一个接口。
简单来说就是：它自己不是容器，用的其他的容器进行封装然后再使用，那么这个类就是容器适配器。
比如queue和stack的实现它们就是容器适配器，但它们不是容器，而是对底层容器进行封装，即对deque封装。
如：
template<class T, class Con = deque<T>>//底层容器的类型四.deque：
deque(双端队列)：是一种双开口的"连续"空间的数据结构，双开口的含义是：可以在头尾两端 进行插入和删除操作，且时间复杂度为O(1)，与vector比较，头插效率高，不需要搬移元素；与 list比较，空间利用率比较高。
注：deque的空间不是绝对连续的:它并不是真正连续的空间，而是由一段段连续的小空间拼接而成的，实际deque类似于一个 动态的二维数组。
如：
访问它就可以利用类似二维数组，但是它的底层实现是复杂的，如要判断数据相对位置，控制四个指针的指向。故通常作为了解即可。
当然可以理解为它是vector和list结合，但并不完全。与vector相比，它头插，头删，尾插，可以直接进行，不用大量挪动以及容量不足的时候扩大量空间，与list相比，它的底层空间中控数组里面存着的指针所指向的数组是连续的，这样就可以提高一定空间利用率。
但是不可能能完全综合了优点，还存在个致命的缺点：不适合遍历，因为在遍历时，deque的迭代器要频繁的去检测其 是否移动到某段小空间的边界，导致效率低下，而序列式场景中，可能需要经常遍历，因此在实际遍历不用它。 故这里只是在stack和queue的封装，底层用了它。
那为什么这里会用deque而不是vector或者list：
1. stack和queue不需要遍历(因此stack和queue没有迭代器)，只需要在固定的一端或者两端进 行操作。
2. 在stack中元素增长时，deque比vector的效率高(扩容时不需要搬移大量数据)；queue中的 元素增长时，deque不仅效率高，而且内存使用率高。