deque则是一种双向开口的连续线性空间。
deque由一段一段的定量连续空间组成，一旦需要增加新的空间，只要配置一段定量连续空间拼接在头部或尾部即可，因此deque的最大任务是如何维护这个整体的连续性
deque的数据结构如下：
class deque
{
...
protected:
typedef pointer* map_pointer;//指向map指针的指针
map_pointer map;//指向map
size_type map_size;//map的大小
public:
...
iterator begin();
itertator end();
...
}
deque内部有一个指针指向map，map是一小块连续空间，其中的每个元素称为一个节点，node，每个node都是一个指针，指向另一段较大的连续空间，称为缓冲区，这里就是deque中实际存放数据的区域，默认大小512bytes。整体结构如上图所示。
deque的迭代器数据结构如下：
deque虽然也提供随机访问的迭代器，但是其迭代器并不是普通的指针，其复杂程度比vector高很多。
struct __deque_iterator
{
...
T* cur;//迭代器所指缓冲区当前的元素
T* first;//迭代器所指缓冲区第一个元素
T* last;//迭代器所指缓冲区最后一个元素
map_pointer node;//指向map中的node
...
}
从deque的迭代器数据结构可以看出，为了保持与容器联结，迭代器主要包含上述4个元素。
deque迭代器的“++”、“–”操作是远比vector迭代器繁琐，其主要工作在于：
- 缓冲区边界，如何从当前缓冲区跳到另一个缓冲区；
- 当然deque内部在插入元素时，如果map中node数量全部使用完，且node指向的缓冲区也没有多余的空间，这时会配置新的map（2倍于当前+2的数量）来容纳更多的node，也就是可以指向更多的缓冲区；
- 在deque删除元素时，也提供了元素的析构和空闲缓冲区空间的释放等机制。
deque： 双端队列容器。
底层数据结构： 动态开辟的二维数组，一维数组从2开始，以2倍的方式进行扩容，每次扩容后，原来第二维的数组，从新的第一维数组的下标oldsize/2开始存放，上下都预留相同的空行，方便支持deque的首尾元素添加。
第一维空间大小是MAP_SIZE=2，第二维和元素类型有关。
如果T是int类型，则第二维空间大小是4096/4=1024个。
- 双端队列，两个端可以做队头，或者队尾。
- 相当于2个方向都有2个角色。
- first和last处于中间的位置（512）：为了让两头都预留足够的空间，每一头都可以插入的。
随着元素的增加，相应的指针fisrt和last向两端移动！
如果还想从右向左入，这个第二维已经没有空间了！
需要进行另外一个二维的开辟。
随着我们空间又添加满了：
此时deque就需要扩容了，它扩容的是第一维，是按照2倍进行扩容的。
- 然后第二维也要挪过来了。是放在第一维的中间的位置。
- 因为是双端队列，任何一端都有可能进行元素的插入。给上下都预留空间。方便元素的添加！
然后deque又需要扩容。第一维扩容到原来的2倍。第二维挪过来，放在第一维的中间位置。
10、STL中stack实现stack（栈） 是一种先进后出（First In Last Out）的数据结构，只有一个入口和出口，那就是栈顶，除了获取栈顶元素外，没有其他方法可以获取到内部的其他元素，其结构图如下：
stack这种单向开口的数据结构很容易由双向开口的deque和list形成，只需要根据stack的性质对应移除某些接口即可实现，stack的源码如下：
template> class stack { ... protected: Sequence c; public: bool empty(){return c.empty();} size_type size() const{return c.size();} reference top() const {return c.back();} const_reference top() const{return c.back();} void push(const value_type& x){c.push_back(x);} void pop(){c.pop_back();} };
从stack的数据结构可以看出，其所有操作都是围绕Sequence完成，而Sequence默认是deque数据结构。
stack这种“修改某种接口，形成另一种风貌”的行为，成为adapter(配接器)。常将其归类为container adapter（容器适配器）而非container。
stack除了默认使用deque作为其底层容器之外，也可以使用双向开口的list，只需要在初始化stack时，将list作为第二个参数即可。
由于stack只能操作顶端的元素，因此其内部元素无法被访问，也不提供迭代器。
11、STL中queue的实现queue（队列）是一种先进先出（First In First Out）的数据结构，只有一个入口和一个出口，分别位于最底端和最顶端，出口元素外，没有其他方法可以获取到内部的其他元素，其结构图如下：
类似的，queue这种“先进先出”的数据结构很容易由双向开口的deque和list形成，只需要根据queue的性质对应移除某些接口即可实现，queue的源码如下：
template> class queue { ... protected: Sequence c; public: bool empty(){return c.empty();} size_type size() const{return c.size();} reference front() const {return c.front();} const_reference front() const{return c.front();} void push(const value_type& x){c.push_back(x);} void pop(){c.pop_front();} };
从queue的数据结构可以看出，其所有操作都也都是是围绕Sequence完成，Sequence默认也是deque数据结构。queue也是一类container adapter（容器适配器）。
同样，queue也可以使用list作为底层容器，不具有遍历功能，没有迭代器。
