2.queue的模拟实现
1.queue的结构
和stack的结构非常相似，代码框架如下：
namespace zht//这里把实现的queue包在命名空间中 { template<class T, class Container = std::deque<T>> class queue { public: //成员函数 private: Container _con; }; }
2.接口实现
queue的接口实现方式和queue也是非常的类似，唯一需要改的就是push和pop数据的位置
//构造函数：我们不显示写，编译器生成。直接调用_con的默认构造 bool empty() const { return _con.empty(); } size_t size() const { return _con.size(); } const T& top() { return _con.back();//适配这类操作的容器都是支持back或者front接口的，直接调用即可 } void push(const T& val)//这里的push我们采用尾插的方式插入 { _con.push_back(val); } void pop()//由于push使用的是尾插，所以pop采用头删的方式 { _con.pop_back(); }
至此，我们就算是能够手撕stack和queue了哈哈。
4.了解deque
我们注意到，stack和queue的容器都是deque。这是为什么呢？在学习数据结构的时候，实现的stack和queue一般是使用顺序表和链表实现的。为什么这里不使用vector和list呢？
vector和list的结构都存在一些缺陷：vector真正的缺点在于扩容消耗，不支持头插头删，因为头部中部删除效率低。而list不支持随机访问，且CPU高速缓存命中率低，空间不连续。而deque兼具了vector和list的优点，虽然deque也有很多缺点，但是作为适配器的容器恰好避免了这些。
对于deque，我们稍微了解一下即可，因为deque合适的使用场景很少。
1.deque的原理介绍
deque(双端队列)：是一种双开口的"连续"空间的数据结构，双开口的含义是：可以在头尾两端进行插入和删除操作，且时间复杂度为O(1)，与vector比较，头插效率高，不需要搬移元素；与list比较，空间利用率比较高 。
这只是逻辑图，deque在底层并不是真的连续空间
2.deque的底层结构
deque的底层是由很多段连续的小空间拼接而成，类似一个二维数组，然后这些小空间的地址存放在一个中控指针数组中。结构示意图如下：
3.deque的迭代器设计
那么deque是如何使用迭代器来维护这个假想的连续结构的呢？
这里参考一下侯捷老师的STL源码剖析中的图：
deque的迭代器包含四个指针，其中cur指向当前值，first和last指向当前cur所在的小段连续空间，node指向中控数组中存放所在连续空间的地址。
4.deque的优缺点分析
优点：头部插入和删除时，不需要搬移元素，效率特别高，扩容时，也不需要搬移大量的元素，因此其效率是比vector高的。与list比较，其底层是连续空间，空间利用率比较高，不需要存储额外字段。
缺点：不适合遍历，因为在遍历时，deque的迭代器要频繁的去检测其是否移动到某段小空间的边界，导致效率低下，而序列式场景中，可能需要经常遍历，因此在实际中，需要线性结构时，大多数情况下优先考虑vector和list，deque的应用并不多，而目前能看到的一个应用就是，STL用其作为stack和queue的底层数据结构
5.为什么选择deque作为stack和queue的底层默认容器
stack是一种后进先出的特殊线性数据结构，因此只要具有push_back()和pop_back()操作的线性结构，都可以作为stack的底层容器，比如vector和list都可以；queue是先进先出的特殊线性数据结构，只要具有push_back和pop_front操作的线性结构，都可以作为queue的底层容器，比如list。但是STL中对stack和queue默认选择deque作为其底层容器，主要是因为：
- stack和queue不需要遍历(因此stack和queue没有迭代器)，只需要在固定的一端或者两端进行操作。
- 在stack中元素增长时，deque比vector的效率高(扩容时不需要搬移大量数据)；queue中的元素增长时，deque不仅效率高，而且内存使用率高。
- 结合了deque的优点，而完美的避开了其缺陷
和queue默认选择deque作为其底层容器，主要是因为：
- stack和queue不需要遍历(因此stack和queue没有迭代器)，只需要在固定的一端或者两端进行操作。
- 在stack中元素增长时，deque比vector的效率高(扩容时不需要搬移大量数据)；queue中的元素增长时，deque不仅效率高，而且内存使用率高。
- 结合了deque的优点，而完美的避开了其缺陷
