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)
Queues (FIFO)
Fair ordering by construction — and the one change that turns DFS into BFS.
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.
example_01.pyPython
import time
from collections import deque
def drain_list(n):
q = list(range(n))
steps = 0
while q:
q.pop(0) # removes the FRONT: shifts every other element
steps += 1
return steps
def drain_deque(n):
q = deque(range(n))
while q:
q.popleft() # O(1): no shifting
# The browser clock is quantised to about a millisecond, and draining a
# deque is far quicker than that -- so repeat it and divide, or the fast
# column reads a meaningless zero.
REPS = 50
def ms(fn, n, reps=1):
t0 = time.time()
for _ in range(reps):
fn(n)
return (time.time() - t0) * 1000 / reps
print("%8s %14s %14s %10s" % ("n", "list (ms)", "deque (ms)", "ratio"))
for n in (2000, 4000, 8000, 16000):
a = ms(drain_list, n)
b = ms(drain_deque, n, REPS)
print("%8d %14.2f %14.2f %10.0f" % (n, a, b, a / b))
# Double n and the list column roughly quadruples: that is the signature
# of O(n^2). The deque column doubles, as an O(n) total should.
#
# The reason is what pop(0) has to do. A Python list is a contiguous
# array, so removing the first element moves every remaining element one
# slot to the left -- n-1 moves, for every one of the n removals.
print()
print("total element moves when draining a list of n with pop(0):")
for n in (10, 100, 1000):
print(" n = %5d -> %d moves (n(n-1)/2)" % (n, n * (n - 1) // 2))
# append() and pop() at the END are both O(1), so a list is a perfectly
# good STACK. It is specifically the front that is expensive, and that is
# what makes it the wrong shape for a queue.
#
# A deque is a doubly-linked list of blocks, so both ends are O(1):
d = deque([2, 3, 4])
d.appendleft(1)
d.append(5)
print()
print("deque after appendleft(1) and append(5):", list(d))
print("popleft:", d.popleft(), " pop:", d.pop(), " left:", list(d))
# The classic alternative, before deques, was the CIRCULAR buffer: a
# fixed array with head and tail indices that wrap around with modulo,
# so nothing is ever shifted and the space is reused.
class Circular:
def __init__(self, cap):
self.a = [None] * cap
self.head = self.size = 0
def push(self, x):
if self.size == len(self.a):
return "full"
self.a[(self.head + self.size) % len(self.a)] = x
self.size += 1
def pop(self):
if not self.size:
return "empty"
x = self.a[self.head]
self.head = (self.head + 1) % len(self.a)
self.size -= 1
return x
c = Circular(4)
for x in "abcd":
c.push(x)
print()
print("full buffer:", c.a, "head =", c.head)
print("pop:", c.pop(), "pop:", c.pop())
c.push("e"); c.push("f")
print("after pushing e and f:", c.a, "head =", c.head)
# e and f landed in slots 0 and 1 -- the space a and b vacated. The array
# never grew and nothing moved; only the two indices changed. That is why
# this is the structure in ring buffers, audio pipelines and network
# stacks, where the memory is fixed up front and cannot be reallocated.
Output
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.
Where to practise this
Two follow-ons worth doing with a queue in front of you:
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.
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)
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.
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.