陣列與線性結構
雙端佇列
雙端佇列（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 之上。
又稱
另見