leetExpert

Module 9 · Queues

Practice

Practice~1 min

How to practice this module

Queue problems hinge on FIFO order and the ring-buffer mechanics behind it. Recent Calls is a pure sliding-time queue; Queue Using Stacks forces you to reason about order preservation; First Unique and Sliding Window Maximum both need a queue of candidates. Done when all four show Solved in the hub.

Problems

Queues — work them in order; difficulty ascends.

0/4

solved

  1. 1Number of Recent CallsEasyTime-window queueWatch for: Pop the front while it is older than t - 3000; a plain FIFO of timestamps is all you need
  2. 2Implement Queue Using StacksEasyTwo-stack amortised queueWatch for: Only refill the pop stack when it is empty, or order corrupts and peek goes stale
  3. 3First Unique in a StreamMediumQueue + frequency mapWatch for: Eject repeated characters from the queue front as you discover them; '#' when the front is stale
  4. 4Sliding Window MaximumHardMonotonic dequeWatch for: Drop from the back anything smaller than the new value and from the front anything out of window — the max is the front

Cheatsheet

Queues — FIFO frontiers — BFS levels and sliding-window maxima.

Smell → pattern

  • Level-order / shortest unweightedBFS queue
  • Recent k elements aggregateDeque both ends
  • Generate in arrival orderPush back, pop front
  • Multi-source expansionSeed queue with all starts

Patterns

BFS frontier

Core

Smell: Layers from a source (or many)

Enqueue start(s), mark seen. Pop front, push unseen neighbours. Distance = layers or an explicit dist map.

0L1L2

Deque for window extrema

Safe

Smell: Max/min in every window of size k

Keep candidates at both ends: drop from back while worse than new; drop from front when out of window. Front is always the answer.

front · popback · push

Classic FIFO

Reach

Smell: Process in arrival order

Produce in the order you consume. If you need LIFO, you wanted a stack — don’t fake it with index tricks.

front · popback · push

Complexity targets

  • BFS over graph

    Time
    O(V+E)
    Space
    O(V)
    Note
    Queue + seen set

  • Deque window max

    Time
    O(n)
    Space
    O(k)
    Note
    Amortised O(1) per index

Traps

  • Forgetting the seen set

    BFS without marking visited revisits nodes and can loop forever on cycles.

  • Stale deque front

    Before reading the max/min, drop indices that slid out of the window. A stale front is the classic off-by-k bug.