双向队列deque

---

它是vector和list的结合，复杂度处于二者之间。

线性表存储，deque采用分块的线性存储结构来存储数据，每块的大小一般为512B，将之称为deque块;

所有的deque块使用一个map块进行管理，每个map数据项记录各个deque块的首地址,所以允许较为快速的随机访问;

deque<int> a

a.push_back(e) 在尾部插入元素e,会不断扩张队列

a.push_front(e) 在头部插入元素e

a.pop_front() 在头部删除数据

a.pop_back() 在尾部删除

a.erase(a.end())

a[1]

---

底层怎么实现的？

和 vector 容器采用连续的线性空间不同，deque 容器存储数据的空间是由一段一段等长的连续空间构成，各段空间之间并不一定是连续的，可以位于在内存的不同区域。

为了管理这些连续空间，deque 容器用数组（数组名假设为 map）存储着各个连续空间的首地址

image.gif

通过建立 map 数组，deque 容器申请的这些分段的连续空间就能实现“整体连续”的效果。换句话说，当 deque 容器需要在头部或尾部增加存储空间时，它会申请一段新的连续空间，同时在 map 数组的开头或结尾添加指向该空间的指针，由此该空间就串接到了 deque 容器的头部或尾部。

有读者可能会问，如果 map 数组满了怎么办？

很简单，再申请一块更大的连续空间供 map 数组使用，将原有数据（很多指针）拷贝到新的 map 数组中，然后释放旧的空间。