Stacks, Queues & Deques

A stack works like a pile of plates: you always take from the top, and you always add to the top. Whatever went on last comes off first — LIFO, last in, first out.

A queue works like the line at a counter: the person who arrived first gets served first. Whatever went in first comes out first — FIFO, first in, first out.

That is the entire conceptual distinction. Everything else — the call stack, undo history, BFS, sliding windows — falls out of choosing the right ordering rule.

The intuition, hands-on

Pick a mode below and push a few items in. Switch modes and notice where the removal happens: top for a stack, front for a queue. The highlighted item after each removal shows which ordering rule is in effect.

Where each structure shows up

Stacks in the wild

The call stack. Every time your program calls a function, a frame is pushed onto the call stack. When the function returns, the frame is popped. That is why a stack overflow is called a stack overflow — the stack ran out of space.

Undo history. Your editor pushes every action onto a stack. Ctrl+Z pops the most recent one. The most recent action is always the one you want to undo — LIFO is exactly right.

Depth-first search (DFS). Recursive DFS uses the call stack implicitly. Iterative DFS keeps an explicit stack of nodes to visit next — you push neighbors, pop the next node to explore.

Expression and bracket parsing. Opening brackets get pushed; every closing bracket pops and checks whether it matches the top. This is the foundation of compilers and linters.

Queues in the wild

Breadth-first search (BFS). You start with one node, enqueue its neighbors, then process them in arrival order — guaranteeing you visit all nodes at distance k before any at distance k + 1. A stack produces DFS; a queue produces BFS.

Task and job queues. Background workers pull jobs off a queue in arrival order. The first task submitted is the first processed — fairness requires FIFO.

Deques

A deque (double-ended queue) allows push and pop from both ends in O(1). It generalizes stack and queue. The main algorithmic use is the sliding-window maximum/minimum problem: as the window slides, you pop stale indices from the front and pop dominated elements from the back, maintaining a monotonic deque that answers “what is the max in this window?” in O(1) per step.

Python: the right tool for each job

Stack: a plain list works

stack = []

stack.append("a")   # push — O(1) amortized (occasionally reallocates, but cheap on average)
stack.append("b")
stack.append("c")

top = stack.pop()   # pop from the end — O(1)
print(top)          # "c"  (LIFO)

append and pop() (no index argument) both operate on the right end of the list and are O(1). A list is a perfectly good stack.

Queue: use collections.deque

from collections import deque

q = deque()

q.append("a")       # enqueue at back — O(1)
q.append("b")
q.append("c")

front = q.popleft() # dequeue from front — O(1)
print(front)        # "a"  (FIFO)

deque is backed by a doubly-linked list of fixed-size blocks. Both append (right) and popleft (left) are O(1). That is what you want for a queue.

Deque: both ends

from collections import deque

d = deque([1, 2, 3])

d.appendleft(0)   # push to front — O(1)
d.append(4)       # push to back  — O(1)

d.popleft()       # 0  — O(1)
d.pop()           # 4  — O(1)

See it in code: bracket validator

A stack is the canonical tool for balanced-bracket checking. Push every opening bracket; when you see a closing bracket, pop and confirm the pair matches. If the stack is empty at the end, the brackets are balanced.

Quick check