Queues

What is a queue?

A queue is a FIFO (first-in, first-out) data structure: elements are removed in the same order they were added. It is the engine of BFS - by processing nodes in arrival order, it guarantees that each node is visited at the shortest possible distance from the source.

In Python, the right tool is collections.deque, not a list. A list looks tempting because list.append and list.pop(0) seem to work, but list.pop(0) is O(n): it shifts every remaining element one position left. deque.popleft() is O(1) because the deque maintains explicit head and tail pointers.

The core trade-off: O(1) enqueue and dequeue from both ends, but no random access. Indexing into a deque by position is O(n). Use a deque when you care about the order of arrival and need fast front-removal; use a list when you need fast index lookup.

Core operations

Key patterns

BFS traversal

Visit nodes in waves outward from a source, dequeuing the front node and enqueuing its unvisited neighbors.

When to use - you need the shortest path or fewest hops in an unweighted graph or grid, or you want to walk a tree level by level. The naive alternative reruns a search from scratch for each target or tries DFS, which can reach a node by a longer path first; BFS settles every node at its true distance in one O(V + E) pass.

How it works - the queue holds nodes to visit in arrival order. Pop the front node, then enqueue its unvisited neighbors at the back. Because every neighbor lands after the current node's whole level, all nodes at distance d come off the queue before any at distance d+1 - that ordering is the invariant that makes the first arrival at a node its shortest one. Mark a node visited the moment you enqueue it so it never enters the queue twice.

Example: process arrivals in FIFO order. On the default graph (0-1, 0-2, 1-3, 2-3, 3-4, start 0), expanding node 0 enqueues 1 and 2, expanding 1 enqueues 3, and expanding 2 finds 3 already visited, so the queue drains [1, 2] to [2, 3] to [3] to [4] with nothing jumping the line. Nodes leave in exactly the order they arrived, which is why both distance-1 nodes process before any distance-2 node and the visit order reads 0, 1, 2, 3, 4. The visualizer below walks the frontier wave by wave.

Monotonic deque (sliding window maximum)

Keep a deque of indices whose values stay in decreasing order, so the front is always the current window's maximum.

When to use - you need the minimum or maximum of every sliding window as it moves across an array. Rescanning each window costs O(n*k); the monotonic deque tracks the extreme without rescanning and turns the whole sweep into O(n).

How it works - each step does two cleanups. First, popleft any index that has fallen behind the window's left edge. Second, pop from the back every index whose value is smaller than the incoming element - those can never be the maximum while the newcomer remains in the window. Then append the new index. The front now holds the index of the window's maximum. Store indices, not values, because you need the position to know when an element has left the window. Each index is appended once and removed at most once, so the total work across all n steps is O(n).

Example: max of every size-3 window. Given [8, 2, 7, 4, 9, 1] with k = 3, the incoming 7 pops the 2 off the back (a smaller value can never be the max while 7 is in the window), and the first full window reports 8. Sliding to 4 drops the expired 8 from the front for a max of 7, then the 9 evicts both 4 and 7 from the back and the trailing 1 cannot touch it, so the last two windows both read 9. Maxima: 8, 7, 9, 9 - the visualizer below moves the window one index at a time.

When to reach for a queue

• You need BFS - level-by-level traversal or shortest path in an unweighted graph.
• The problem involves processing items in the order they arrive - task scheduling, rate limiting.
• You need sliding window minimum or maximum - monotonic deque.
• The problem talks about levels, layers, or rounds of processing.
• You need to print or group nodes of a tree by depth level.