Algorithms & Coding Interviews · Arrays, Strings & Linear Structures

Queues & Deques

Queues power BFS, time-window counters and simulations; deques enable the monotonic deque for sliding-window maximum in O(n). Learn the per-language pitfalls (shift and pop(0) are O(n)), circular buffers, and watch Sliding Window Maximum and a two-stack queue animated.

🧮 Algorithms & Coding Interviews● Intermediate⏱ 10 min read▶ 2 interactive🛠️ 4 exercises

🎯 What you'll learn

FIFO queues and deques in Python, TypeScript and C#
Time-window eviction and circular buffers
The monotonic deque for window max/min
Six LeetCode problems up to Sliding Window Maximum

📚 Before you start

Part 1The Pattern

A queue is first-in, first-out: you add at the back and remove from the front. It's the backbone of BFS (graphs/01), task scheduling, rate limiting by time window, and simulations. A deque (double-ended queue) adds O(1) operations at both ends, which enables the monotonic deque: the standard O(n) answer to "maximum (or minimum) of every sliding window".

A monotonic deque for sliding window maximum: the front is always the current max

1Queues in Each Language

	Python	TypeScript / JavaScript	C#
FIFO queue	`collections.deque`: `append`, `popleft`	array + head index (avoid `shift()`, which is O(n))	`Queue<T>`: `Enqueue`, `Dequeue`, `Peek`
deque	`deque`: `append`, `appendleft`, `pop`, `popleft`	array with head index, or a ring buffer	`LinkedList<T>` (`AddFirst/AddLast/RemoveFirst/RemoveLast`)
priority queue	`heapq` (see `trees/04`)	implement a heap	`PriorityQueue<TElement, TPriority>`

Interview trap: list.pop(0) in Python and array.shift() in JavaScript are O(n), so a BFS written with them becomes O(n²). Use deque or a head pointer.

2Recognition Cues

"process in arrival order", "level by level", "shortest number of steps" → queue (BFS)
"requests in the last 3000 ms", "moving average of the last k values" → queue of timestamps/values, evict from the front
"maximum/minimum of each window of size k" → monotonic deque
"design a circular buffer", "bounded queue" → fixed array + head/tail indices modulo capacity

3Monotonic Deque Template

typescript

function windowMax(nums: number[], k: number): number[] {
  const dq: number[] = [];             // use a head pointer instead of shift() for O(1)
  let head = 0;
  const out: number[] = [];
  for (let i = 0; i < nums.length; i++) {
    if (head < dq.length && dq[head] <= i - k) head++;
    while (dq.length > head && nums[dq[dq.length - 1]] <= nums[i]) dq.pop();
    dq.push(i);
    if (i >= k - 1) out.push(nums[dq[head]]);
  }
  return out;
}

python

from collections import deque

def window_max(nums, k):
    dq = deque()                       # indices; values decreasing front → back
    out = []
    for i, x in enumerate(nums):
        if dq and dq[0] <= i - k:      # front fell out of the window
            dq.popleft()
        while dq and nums[dq[-1]] <= x:
            dq.pop()                    # smaller values can never be a max again
        dq.append(i)
        if i >= k - 1:
            out.append(nums[dq[0]])     # front is the window maximum
    return out

The deque keeps indices whose values are decreasing from front to back. When a new value arrives, every smaller value behind it can never be a window maximum again (the new value is larger and stays in the window longer), so it's popped from the back. The front is evicted when it slides out of the window. Each index enters and leaves once: O(n) total, versus O(n·k) for recomputing each window's max.

4Circular Buffers

A fixed-capacity queue stores items in an array with head and size (or head and tail); positions wrap with % capacity. Enqueue writes at (head + size) % capacity; dequeue advances head. Everything is O(1) with no allocations, which is why ring buffers are used in network stacks, logging and audio.

Under the HoodWhy deque Is O(1) at Both Ends▾

CPython's deque is a doubly linked list of fixed-size blocks (64 slots each), so appends and pops at either end touch only the end block. Indexing into the middle is O(n). C#'s Queue<T> is a circular array that doubles when full (amortized O(1) enqueue). A JavaScript array used with shift() must re-index every remaining element, which is why the head-pointer trick matters.

⚠️ Common Pitfalls

O(n) dequeues with pop(0) / shift().
Storing values instead of indices in a monotonic deque: you can't tell when the front leaves the window.
Evicting at the wrong time: remove the expired front before reading the max.
Off-by-one in circular buffers: distinguish full from empty (keep a size counter).
Using a deque when a heap is needed: a monotonic deque works for sliding windows; arbitrary removals need a heap.

📋 Quick Reference

text

Queue: deque.append / popleft · Queue<T>.Enqueue / Dequeue · JS: arr + head index
Window max: pop front if out of window; pop back while ≤ x; push i; answer = a[front]
Circular: tail = (head + size) % cap
All O(1) per operation; sliding window max O(n)

Part 2Interview Problems

Six problems: queue design (two stacks, circular buffer), time-window eviction, simulation with queues, scheduling, and the monotonic deque for Sliding Window Maximum.

1Implement Queue using Stacks (LeetCode 232)

🟢 Easy. Implement a FIFO queue with only stack operations: push, pop, peek, empty.

text

push(1), push(2), peek() → 1, pop() → 1, empty() → false

Approach. Two stacks: inbox receives pushes; outbox serves pops. When outbox is empty, move everything from inbox (this reverses the order). Each element moves at most once.

Complexity. Amortized O(1) per operation.

typescript

class MyQueue {
  private inbox: number[] = [];
  private outbox: number[] = [];
  push(x: number): void { this.inbox.push(x); }
  private shift(): void {
    if (!this.outbox.length) while (this.inbox.length) this.outbox.push(this.inbox.pop()!);
  }
  pop(): number { this.shift(); return this.outbox.pop()!; }
  peek(): number { this.shift(); return this.outbox[this.outbox.length - 1]; }
  empty(): boolean { return !this.inbox.length && !this.outbox.length; }
}

python

class MyQueue:
    def __init__(self):
        self.inbox, self.outbox = [], []

    def push(self, x):
        self.inbox.append(x)

    def _shift(self):
        if not self.outbox:
            while self.inbox:
                self.outbox.append(self.inbox.pop())

    def pop(self):
        self._shift()
        return self.outbox.pop()

    def peek(self):
        self._shift()
        return self.outbox[-1]

    def empty(self):
        return not self.inbox and not self.outbox

2Number of Recent Calls (LeetCode 933)

🟢 Easy. ping(t) records a request at time t (strictly increasing) and returns how many requests happened in [t − 3000, t].

text

ping(1) → 1, ping(100) → 2, ping(3001) → 3, ping(3002) → 3

Approach. Keep a queue of timestamps; on each ping, append t and evict from the front while the oldest is older than t − 3000. The queue length is the answer. This is the core of a sliding-window rate limiter.

Complexity. Amortized O(1) per ping.

typescript

class RecentCounter {
  private q: number[] = [];
  private head = 0;
  ping(t: number): number {
    this.q.push(t);
    while (this.q[this.head] < t - 3000) this.head++;
    return this.q.length - this.head;
  }
}

python

from collections import deque

class RecentCounter:
    def __init__(self):
        self.q = deque()

    def ping(self, t):
        self.q.append(t)
        while self.q[0] < t - 3000:
            self.q.popleft()
        return len(self.q)

3Sliding Window Maximum (LeetCode 239)

🔴 Hard. Return the maximum of every contiguous window of size k.

text

nums = [1,3,-1,-3,5,3,6,7], k = 3 → [3,3,5,5,6,7]

Approach. Monotonic decreasing deque of indices: pop the front when it leaves the window, pop smaller values from the back before pushing the new index, and read the maximum at the front.

Complexity. O(n) time, O(k) space.

typescript

function maxSlidingWindow(nums: number[], k: number): number[] {
  const dq: number[] = [];
  let head = 0;
  const out: number[] = [];
  for (let i = 0; i < nums.length; i++) {
    if (head < dq.length && dq[head] <= i - k) head++;
    while (dq.length > head && nums[dq[dq.length - 1]] <= nums[i]) dq.pop();
    dq.push(i);
    if (i >= k - 1) out.push(nums[dq[head]]);
  }
  return out;
}

python

from collections import deque

def max_sliding_window(nums, k):
    dq, out = deque(), []
    for i, x in enumerate(nums):
        if dq and dq[0] <= i - k:
            dq.popleft()
        while dq and nums[dq[-1]] <= x:
            dq.pop()
        dq.append(i)
        if i >= k - 1:
            out.append(nums[dq[0]])
    return out

4Design Circular Queue (LeetCode 622)

🟠 Medium. Implement a fixed-capacity circular queue: enQueue, deQueue, Front, Rear, isEmpty, isFull.

text

k=3: enQueue 1,2,3 → true; enQueue 4 → false; Rear → 3; deQueue; enQueue 4; Rear → 4

Approach. A fixed array plus head and size. The tail slot is (head + size) % k; the rear element is at (head + size − 1) % k.

Complexity. O(1) per operation, O(k) space.

typescript

class MyCircularQueue {
  private buf: number[];
  private head = 0;
  private size = 0;
  constructor(k: number) { this.buf = new Array(k).fill(0); }
  enQueue(value: number): boolean {
    if (this.isFull()) return false;
    this.buf[(this.head + this.size) % this.buf.length] = value;
    this.size++;
    return true;
  }
  deQueue(): boolean {
    if (this.isEmpty()) return false;
    this.head = (this.head + 1) % this.buf.length;
    this.size--;
    return true;
  }
  Front(): number { return this.isEmpty() ? -1 : this.buf[this.head]; }
  Rear(): number { return this.isEmpty() ? -1 : this.buf[(this.head + this.size - 1) % this.buf.length]; }
  isEmpty(): boolean { return this.size === 0; }
  isFull(): boolean { return this.size === this.buf.length; }
}

python

class MyCircularQueue:
    def __init__(self, k):
        self.buf = [0] * k
        self.head = self.size = 0

    def enqueue(self, value):
        if self.is_full():
            return False
        self.buf[(self.head + self.size) % len(self.buf)] = value
        self.size += 1
        return True

    def dequeue(self):
        if self.is_empty():
            return False
        self.head = (self.head + 1) % len(self.buf)
        self.size -= 1
        return True

    def front(self):
        return -1 if self.is_empty() else self.buf[self.head]

    def rear(self):
        return -1 if self.is_empty() else self.buf[(self.head + self.size - 1) % len(self.buf)]

    def is_empty(self):
        return self.size == 0

    def is_full(self):
        return self.size == len(self.buf)

5Dota2 Senate (LeetCode 649)

🟠 Medium. Senators from parties R and D vote in rounds; each can ban one opposing senator's future votes. Predict the winning party.

text

"RDD" → "Dire"

Approach. Two queues of indices. Repeatedly compare the fronts: the earlier senator bans the other and re-enters at the back with index + n (next round). The party whose queue empties first loses.

Complexity. O(n) time (each round removes one senator), O(n) space.

typescript

function predictPartyVictory(senate: string): string {
  const n = senate.length, r: number[] = [], d: number[] = [];
  for (let i = 0; i < n; i++) (senate[i] === "R" ? r : d).push(i);
  let hr = 0, hd = 0;
  while (hr < r.length && hd < d.length) {
    const a = r[hr++], b = d[hd++];
    if (a < b) r.push(a + n); else d.push(b + n);
  }
  return hr < r.length ? "Radiant" : "Dire";
}

python

from collections import deque

def predict_party_victory(senate):
    n = len(senate)
    r = deque(i for i, c in enumerate(senate) if c == "R")
    d = deque(i for i, c in enumerate(senate) if c == "D")
    while r and d:
        a, b = r.popleft(), d.popleft()
        if a < b:
            r.append(a + n)          # R acts first, bans D, votes again next round
        else:
            d.append(b + n)
    return "Radiant" if r else "Dire"

6Task Scheduler (LeetCode 621)

🟠 Medium. CPU tasks (letters) each take one unit; identical tasks need n idle units between them. Return the minimum total time.

text

tasks = [A,A,A,B,B,B], n = 2 → 8   (A B _ A B _ A B)

Approach. The most frequent task forms the skeleton: (maxFreq − 1) full blocks of length n + 1, plus one final slot per task tied for the max frequency. If there are enough other tasks to fill every gap, no idling is needed and the answer is just the task count.

Complexity. O(T) time, O(26) space.

typescript

function leastInterval(tasks: string[], n: number): number {
  const counts = new Map<string, number>();
  for (const t of tasks) counts.set(t, (counts.get(t) ?? 0) + 1);
  const maxFreq = Math.max(...counts.values());
  const tied = [...counts.values()].filter((c) => c === maxFreq).length;
  return Math.max(tasks.length, (maxFreq - 1) * (n + 1) + tied);
}

python

def least_interval(tasks, n):
    counts = {}
    for t in tasks:
        counts[t] = counts.get(t, 0) + 1
    max_freq = max(counts.values())
    tied = sum(1 for c in counts.values() if c == max_freq)
    return max(len(tasks), (max_freq - 1) * (n + 1) + tied)

🧠 Key takeaways

Use deque / Queue<T> / a head index: pop(0) and shift() are O(n).
Time windows: append new events, evict expired ones from the front.
Monotonic deque: pop expired front, pop smaller back, push; front = window max → O(n).
Circular buffers use head, size and % capacity for O(1) fixed-size queues.

🛠️ Practice exercises

Each exercise is a file in this topic folder. Code exercises are self-checking: run them and make the checks pass.

algo_queues_and_deques_exercise_1.py

TS PY

algo_queues_and_deques_exercise_2.py

TS PY

✅ Check yourself

Answer the questions — feedback is instant.

1. Cost of arr.shift() in JavaScript on an array of n elements?

Re-indexes elements.

2. Why does the monotonic deque store indices?

Expiry needs positions.

3. Two-stack queue: when do elements move from inbox to outbox?

Each element moves once → amortized O(1).

4. Task Scheduler's answer is at least…

max(tasks, skeleton).

Source: algo_queues_and_deques_theory_1.md, algo_queues_and_deques_theory_2.md · generated by tools/build_lessons.py