前面讲的队列，是很“规矩”的，队列的元素都是“先进先出”，队头的只能弹出，队尾只能进入。有没有不那么“规矩”的队列呢？这就是双端队列。双端队列是一种具有队列和栈性质的数据结构，它能在两端进行插入和删除，而且也只能在两端插入和删除。
deque也是顺序容器的一种，也是一个可变长数组。要使用deque，需要包含头文件deque。 所有适用于vector的操作都适用于deque, deque在头尾增删元素性能较好。
deque的特点：
- deque和vector有很多类似的地方。在deque中，随机存取任何元素都能在常数时间内完成(但慢于vector)。
- 它相比于vector的优点是，vector在头部删除或添加元素的速度很慢，在尾部添加元素的性能较好，而deque在头尾增删元素都具有较好的性能（大多数情况下都能在常数时间内完成）。
deque有两种vector没有的成员函数：
- void push_front (const T & val); //将 val 插入容器的头部
- void pop_front () ; //删除容器头部的元素
deque使用注意：
- deque支持随机存取
- deque支持在头部和尾部存储数据
- deque不支持 capacity 和 reserve 操作
STL中deque的常用函数：
dq[i]; //返回q中下标为i的元素；
dq.front(); //返回队头；
dq.back(); //返回队尾；
dq.pop_back(); //删除队尾。不返回值；
dq.pop_front(); //删除队头。不返回值；
dq.push_back(e); //在队尾添加一个元素e；
dq.push_front(e); //在队头添加一个元素e。双端队列的经典应用是单调队列。单调队列有2个特征：
- （1）队列中的元素是单调有序的，且元素在队列中的顺序和原来在序列中的顺序一致；
- （2）单调队列的队头和队尾都能入队和出队。
- 其中（1）是我们期望的结果，它是通过（2）来实现的。
单调队列用起来非常灵活，在很多问题中应用它可以获得优化。简单地说是这样实现的：序列中的n个元素，用单调队列处理时，每个元素只需要进出队列一次，复杂度是O(n)。
下面用两个模板题来讲解单调队列的应用，了解它们如何通过单调队列获得优化。注意队列中“删头、去尾、窗口”的操作。
- 1984: 滑动窗口
- 1727: 最大子序列和
