Day 18: Queues & Deques

DAY 18 / 30 · WEEK 3

Goal of the day

Understand FIFO (first-in, first-out) queue mechanics — enqueue at the back, dequeue from the front — and contrast it with Day 17’s stack (LIFO, both ends collapse to one).
Understand a deque (double-ended queue): push and pop from both ends, front and back.
Solve Sliding Window Maximum in O(n) using a monotonic deque of indices — instead of the naive O(n·k) approach of rescanning every window.

Concept

FIFO vs. LIFO. Day 17’s stack is last-in, first-out: whatever you pushed most recently is the first thing that comes back out, and both push and pop happen at the same end. A queue flips that: it’s first-in, first-out. Whoever enqueued first is the first one dequeued — think of a checkout line. Enqueue always adds to the back; dequeue always removes from the front. Those are two different ends, which is the key structural difference from a stack.

A JS gotcha worth knowing: a plain array works fine as a queue functionally (push to enqueue, shift to dequeue), but Array.prototype.shift() is O(n) — removing index 0 forces every remaining element to re-index down by one. A real O(1) queue needs a different structure (two stacks, a linked list, or an index-based circular buffer) — that’s exactly what today’s first two practice problems have you build.

A deque (pronounced “deck”) generalizes both: you can push and pop from either end — pushFront/pushBack/popFront/popBack. A stack is a deque restricted to one end; a queue is a deque restricted to push-back/pop-front. Having both ends available is exactly what makes today’s main algorithm possible.

Sliding Window Maximum. Given an array and a window size k, report the max of every contiguous window of size k as it slides across the array. The naive approach rescans all k elements for every one of the n - k + 1 windows: O(n·k). A monotonic deque gets this to O(n): keep a deque of indices whose values are strictly decreasing from front to back. The front index is always the current window’s max. When a new element arrives, pop any smaller values off the back first — they can never win again, a bigger number just showed up behind them. Then push the new index onto the back. Finally, if the front index has slid outside the window, pop it from the front — even if it’s still the largest value ever seen, it’s no longer inside the window, so it doesn’t count anymore.

Diagram: queue mechanics (FIFO)

Diagram: the monotonic deque’s invariant

Interactive visualization: Sliding Window Maximum

current index i in the deque just popped from the back just expired from the front front of deque = window max

Array nums[i] — colors show what's happening at each index right now

Press Play or Step to begin.

Step 0 / 0

Deque contents after this step (front → back, shown as index:value)

The code: Sliding Window Maximum

function maxSlidingWindow(nums, k) {
  const deque = [];   // holds INDICES; front-to-back values strictly decrease
  const result = [];

  for (let i = 0; i < nums.length; i++) {
    // 1. pop smaller trailing values off the BACK — they can never be the
    //    max again now that a bigger (or equal) number has shown up
    while (deque.length && nums[deque[deque.length - 1]] <= nums[i]) {
      deque.pop();
    }

    // 2. push the current index onto the back
    deque.push(i);

    // 3. pop the FRONT if it has slid outside the window
    if (deque[0] <= i - k) {
      deque.shift();
    }

    // 4. once the window is full (i >= k - 1), the front is the max
    if (i >= k - 1) {
      result.push(nums[deque[0]]);
    }
  }

  return result;
}

Line by line:

deque holds array indices, not values — storing values would make it impossible to tell whether the front has aged out of the window (you’d have no way to compare “position” against i - k).
Step 1’s while loop pops the back as long as it’s ≤ the incoming value. This is what keeps the deque’s invariant (strictly decreasing front-to-back) true after every push — an equal or smaller trailing value is provably useless from now on.
Step 2 pushes i onto the back after the cleanup — the new element always ends up as a valid candidate.
Step 3’s check deque[0] <= i - k tests whether the front index is still inside the current window [i - k + 1, i]. If it isn’t, it’s evicted from the front — regardless of how large its value is.
Step 4 only starts recording once the first full window exists (i >= k - 1); before that there simply isn’t a complete window yet.

Dry run: maxSlidingWindow([5, 3, 8, 2, 9, 1, 7, 4], k = 3)

i	nums[i]	Deque before	Action(s)	Deque after	Window max
0	5	[]	push 0	[0]	—
1	3	[0]	3 doesn’t evict 5 → push 1	[0, 1]	—
2	8	[0, 1]	pop back 1 (3≤8), pop back 0 (5≤8), push 2	[2]	nums[2] = 8
3	2	[2]	2 doesn’t evict 8 → push 3	[2, 3]	nums[2] = 8
4	9	[2, 3]	pop back 3 (2≤9), pop back 2 (8≤9), push 4	[4]	nums[4] = 9
5	1	[4]	1 doesn’t evict 9 → push 5	[4, 5]	nums[4] = 9
6	7	[4, 5]	pop back 5 (1≤7), 7 doesn’t evict 9 → push 6	[4, 6]	nums[4] = 9
7	4	[4, 6]	4 doesn’t evict 7 → push 7; front 4 ≤ 7−3=4 → expired, pop front	[6, 7]	nums[6] = 7

Final result: [8, 8, 9, 9, 9, 7]. Notice i=7: index 4 (value 9) is still the largest value ever seen, but it’s outside the window [5, 6, 7] — position, not value, decides eviction from the front.

Complexity

Approach	Time	Space	Why
Naive (rescan each window)	O(n·k)	O(1)	For each of the n − k + 1 windows, scan all k elements to find the max.
Monotonic deque	O(n)	O(k)	Every index is pushed onto the deque exactly once and popped at most once (from either end) — that’s ≤ 2n total push/pop operations, not n·k. The deque never holds more than k indices at a time.

Interview corner

Why does the deque store indices instead of values? Storing values would make step 3 impossible — you need to compare the front’s position against i - k to know whether it has slid outside the window. A raw value carries no position information at all.

⚠ Trap: this is the single most common way this pattern breaks in an interview — writing deque.push(nums[i]) instead of deque.push(i) compiles fine and even passes the first couple of test cases, then silently gives wrong answers once a stale-looking value needs to expire.
Why is this O(n) despite the nested-looking while loop inside the for loop? Amortized analysis: each of the n indices is pushed onto the deque exactly once over the whole run, and can be popped at most once (from the back or the front) before it’s gone for good. Total pushes + pops across the entire algorithm is bounded by 2n, not n·k — the nesting looks like O(n·k) but the inner loop’s total work across all iterations is capped by how many elements exist, not by k.

↳ Common follow-up: “What if the array is strictly increasing?” — then every push immediately pops the entire deque from the back first, so the deque never holds more than 1 index; still O(n) overall, just a different distribution of the work.
What’s the deque’s invariant, and why does maintaining it work? Front-to-back, the values at the stored indices strictly decrease. That’s why the front is always the correct answer: anything that could have beaten it was already popped off the back before it could sit behind it.
What happens if you forget to pop expired front indices before reading the max?

⚠ Trap: you’ll silently return a max from an index that’s no longer inside the current window — the code won’t throw, it’ll just be wrong, and easy to miss unless you specifically trace an example where the old max ages out (like i=7 in today’s dry run).
How is this different from Day 17’s stack-based “next greater element” pattern? Both use a monotonic structure, but “next greater element” only ever pops from one end (a stack, LIFO). Sliding Window Maximum needs both ends — pop the back to maintain the value invariant, pop the front to enforce the window boundary — which is exactly why it needs a deque and not a plain stack.

How to talk through it out loud: name the invariant before you write a line of code — “I’ll keep a deque of indices where the values are strictly decreasing front to back, so the front is always my current window’s max.” Then narrate the two eviction rules separately: “I pop the back when a new value makes an old one useless, and I pop the front when an old index slides outside the window.” Interviewers are listening for whether you can articulate why each end gets popped, not just recite the code from memory.

Practice problems

Note: problem 3 (Sliding Window Maximum) is LeetCode Hard and is today’s own core algorithm, not a step up in difficulty from problems 1-2 — same intentional exception to the usual easy→medium ramp used on Day 10 (Merge k Sorted Lists), since it’s the natural, direct application of what this lesson just taught.

1. Implement Queue using Stacks

Easy — LeetCode: Implement Queue using Stacks

Implement a FIFO queue (push, pop, peek, empty) using only two stacks (LIFO structures).

Show hint

Use an “in” stack for pushes. When you need to pop or peek and the “out” stack is empty, dump the entire “in” stack into the “out” stack first — that reversal is exactly what turns LIFO order back into FIFO order.

Show solution

class MyQueue {
  constructor() {
    this.inStack = [];
    this.outStack = [];
  }
  push(x) {
    this.inStack.push(x);
  }
  _transferIfNeeded() {
    if (this.outStack.length === 0) {
      while (this.inStack.length) this.outStack.push(this.inStack.pop());
    }
  }
  pop() {
    this._transferIfNeeded();
    return this.outStack.pop();
  }
  peek() {
    this._transferIfNeeded();
    return this.outStack[this.outStack.length - 1];
  }
  empty() {
    return this.inStack.length === 0 && this.outStack.length === 0;
  }
}

2. Design Circular Deque

Medium — LeetCode: Design Circular Deque

Implement a fixed-capacity deque with insertFront, insertLast, deleteFront, deleteLast, getFront, getRear, isEmpty, and isFull — all O(1), using a fixed-size array as the backing store (no shifting elements around).

Show hint

Track a front index and a size count instead of a separate “rear” index — the rear position is always derivable as (front + size - 1) % capacity. Wrapping front backwards for insertFront needs (front - 1 + capacity) % capacity, not plain front - 1 — JS’s % keeps a negative sign on negative operands, so the raw subtraction can go negative.

Show solution

class MyCircularDeque {
  constructor(k) {
    this.cap = k;
    this.data = new Array(k);
    this.front = 0;
    this.size = 0;
  }
  insertFront(value) {
    if (this.size === this.cap) return false;
    this.front = (this.front - 1 + this.cap) % this.cap; // wrap backwards safely
    this.data[this.front] = value;
    this.size++;
    return true;
  }
  insertLast(value) {
    if (this.size === this.cap) return false;
    const rear = (this.front + this.size) % this.cap;
    this.data[rear] = value;
    this.size++;
    return true;
  }
  deleteFront() {
    if (this.size === 0) return false;
    this.front = (this.front + 1) % this.cap;
    this.size--;
    return true;
  }
  deleteLast() {
    if (this.size === 0) return false;
    this.size--; // rear is derived from size, so shrinking size "removes" it
    return true;
  }
  getFront() {
    return this.size === 0 ? -1 : this.data[this.front];
  }
  getRear() {
    return this.size === 0 ? -1 : this.data[(this.front + this.size - 1) % this.cap];
  }
  isEmpty() {
    return this.size === 0;
  }
  isFull() {
    return this.size === this.cap;
  }
}

3. Sliding Window Maximum

Hard — intentional exception, see note above — LeetCode: Sliding Window Maximum

Given an array nums and window size k, return the max of every contiguous window of size k. Today’s main algorithm, applied directly.

Show hint

Keep a deque of indices, front-to-back strictly decreasing by value. Before pushing index i, pop any back indices whose value is ≤ nums[i]. After pushing, pop the front if it’s fallen outside [i - k + 1, i].

Show solution

function maxSlidingWindow(nums, k) {
  const deque = [];
  const result = [];
  for (let i = 0; i < nums.length; i++) {
    while (deque.length && nums[deque[deque.length - 1]] <= nums[i]) {
      deque.pop();
    }
    deque.push(i);
    if (deque[0] <= i - k) {
      deque.shift();
    }
    if (i >= k - 1) {
      result.push(nums[deque[0]]);
    }
  }
  return result;
}

Quiz

In a queue, which end does dequeue() remove from?
- The front — the oldest element still waiting
- The back — same end as enqueue
- Either end, implementation’s choice
Show answer
The front — the oldest element still waiting
A queue is FIFO: enqueue always adds to the back, and dequeue always removes from the front — the two operations happen at opposite ends, unlike a stack where both happen at the same end.
What does the monotonic deque in Sliding Window Maximum actually store?
- Array indices
- The array’s values directly
- Neither — it stores running sums
Show answer
Array indices
The deque stores indices, not values — that’s what lets step 3 check whether the front index has slid outside the current window (i - k), a check that’s impossible if all you have is a bare value with no position information.
Front to back, how do the values at the deque’s stored indices relate to each other?
- They strictly decrease
- They strictly increase
- They stay in original array order, unsorted
Show answer
They strictly decrease
Front-to-back, the values at the stored indices strictly decrease. That’s exactly why the front is always the current window’s max — anything that could have beaten it was already popped off the back before it could end up behind it.
Why is Sliding Window Maximum’s deque solution O(n), not O(n·k), despite the nested while loop?
- Each index is pushed once and popped at most once across the whole run — total work is bounded by 2n
- Because k is always a small constant in practice
- It isn’t actually O(n) — it’s O(n·k), just with a small constant factor
Show answer
Each index is pushed once and popped at most once across the whole run — total work is bounded by 2n
Each of the n indices is pushed onto the deque exactly once and popped at most once (from either end) over the entire run — total push/pop operations are bounded by 2n, not n·k, even though the while loop is nested inside the for loop.
When do we pop from the deque’s front vs. its back?
- Back: a smaller trailing value is now useless. Front: its index has expired out of the window.
- Only ever from the front — same as a plain queue
- Only ever from the back — same as a plain stack
Show answer
Back: a smaller trailing value is now useless. Front: its index has expired out of the window.
Pop the back when a new value makes an existing trailing value useless (it can never be the max again). Pop the front when its index has slid outside the current window — regardless of how large that value still is.