双端队列

双端队列是指允许两端都可以进行入队和出队操作的队列，其元素的逻辑结构仍是线性结构。将队列的两端分别称为前端和后端，两端都可以入队和出队。

基本简介

双端队列（deque，全名double-ended queue）是一个限定插入和删除操作的数据结构，具有队列和栈的性质。双端队列中的元素可以从两端弹出，其限定插入和删除操作在表的两端进行。

双端队列是限定插入和删除操作在表的两端进行的线性表。这两端分别称做端点1和端点2。也可像栈一样，可以用一个铁道转轨网络来比喻双端队列。

基本操作

这里，只讨论deque类的插入和删除操作。

插入

双端队列不仅提供了push_back成员函数，还提供了push_front成员函数，从而可以在序列的前后两端进行插入操作。

对于双端队列，在序列的两端插入元素的时间复杂度均为常数，在中间插入元素的时间复杂度与插入点到最近序列端点的距离成正比。并且，对于双端队列的插入操作(包括在双端插入和中间插入)，将会使所有的迭代器失效，只能采用下标操作。

删除

双端队列不仅提供了pop_back成员函数，还提供了pop_front成员函数，从而可以在序列的前后两端进行删除操作。在中间的删除操作将会使所有迭代器失效；而在两端的删除操作，仅当删除位置就是迭代器所指向位置时会使迭代器失效。

分类

输出受限的双端队列：允许在一端进行插入和删除，但在另一端只允许插入的双端队列称为输出受限的双端队列，如图3-11所示。

输出受限的双端队列

输入受限的双端队列：允许在一端进行插入和删除，但在另一端只允许删除的双端队列称为输入受限的双端队列，如图3-12所示。而如果限定双端队列从某个端点插入的元素只能从该端点删除，则该双端队列就蜕变为两个栈底相邻接的栈了。

输入受限的双端队列

应用

正是由于双端队列在两端插入、删除操作的便利性，并且它又具有随机访问迭代器，其应用十分广泛。STL的适配器，如堆栈、队列和优先队列都可以采用双端队列来实现，其中前两者默认采用deque来保存自己的元素。