Topics

Stacks and Queues: A Study Guide

Stacks and queues are the two simplest ordered collections, and they differ by a single rule: which end you remove from. A stack is last-in, first-out (LIFO): the most recently added item leaves first. A queue is first-in, first-out (FIFO): items leave in arrival order. That one distinction decides whether you get depth-first or breadth-first behavior, undo history or task scheduling.

Why They Matter#

These structures are the quiet engines behind a surprising number of algorithms. Depth-first search uses a stack (often the call stack). Breadth-first search uses a queue. Expression parsing, matching brackets, backtracking, and the monotonic-stack pattern are all stack problems. Sliding-window maximums and level-order tree traversals are all queue problems.

Key Operations and Their Big-O#

Both structures are built for O(1) access at their working end:

StructureOperationTime
Stackpush / pop / peekO(1)
Queueenqueue / dequeue / peekO(1)
EithersearchO(n)

In Python, use a list for a stack (append and pop) and collections.deque for a queue (append and popleft). Avoid list.pop(0) for a queue: it is O(n) because every remaining element shifts.

A Short Example#

Matching brackets is the classic stack problem:

 1def is_balanced(s):
 2    pairs = {")": "(", "]": "[", "}": "{"}
 3    stack = []
 4    for ch in s:
 5        if ch in "([{":
 6            stack.append(ch)
 7        elif ch in pairs:
 8            if not stack or stack.pop() != pairs[ch]:
 9                return False
10    return not stack   # leftover openers mean unbalanced

Common Pitfalls#

  • Using list.pop(0) as a queue. It looks right and passes small tests, then times out. Reach for deque.
  • Popping an empty stack. Always guard with if stack before pop, or you get an IndexError.
  • Confusing which end is “the top.” Decide early whether the end of the list or the front is your working end, and stay consistent.
  • Recursion depth. DFS via recursion is a stack too, and Python caps it near 1000 frames. Convert to an explicit stack for deep inputs.

Where the Curriculum Covers This#

In the 60-day challenge: