一、deque的简单介绍
1.deque的物理结构
deque是一种双向开口的连续性空间。所谓的双向开口，意思是可以在头尾两端分别做元素的插入和删除操作。
2.deque的内部结构
deque并不是真正连续的空间，而是由一段段连续的小空间拼接而成的，实际deque类似于一个动态的二维数组，其底层结构如下图所示：
从deque的结构图来看map就是一个指针数组， 数组中的每个元素是一个地址，地址分别对应了一块较大的连续空间，用来存储数据。
需要注意：map中的元素我们称之为一个一个的buffer，当开辟第一个buffer时并不是从头开辟的，而是在从中间去开辟，当这个buffer指向的空间所存储的数据已满时，想要在这个这个buffer所指向的空间前插入元素时，就会在前面开辟一块同样大小的空间，在map数组中前一个buffer就会指向这段空间，以此类推。
deque是如何访问元素的呢？
//假设有如下定义 deque<int> dq;
二、deque的迭代器
deque的迭代器是一个start类和finish类，分别包含了四个指针cur、first、last、node;
迭代器strart中:
cur ----- 指向此迭代器所指缓冲区中的现行元素开头
first ----- 指向此迭代器所指缓冲区的头
last ----- 指向此迭代器所指缓冲区的尾（含备用空间）
node ----- 指向的是管控中心
迭代器finish中:
cur ----- 指向此迭代器所指缓冲区中的现行元素结尾
first ----- 指向此迭代器所指缓冲区的头
last ----- 指向此迭代器所指缓冲区的尾（含备用空间）
node ----- 指向的是管控中心
通过cur指针来访问元素，当第一个buffer访问至结束时，通过node指针++操作，进入到第二个buffer，此时first、last也同时管控新的buffer；
三、为何要选用deque作为stack和queue的默认容器
stack和queue的默认容器是deque，我们仔细思考一下，在没有deque的情况下：
对于stack：我们也可以用 vector 和 list ；对于queue：我们只能使用 list ；
问题1：stack如果选用vector，相比选用deque，哪一个更好？为什么？
deque的优势在于：扩容代价不大，不需要拷贝数据，浪费空间也不大
问题2：stack&queue如果选用list，相比选用deque，哪一个更好？为什么？
deque的优势在于：cpu高速cache命中高，以为是一段连续的空间；此外，list需要频繁的申请小块空间。从申请和释放空间上来看，deque申请和释放空间次数少，代价低，唯一需要扩容的就是中控数组（map），但代价也很小。
总结：deque适合头尾的插入删除，但是中间插入删除和随机访问效率都差强人意。所有要高频随机访问还得是vector，要任意位置插入，还得是list；
四、stack的模拟实现
结合上面的分析，总结下来deque在设计出来的时候还是考虑到很多地方的，在模拟实现上，我们给模板的第二个参数加上Container，它接收的是容器，如vector、list
#include<vector> #include<list> // 适配器模式 namespace mlg { // 为了能够实现接收以下其他容器，模板参数需要加上Container // stack<int, vector<int>> s; // stack<int, list<int>> s; template<class T, class Container = deque<T>>//模板增加一个容器参数，给到缺省值 class stack { public: //判断栈是否为空 bool empty() const {return _con.empty();} //计算当前栈中有效元素的个数 size_t size() const {return _con.size();} //取栈顶的元素 const T& top() const {return _con.back();} //尾插（元素入栈） void push(const T& x) {_con.push_back(x);} //尾删（元素出栈） void pop() {_con.pop_back();} private: Container _con;//成员变量是未知的容器 }; void test_stack() { //stack<int, std::vector<int>> s; //stack<int, std::list<int>> s; stack<int> s; s.push(1); s.push(2); s.push(3); s.push(4); while (!s.empty())//判断栈是否为空 { cout << s.top() << " ";//取栈顶的元素 s.pop();//删除栈顶的元素，两个函数结合就能实现栈中元素出栈效果 } cout << endl; } }
五、queue的模拟实现
#include<vector> #include<list> namespace mlg { // 为了能够实现接收以下其他容器，模板参数需要加上Container // stack<int, vector<int>> s; // stack<int, list<int>> s; template<class T, class Container = deque<T>>//模板增加一个容器参数，给到缺省值 class queue { public: //判断队列是否为空 bool empty() const {return _con.empty();} //计算当前队列中有效的元素个数 size_t size() const {return _con.size();} //取队头的元素 const T& front() const {return _con.front();} //取队尾的元素 const T& back() const {return _con.back();} //队尾入数据 void push(const T& x) {_con.push_back(x);} //队头出数据 void pop() {_con.pop_front();} private: Container _con;//成员变量是未知的容器 }; void test_queue() { //queue<int, vector<int>> q; //queue<int, list<int>> q; queue<int> q; q.push(1); q.push(2); q.push(3); q.push(4); while (!q.empty())//判断队列是否为空 { cout << q.front() << " ";//取队头的数据 q.pop();//删除队头的数据，两个函数结合就能实现队列中元素出栈效果 } cout << endl; } }
最后，对于STL之前的几篇博客还要一个知识点未曾提及，那就是迭代器相关的，将会在后续的博客中进行介绍。
