双端队列

双端队列是指一个可以在队首/队尾插入或删除元素的队列。相当于是栈与队列功能的结合。具体地，双端队列支持的操作有 $4$ 个：

• 在 $\textcolor{red}{队首}$ 插入一个元素。
• 在 $\textcolor{red}{队尾}$ 插入一个元素。
• 在 $\textcolor{red}{队首}$ 删除一个元素。
• 在 $\textcolor{red}{队尾}$ 删除一个元素。

STL 的 deque

使用方法为 deque<元素类型> 队列名字; 例如 deque<int> q;

• q.push_front(x)。元素加入到队首。
• q.push_back(x)。元素加入到队尾。
• q.pop_front()。删除队头，保证队列不为空使用。
• q.pop_back()。删除队尾，保证队列不为空使用。

deque 的底层实现常数巨大，且非常占用内存。曾有 NOI 选手开了 $10^6$ 个 deque 喜提 MLE 错失金牌。