Context first
A queue serves items in the order they arrived: FIFO, First In, First Out. You add at the back (enqueue) and remove from the front (dequeue). It is the queue at a shop, modelled exactly.
Why the Naive Implementation Is Wrong
If you implement a queue as a plain array and dequeue by removing element 0, every dequeue shifts all remaining elements down one position — that is O(n), not O(1).
Real implementations avoid this. A linked list with head and tail pointers gives O(1) at both ends. Or you keep the array and move pointers instead of data, which leads directly to the circular queue.
Circular Queues Reuse the Space
Switch to circular mode. Instead of shifting elements, two indices — front and rear — move forward and wrap around using modulo arithmetic:
Dequeue several items then enqueue more, and watch the queue wrap past the end of the array to reuse the freed slots. This is how fixed-size buffers work in networking, audio streaming and embedded systems, where allocating memory on the fly is not an option.
The Insight That Matters Most
Choose Stack vs queue traversal and step through. Both run identical code over the same graph. The only difference is where pending nodes are taken from:
- Take from the end (stack, LIFO) → you dive deep down one branch first. That is depth-first search.
- Take from the front (queue, FIFO) → you sweep level by level. That is breadth-first search.
One data-structure choice completely changes the traversal order — and with it, whether the algorithm finds the shortest path. BFS does; DFS does not.
Variants Worth Knowing
- Deque (double-ended queue) — add and remove at both ends. Can act as either a stack or a queue.
- Priority queue — serves the highest priority item rather than the oldest. Usually built on a heap, and the engine behind Dijkstra and A*.
- Blocking queue — waits when empty or full. The standard tool for passing work between threads.
First in, first out
A queue adds at one end and removes from the other. The oldest item is served first, which is what "queue" means outside computing too.
| Operation | Meaning | Cost |
|---|
| enqueue | Add to the back | O(1) |
| dequeue | Remove from the front | O(1) |
| peek | Look at the front | O(1) |
| is_empty | Nothing left | O(1) |
In Python, use collections.deque and not a list:
from collections import deque
q = deque()
q.append(1) # enqueue at the back
q.append(2)
q.popleft() # 1 - dequeue from the front, O(1)
A list is the wrong choice. list.pop(0) shifts every remaining element, so it is O(n), and a loop dequeuing n items becomes O(n²). This is the single most common queue performance bug, and it is easy to miss because the code looks correct and works on small inputs.
deque is implemented as a doubly linked list of fixed-size blocks, giving O(1) at both ends with far better cache behaviour than one node per element.
Why BFS needs a queue
The clearest use, and the reason it appears in every graph algorithm discussion.
Breadth-first search must process all nodes at distance 1 before any at distance 2. A queue's first-in-first-out order produces exactly that: neighbours added later are processed later, so exploration proceeds in rings.
def bfs(graph, start):
visited = {start}
q = deque([start])
while q:
node = q.popleft()
for nbr in graph[node]:
if nbr not in visited:
visited.add(nbr)
q.append(nbr)
return visited
Swap popleft() for pop() and the same code becomes depth-first search. The data structure is the algorithm's traversal order — which is the neatest illustration of why choosing the right structure matters.
The variants
| Type | Behaviour | Python |
|---|
| Simple queue | FIFO | collections.deque |
| Deque | Add and remove at both ends | collections.deque |
| Priority queue | Highest priority first | heapq |
| Circular buffer | Fixed size; overwrites oldest | deque(maxlen=n) |
| Blocking queue | Waits when empty or full | queue.Queue |
deque(maxlen=n) deserves a mention because it is genuinely useful and under-known: it silently discards from the opposite end when full, which gives you a rolling window of the last n items in one line. Ideal for recent-events buffers and moving-window statistics.
Priority queues are not FIFO at all — they serve by priority, and they are heaps. Dijkstra's algorithm is BFS with a priority queue substituted for the plain queue.
queue.Queue adds locking for producer-consumer communication between threads. It is slower than deque and that is the price of thread safety; use deque in single-threaded code.
Why list.pop(0) is the bug, and what to use instead
A queue built on a Python list looks correct and is quadratic. This is the single most common performance mistake in code that processes work in FIFO order, and it is worth seeing measured, because nothing about the code looks slow.
Experiments to try
- Enqueue A, B, C then dequeue. A comes out first — the opposite of a stack.
- Switch to circular mode. Dequeue a few, enqueue a few more, and watch the indices wrap around to reuse slots instead of shifting data.
- Fill the circular queue completely and try one more enqueue — it reports full, because a fixed buffer cannot grow.
- Open Stack vs queue traversal and step through. Watch the two visit orders diverge from the very first branch.
- Note the BFS order. It finishes each level before starting the next, which is exactly why it finds shortest paths in unweighted graphs.
Worth remembering
A queue preserves arrival order with O(1) work at both ends, provided you move pointers rather than data. Its most important property in algorithms is level-by-level processing — swapping a stack for a queue turns depth-first search into breadth-first search and nothing else changes.
Where queues appear in systems
- Task and job queues. Celery, RabbitMQ, SQS — work is enqueued by producers and processed by workers. This is the dominant pattern for decoupling components in distributed systems.
- Request handling. Web servers queue incoming connections when all workers are busy.
- Print spoolers and scheduling. The original example, and still accurate.
- Buffering between fast and slow components — keyboard input, network packets, audio samples.
- Rate limiting. A queue of timestamps gives a sliding-window limiter.
- BFS and level-order traversal.
- Producer-consumer pipelines, where a bounded queue provides backpressure.
That last point is worth expanding. A bounded queue is a design decision, not a limitation: when it fills, producers block, which propagates backpressure upstream instead of allowing unbounded memory growth. An unbounded queue under sustained overload does not fail gracefully — it consumes memory until the process dies.
So queue depth is a monitoring signal. A steadily growing queue means consumers cannot keep up, and it is a leading indicator of failure well before latency becomes visible to users.
Circular buffers
A fixed-size array with two indices — head and tail — that wrap around using modulo arithmetic.
next index = (index + 1) % capacity
The advantages are no allocation after construction and perfect cache behaviour, which is why they are used in embedded systems, audio processing and network drivers where allocation during operation is unacceptable.
The design decision is what to do when full: reject the new item, block until space is available, or overwrite the oldest. deque(maxlen=n) takes the third option, which is right for "keep the most recent n" and wrong for a work queue where losing tasks is unacceptable.
Queue against stack
| | Queue | Stack |
|---|
| Order | First in, first out | Last in, first out |
| Graph traversal | Breadth-first | Depth-first |
| Memory during traversal | The frontier width | The path depth |
| Natural for | Fairness, scheduling, distance | Backtracking, nesting, undo |
| Python | collections.deque | list |
The memory row decides which is usable on a large graph: a queue holds an entire level, which on a wide graph can be enormous; a stack holds one path.
Two stacks can simulate a queue, and two queues can simulate a stack — a classic exercise that illustrates the relationship, and not something to do in practice.
Questions people ask
Why not use a list as a queue? pop(0) is O(n) because it shifts every element. Use deque.
Is deque thread-safe? append and popleft are atomic thanks to the GIL, so it works for simple producer-consumer use. queue.Queue adds proper blocking semantics.
What is a priority queue? A queue ordered by priority rather than arrival, implemented as a heap. Not FIFO.
How do I limit a queue's size? deque(maxlen=n) to discard the oldest, or queue.Queue(maxsize=n) to block producers.
Why do distributed systems use queues? They decouple producers from consumers, absorb bursts, allow retries, and let the two sides scale and fail independently.
What is backpressure? Slowing producers when the queue fills, so overload propagates upstream rather than exhausting memory.
Recap in one screen
- Add at the back, remove from the front; the oldest item is served first.
- Use
collections.deque — a list's pop(0) is O(n) and turns traversals quadratic. - A queue makes graph traversal breadth-first, exactly as a stack makes it depth-first.
deque(maxlen=n) gives a rolling window of the last n items for free.- In systems, queues decouple components and provide backpressure — and queue depth is an early warning signal.