双端队列deque是容器的一种。它比vector更强大，vector只可以在尾端插入元素，deque不只是可以再尾端插入，也可以在队列头插入。下面借助《STL源代码剖析》的图片讲解。

1、deque的内存结构

vector是开辟一段连续的内存，deque可以在前端插入元素，如果像vector开辟一段连续的内存，向前面插入元素不易维护。例如如果只是开辟一段连续内存，那么前端到开辟内存的起始位置要空多少个位置？当这段内存满了时，拷贝到更大内存时，前端空留多少位置？显然难以维护。deque在STL中是维护多个连续内存的，多个连续的内存不一定连续，一段连续的内存叫做缓冲区。STL用一个叫“中控器”的结构map来维护，如下图：

图（1）

map是一个指针的指针，它执向一段连续内存，这段连续内存的内容也是指针，指向缓冲区的起始位置。当map满了的话，可以扩大map到更大的地方。

2、deque的迭代器

3、deque的操作

当向deque插入/删除（在头或者在尾）元素时，如果所操作结点在缓冲区的头或者尾，都要考虑开辟/释放缓冲区的问题。

例如，向图（2）deque末尾插入4个元素0、1、2、3。当插入最后一个元素时，finish迭代器就要移动下一个缓冲区。如下图：

图（4）

当向图（4）deque的头插入元素99时，也会开辟新的缓冲区。如下图：

图（5）

当在首或者尾删除元素时，可能会涉及缓冲区的释放，不难想象。

当在deque中间删除元素时，就会涉及其他元素的移动。deque首尾都可以移动，它会判断怎么可以少移动元素，如果删除位置距离头更近，它会把前面的元素向后移；反之，把后面元素向前移。