数组与线性结构
双端队列
双端队列（deque，读作「deck」，是 double-ended queue 的简称）是一条两端都能进出的队伍。你可以在队头和队尾同时进行 push 和 pop，全部 O(1)。这让它成为栈和队列的超集：只用一端就像栈；一端进、另一端出就像队列。
其底层通常是环形缓冲区，或者一串固定大小的分块，于是在任一端扩展都很便宜，也不必大规模挪动。C++ 的 std::deque 还像 vector 一样支持 O(1) 的下标访问，不过在中间插入仍然是 O(n)。与 vector 相比，它额外给了你一个廉价的队头，而朴素动态数组恰恰缺这一点。
当你需要在两端都增删时，双端队列最为出彩。经典例子是滑动窗口最大值：用一个双端队列按序保存候选下标，从队头丢弃过期的、从队尾压入新的——把朴素的 O(n*k) 扫描化为 O(n)。
#include <deque> std::deque<int> dq; dq.push_back(2); // [2] dq.push_front(1); // [1, 2] O(1) at the front dq.push_back(3); // [1, 2, 3] // front <- [ 1 | 2 | 3 ] -> back dq.pop_front(); // [2, 3] O(1) int b = dq.back(); // 3 O(1)
两端都是 O(1)；它既能当栈又能当队列。
双端队列是栈和队列的推广，所以许多库的 std::queue 与 std::stack 都建立在 deque 之上。
又称
另见