Stacks & Queues
14 min
A stack is Last-In-First-Out (LIFO) — think of a stack of plates, you
only add/remove from the top. A Python list is already a perfectly good
stack: append() pushes, pop() pops, both O(1).
stack = []
stack.append(1)
stack.append(2)
stack.append(3)
stack.pop() # 3 — removes and returns the top
print(stack) # [1, 2]
Stacks show up everywhere: undo history, function call stacks, matching brackets, depth-first traversal.
Bracket/tag matching is the canonical stack problem — push on open, pop-and-check on close.
A queue is First-In-First-Out (FIFO) — like a checkout line. Using a
plain list as a queue is a trap: list.pop(0) is O(n) because every
remaining element shifts left. Use collections.deque instead — it's a
doubly linked list under the hood, so both ends are O(1).
from collections import deque
q = deque()
q.append("a") # enqueue at the right
q.append("b")
q.popleft() # "a" — dequeue from the left, O(1)
Write a function `is_balanced(s)` that returns True if every bracket in `s` (only the characters `()[]{}` matter) is properly opened and closed in the right order, False otherwise.
Write a function `evaluate_postfix(tokens)` that evaluates a postfix (Reverse Polish) expression, given as a list of string tokens like `["2", "1", "+", "3", "*"]`, and returns the integer result. Division should truncate toward zero.
Which built-in Python structure gives O(1) append AND O(1) pop from BOTH ends (unlike a list)?
You can implement stack-based algorithms (bracket matching, postfix evaluation) and know why deque beats list for queues.