Queues

First in, first out: the structure behind breadth-first search, level-order traversal, ring buffers and the monotonic deque for sliding window maximum.

Overview

What a queue is

A queue is a line. You add at the back (enqueue) and take from the front (dequeue), so the item that waited longest leaves first: FIFO, first in, first out. Both operations cost O(1) with the right structure.

A queue is the right tool whenever items must be handled in the order they arrived, or when you must finish everything at distance d before anything at distance d + 1.

Enqueue — q.append(x) — q.offer(x) — O(1)
Dequeue — q.popleft() — q.poll() — O(1)
Peek front — q[0] — q.peek() — O(1)
Is empty — not q — q.isEmpty() — O(1)

Do not use a Python list as a queue. list.pop(0) shifts every remaining element, so it costs O(n); the Python docs say so and point to deque. In Java, poll() and peek() return null on an empty queue, while remove() and element() throw.

The queue family

"Queue" names several structures. Pick by what decides who leaves next.

Queue (FIFO) — the oldest item — O(1) at each end — BFS, buffering, scheduling in order
Deque — either end, your choice — O(1) at both ends — sliding window, 0-1 BFS, palindrome checks
Circular queue (ring buffer) — the oldest, in a fixed array — O(1), no resizing — fixed-size buffers, streams
Priority queue — the smallest (or largest) key — O(log n) add and remove — Dijkstra, top k, scheduling by priority
Blocking queue — the oldest; callers wait when empty or full — O(1) plus locking — producer and consumer threads

Breadth-first search: why FIFO gives shortest paths

BFS starts at one node and visits nodes in order of distance. The queue is what makes that true: every node at distance d is enqueued before any node at distance d + 1, and FIFO hands them back in that order. So the first time BFS reaches a node, it has found a shortest path to it (counting edges).

A — B (1), C (1) — B, C
B — D (2) — C, D
C — E (2); D already seen — D, E
D — F (3) — E, F
E — none; F already seen — F
F — none — empty

Mark a node as seen when you enqueue it, not when you dequeue it. Otherwise D would be enqueued twice (from B and from C), and on dense graphs the queue can grow far beyond the number of nodes.

Levels and many starting points

Two small changes cover most queue problems.

Level by level. Read len(queue) at the start of a round and dequeue exactly that many. Those are all the nodes of one level. This gives level-order traversal of a tree and a clean way to count minutes or steps.
Many sources. Put every starting node in the queue before the loop, all at distance 0. BFS then spreads from all of them at once. In Rotting Oranges, every rotten orange is a source and each level is one minute.

Rotting Oranges on the grid [[2,1,1],[1,1,0],[0,1,1]] (2 rotten, 1 fresh, 0 empty):

0 — start: the rotten one at (0,0) — 6
1 — (0,1), (1,0) — 4
2 — (0,2), (1,1) — 2
3 — (2,1) — 1
4 — (2,2) — 0: answer 4

If fresh oranges remain when the queue empties, some are unreachable and the answer is -1.

Circular queue: a fixed array that wraps

A circular queue stores items in a fixed array. The front index and the count locate them; the back is (front + count) % capacity. When an index reaches the end of the array it wraps to 0, so freed slots at the start are reused and nothing ever shifts.

Here is the trace with capacity 3.

enqueue 1 — 1 _ _ — 0 — 1
enqueue 2 — 1 2 _ — 0 — 2
enqueue 3 — 1 2 3 — 0 — 3 — full
dequeue, returns 1 — _ 2 3 — 1 — 2
enqueue 4 — 4 2 3 — 1 — 3 — back wrapped to slot 0
dequeue, returns 2 — 4 _ 3 — 2 — 2

Keeping a count avoids the classic trap: with only front and back indices, an empty queue and a full queue look the same (front == back). The other fix is to leave one slot always unused.

The monotonic deque: sliding window maximum

To get the maximum of every window of size k, keep a deque of indices whose values decrease from front to back. For each new index, three steps run in order.

Drop the front if it has left the window.
Pop from the back every index whose value is smaller than the new value; those can never be a maximum again.
Push the new index at the back. The front is now the window's maximum.

Here is the trace on [1, 3, -1, -3, 5, 3, 6, 7] with k = 3.

0 — 1 — 0:1
1 — 3 — 0 — 1:3
2 — -1 — 1:3, 2:-1 — 3
3 — -3 — 1:3, 2:-1, 3:-3 — 3
4 — 5 — 1 — 3, 2 — 4:5 — 5
5 — 3 — 4:5, 5:3 — 5
6 — 6 — 5, 4 — 6:6 — 6
7 — 7 — 6 — 7:7 — 7

The result is [3, 3, 5, 5, 6, 7]. Each index enters the deque once and leaves at most once, so the whole pass is O(n), against O(n·k) for rescanning every window. The back behaves like a monotonic stack; the front is what makes it a queue.

A queue from two stacks

The idea is to push onto an in-stack. To dequeue, if the out-stack is empty, pour the whole in-stack into it (which reverses the order) and pop from the out-stack.

push 1, push 2 — 1, 2
pop — 2 — 1 (after pouring 2, 1 across)
push 3 — 3 — 2
pop — 3 — 2
pop — 3 (after pouring 3 across)

A single pop can cost O(n) when it pours, but every item is moved at most once from in to out, so n operations cost O(n) in total: amortized O(1) each.

Picking the queue type in your language

Plain FIFO, one thread — collections.deque — ArrayDeque (its docs say it is likely faster than LinkedList as a queue)
Priority queue — heapq on a list — PriorityQueue: O(log n) offer and poll, not synchronized
Fixed-size recent history — deque(maxlen=k): adding to a full deque drops the oldest from the other end — a ring buffer you write, or ArrayBlockingQueue
Shared between threads, blocking — queue.Queue (it handles the locking) — ArrayBlockingQueue (bounded) or LinkedBlockingQueue
Shared between threads, non-blocking — ConcurrentLinkedQueue (the Michael and Scott algorithm)

What you will be able to do

Choose between a FIFO queue, a deque, a ring buffer, a priority queue and a blocking queue.
Explain why BFS with a queue finds shortest paths in unweighted graphs, and mark nodes at the right moment.
Process a BFS level by level and start it from many sources.
Trace a monotonic deque for sliding window maximum and argue it is O(n).
Build a circular queue and a queue from two stacks, and explain their costs.

When to use it

Shortest path by edge count in an unweighted graph or grid (BFS)
Level-order traversal of a tree, or counting steps or minutes
Spreading from many starting points at once (multi-source BFS)
Sliding window maximum or minimum (monotonic deque)
A fixed-size buffer of recent items (ring buffer, moving average, recent calls)
Handling tasks or requests strictly in arrival order
Passing work between producer and consumer threads (blocking queue)

More Coding & DSA topics

Start free on Cariara · Coding problems · System design studio