Deque

A deque — short for *double-ended queue*, said 'deck' — is a line you can add to or remove from at either end, the front or the back, each in constant time. That flexibility makes it a stack and a queue rolled into one: restrict yourself to one end and it behaves LIFO like a stack; use the front and back the usual way and it behaves FIFO like a queue.

Four operations, all O(1)

1. 1pushFront(x) / pushBack(x) — add at the left end or the right end.
2. 2popFront() / popBack() — remove from the left end or the right end.
3. 3Every one touches only an end, so every one is O(1) regardless of size.

Worked example — sliding-window maximum

A deque's signature use is the sliding-window maximum: find the largest value in every window of size k as it slides across an array. Naively that's O(nk). A deque holding indices, kept in decreasing order of their values, solves it in O(n). The front always holds the index of the current window's maximum.

1. 1Before adding index i, popBack while the value there is ≤ arr[i] — those can never be the max again.
2. 2pushBack i.
3. 3popFront if the front index has slid out of the window (≤ i − k).
4. 4Once the first window is full, the front index is that window's maximum.

function maxSlidingWindow(arr, k) {
  const dq = []; // holds indices, values decreasing front->back
  const out = [];
  for (let i = 0; i < arr.length; i++) {
    while (dq.length && arr[dq[dq.length - 1]] <= arr[i]) dq.pop();
    dq.push(i);                          // pushBack
    if (dq[0] <= i - k) dq.shift();       // popFront if out of window
    if (i >= k - 1) out.push(arr[dq[0]]); // front = window max
  }
  return out;
}