First in, first out — add at the back, remove from the front. Swap a stack for a queue in a graph traversal and depth-first search becomes breadth-first, without changing another line.
Controls
The same traversal code, differing only in whether the pending list is a stack or a queue.
The Queue
step 0
front →
← back
DFS — stack
BFS — queue
Insight
A queue is open at both ends: you enqueue at the back and dequeue from the front. Order is preserved — fairness by construction.
Where queues are used
• Breadth-first search
• Task & job scheduling
• Printer / request queues
• Message brokers & buffers
• Rate limiting
size0
front–
back–
Complexity
Enqueue / DequeueO(1)
SearchO(n)
SpaceO(n)
Overview
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.
Context first
Queues appear wherever work needs to be processed in the order it was submitted. A web server queues incoming requests.
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.
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.
Experiments to try with Queues
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.
Three queues: the naive list version, the deque that fixes it, and a fixed-size circular buffer. The middle block times the first two so the O(n) is a measurement, not a claim.
queues.pyPython 3
# A queue: add at the back, remove from the front. First in, first out.
from collections import deque
import time
# --- 1. the obvious version, and why it is wrong -----------------------
class ListQueue:
def __init__(self):
self._items = []
def enqueue(self, x):
self._items.append(x)
def dequeue(self):
return self._items.pop(0) # O(n): every other item shifts left
class DequeQueue:
def __init__(self):
self._items = deque()
def enqueue(self, x):
self._items.append(x)
def dequeue(self):
return self._items.popleft() # O(1): no shifting at all
q = DequeQueue()
for x in "ABC":
q.enqueue(x)
print(f"enqueue {x} -> {list(q._items)}")
print(f"dequeue -> {q.dequeue()} (the oldest), left: {list(q._items)}")
# --- 2. the cost, measured --------------------------------------------
print()
N = 30_000
for cls in (ListQueue, DequeQueue):
q = cls()
for i in range(N):
q.enqueue(i)
start = time.time()
for _ in range(N):
q.dequeue()
print(f"{cls.__name__:>12}: {N} dequeues in {time.time() - start:.3f}s")
# --- 3. a circular buffer: fixed memory, no shifting -------------------
class RingQueue:
def __init__(self, capacity):
self._items = [None] * capacity
self._head = self._size = 0
self._cap = capacity
def enqueue(self, x):
if self._size == self._cap:
raise OverflowError("queue is full")
self._items[(self._head + self._size) % self._cap] = x
self._size += 1
def dequeue(self):
x = self._items[self._head]
self._head = (self._head + 1) % self._cap # wrap around
self._size -= 1
return x
print()
ring = RingQueue(4)
for x in "ABCD":
ring.enqueue(x)
print("full ring :", ring._items, "head", ring._head)
ring.dequeue(); ring.dequeue()
ring.enqueue("E")
print("after 2 out, 1 in:", ring._items, "head", ring._head)
print("E landed in the slot A left behind - nothing was ever moved.")
Output
How the code works
self._items.pop(0)The bug that hides in plain sight. Removing the first element of a Python list moves every remaining element one place left, so a queue built this way is O(n) per dequeue and quadratic overall.
self._items.popleft()deque is a doubly linked list of blocks, so both ends are O(1). This is the right answer in Python, and the timing loop above shows the gap on 50,000 items.
(self._head + self._size) % self._capThe modulo is what makes the buffer circular: index 4 of a 4-slot ring is index 0. Writing past the end wraps to the space the front has already vacated.
self._head = (self._head + 1) % self._capDequeuing moves a pointer instead of moving data. That is the whole idea — the same fixed block of memory is reused forever, which is why ring buffers run in device drivers and audio pipelines.
if self._size == self._cap: raise OverflowErrorA ring must track size separately: head and tail meeting is ambiguous between full and empty. Getting this wrong silently overwrites the oldest entry.
Change one thing
Raise N to 200,000. The deque timing scales linearly; the list version takes roughly sixteen times as long, not four.
Make RingQueue overwrite the oldest item instead of raising. You have just written the standard “last N events” log buffer.
Build a BFS on top of ListQueue instead of deque, then run it on a large graph. Same answer, unrecognisable running time.
Where this runs
Real CPython, compiled to WebAssembly and running on your own machine — nothing is uploaded. The first run takes a few seconds while the interpreter downloads; after that it is immediate. Need more room, or want to paste your own attempt? Use the Python compiler.
Predict, then reveal
About to run: Enqueue A, B, C then dequeue. Before it does — what happens to the readout?
Committing to an answer first is the point — the reveal runs the experiment on the visualisation above and reads the real value back, so nothing here is scripted.
Check yourself
0 of 3
Answer without scrolling back up.
Why is a queue built on list.pop(0) slow?
O(n) per dequeue, so O(n²) to drain the queue. The program times 30,000 dequeues both ways.
collections.deque gives O(1) at both ends because it is:
There is no contiguous array to shift, so appending or popping at either end is a pointer update.
A circular buffer must track its size separately because:
Both states have head == tail. Getting this wrong silently overwrites the oldest entry.
Cheat sheet
Queues (FIFO)
Add at the back, remove from the front — FIFO ordering — and see how swapping a stack for a queue turns DFS into BFS.
Ashish Jangra builds and maintains VizLearn. Every module here is written and the visualisation behind it hand-built, so the numbers in a readout come from the same code that draws the picture. Corrections are genuinely welcome and get priority over everything else — if a page states something wrong, or an animation misrepresents what the algorithm does, get in touch.