Queue & Deque

How to think about it

A queue preserves arrival order. A monotonic deque stores candidate indices for window min/max: front is always the answer; back drops dominated values. Combined with a sliding window, each index enters and leaves once.

Template shapes

Shape	Core move	Notes
FIFO queue	Enqueue / dequeue	BFS, buffering
Monotonic deque	Pop back if worse	Window max/min
Time window	Drop expired front	Hit counter

Complexity baseline

O(n) amortized for window extrema; O(1) per op for simple queue designs.

From template to problem

1. Choose queue vs deque based on whether you need both ends.
2. For window max: maintain decreasing values in the deque.
3. Evict front when out of window; push new index after cleaning the back.
4. Record front after the window is full.

/** Deque template: sliding window maximum. */
export function maxSlidingWindow(nums: number[], k: number): number[] {
  const dq: number[] = [];
  const res: number[] = [];
  for (let i = 0; i < nums.length; i++) {
    while (dq.length && dq[0]! <= i - k) dq.shift();
    while (dq.length && nums[dq[dq.length - 1]!]! <= nums[i]!) dq.pop();
    dq.push(i);
    if (i >= k - 1) res.push(nums[dq[0]!]!);
  }
  return res;
}

/** Deque template: sliding window maximum. */
export function maxSlidingWindow(nums: number[], k: number): number[] {
  const dq: number[] = [];
  const res: number[] = [];
  for (let i = 0; i < nums.length; i++) {
    while (dq.length && dq[0]! <= i - k) dq.shift();
    while (dq.length && nums[dq[dq.length - 1]!]! <= nums[i]!) dq.pop();
    dq.push(i);
    if (i >= k - 1) res.push(nums[dq[0]!]!);
  }
  return res;
}