stackqueue类——适配器模式 双端队列deque（C++）

        接下来我们将实现 stack、queue 类的常用函数，其实对于 stack 和 queue 的常用函数实现可以说得上是非常简单，若想详细了解可以看这篇：栈和队列&循环队列（C/C++）_栈和循环队列-CSDN博客；在本篇中我们将使用容器适配器来实现栈和队列。

目录如下:

目录

1. stack 

 2. queue

3. deque

3.1 deque的原理介绍

3.2 deque 的缺陷

3.3 stack、queue为什么选择deque

1. stack 

        我们首先实现的为 stack，根据 cplusplus 网站来实现 stack 的常用函数，如下：

        如上，对于该 stack 函数而言，就只有以上这些类函数（关于其他的 operator 重载函数不包括）。对于以上每个函数的实现，我们并不会在底层实现它，而是使用容器适配器来实现它，如下直接给出函数：

namespace MyStack_Queue {template<class T, class Container = vector<T>>class stack {public:stack(const Container con = Container()):_con(con){}stack(const stack& st):_con(st._con){}bool empty() {return _con.empty();}size_t size() {return _con.size();}void push(const T& e) {_con.push_back(e);}void pop() {_con.pop_back();}T& top() {return _con.back();}const T& top() const {return _con.back();}void swap(stack& st) {_con.swap(st._con);}private:Container _con;};
}

        如上所示，我们在模板处定义了一个类型和一个容器，这个容器的缺省值为 vector，所以当我们在下面函数的实现中，将成员变量默认定义为了 vector 类（但其实在 stack 底层，大多默认都是使用 deque），然后在实现成员函数的时候，默认调用 vector 类中函数，这样就非常方便的实现了一个栈。

        对于以上容器的缺省值，我们不仅仅可以使用 vector，我们还可以使用 deque，还可以使用 list 来实现，只需要在实例化一个对象的时候将值传入就可以了，如下：

void Test00() {MyStack_Queue::stack<int, list<int>> st;st.push(1);st.push(2);st.push(3);st.push(4);st.push(5);while (!st.empty()) {int tmp = st.top();st.pop();cout << tmp << endl;}cout << endl;}

        如上的测试代码，我们使用了一个 list 容器实现了一个栈。但是在实现栈的时候，还是建议使用 vector 类型。

 2. queue

        queue 的实现和 stack 十分的相似，我们使用容器实现，对于 queue 的成员函数如下：

        下列为我们使用容器实现的代码：

	template<class T,class Container = deque<T>>class queue {public:queue(const Container con = Container()):_con(con){}queue(const Container& q) {_con(q._con);}bool empty() {return _con.empty();}size_t size() {return _con.size();}T& front() {return _con.front();}const T& front() const {return _con.front;}T& back() {return _con.back();}const T& back() const {return _con.back();}void pop() {_con.pop_front();}void push(const T& e) {_con.push_back(e);}void swap(queue& q) {_con.swap(q._con);}private:Container _con;};

        对于以上容器的缺省值，我们使用的是 deque，当然我们使用 list 也是一种高效的方式。

3. deque

        接下来我们将简单的讲解 deque -- 双端队列，仅仅只是讲解其原理和优缺点，并不会实现 deque，因为 deque 的迭代器实现起来很复杂，所以我们仅仅将其作为一个了解的知识即可。

3.1 deque的原理介绍

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

        deque 并不是真正连续的空间，而是由一段段连续的小空间拼接而成的，实际上类似于一个动态的二维数组，其具体的实现原理如下：

        所以具体的空间开辟如上所示，存在一个中控数组，里面存储的是每一个分组的地址，当我们想要获取元素的时候，就是通过这样的结构进行获取的。但是 deque 同时也支持 operator[] 重载函数，所以可以随机访问到我们的元素，在这样的数据结构中，为了维护随机访问假象，那么这个责任就落到了 deque 的迭代器身上，迭代器的设计原理如下：

        所以对于 deque 的迭代器有着四个指针，分别指向不同的地方，所以 deque 最难的是它的迭代器。

3.2 deque 的缺陷

        与 vector 相比，deque 的优势为：头插和尾删时，不需要搬移元素，效率特别的高，而且在扩容的时候，也不需要搬移大量的元素，因此效率比 vector 高。

        与 list 相比较，其底层是一个连续的空间，空间利用率比较高，不需要存储额外字段。

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

3.3 stack、queue为什么选择deque

        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 的优点，完美的避开了其缺陷。