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.

from collections import deque
 
queue = deque()
queue.append("first")    # enqueue to the right
queue.append("second")
front = queue[0]         # peek without removing
queue.popleft()          # dequeue from the left: O(1)

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.

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).

Canonical examples

Binary tree level order traversal

Process a tree level by level. The key insight: snapshot level_size = len(queue) at the start of each outer loop iteration. Process exactly that many nodes - that is exactly one level. Their children form the next level and get counted in the following iteration.

Sliding window maximum

The monotonic deque with no tree required. Each index enters the deque once and exits at most once, so the total work is O(n) regardless of window size.

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.

Practice problems

• Binary Tree Level Order Traversal - The canonical BFS template on a tree.
• Rotting Oranges - Multi-source BFS; all rotten oranges start spreading simultaneously.
• Sliding Window Maximum - Monotonic deque in its clearest form.
• Number of Recent Calls - Queue as a sliding time window.
• Design Circular Queue - Implement the underlying structure from scratch.