Deque 可以同時當 Stack 和 Queue 用——而且 Java 官方推薦用它取代那個過時的
Stack類。
先講結論
Deque（Double-Ended Queue）兩端都可以插入和刪除，所有操作 O(1)。它是 Stack 和 Queue 的超集——前端操作就是 Queue，後端操作就是 Stack，兩端都用就是 Deque。最殺手級的應用是「滑動視窗最大值」。
兩端都能操作
addFirst → ┌───┬───┬───┬───┐ ← addLast
removeFirst ← │ A │ B │ C │ D │ → removeLast
└───┴───┴───┴───┘
front rear
Stack 只能從一端操作，Queue 從兩端但一端進一端出。Deque 兩端都能進出，是最靈活的線性結構。
實作方式
雙向鏈表：每個節點有 prev 和 next，兩端操作都 O(1)。直觀但 cache 不友善。
環形陣列：跟 Queue 的環形陣列一樣，但 front 可以往前也可以往後。
addFirst → front = (front - 1 + capacity) % capacity
addLast → tail = (tail + 1) % capacity
Java 的 ArrayDeque 就是環形陣列版，實務上幾乎總是首選。
滑動視窗最大值：Deque 的殺手應用
LeetCode 239。給一個陣列和視窗大小 k，求每個視窗位置的最大值。
暴力法每個視窗都掃一遍是 O(nk)。用一個單調遞減的 Deque 可以做到 O(n)：
Deque<Integer> deque = new ArrayDeque<>();
for (int i = 0; i < n; i++) {
// 把超出視窗的踢掉（從前端）
while (!deque.isEmpty() && deque.peekFirst() < i - k + 1)
deque.pollFirst();
// 比新元素小的都沒用了，踢掉（從後端）
while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i])
deque.pollLast();
deque.offerLast(i);
if (i >= k - 1) result[i-k+1] = nums[deque.peekFirst()];
}Deque 裡存的是 index。前端永遠是當前視窗的最大值。新元素進來時，把所有比它小的從後端踢掉——因為它們不可能再成為任何未來視窗的最大值了。
這個技巧叫「單調隊列」（Monotonic Queue），在競賽和面試中出現頻率很高。
為什麼 Java 推薦 ArrayDeque 取代 Stack？
Java 的 Stack 類繼承自 Vector，每個方法都加了 synchronized——在單執行緒場景這是無謂的效能損失。ArrayDeque 沒有這個問題，而且底層是環形陣列，比 Vector 的動態陣列更高效。
// 不要這樣
Stack<Integer> stack = new Stack<>();
// 要這樣
Deque<Integer> stack = new ArrayDeque<>();
stack.push(1);
stack.pop();Java 的 legacy API 有多少坑？Stack 只是冰山一角。
Deque 是資料結構界的瑞士刀——它什麼都能做，但最閃亮的那一刻是解滑動視窗問題。