Stacks & queues — small structures, huge reach

Two of the most-used structures in computer science, and the difference between them is a single sentence.

A stack is Last-In-First-Out. The most recently added item is the next one to come out. Like a stack of plates — you take the top one off, you put new ones on top.

A queue is First-In-First-Out. The earliest added item is the next one to come out. Like a line at a coffee shop — first in line, first served.

Both structures support two operations. For a stack, push (add to top) and pop (remove from top). For a queue, enqueue (add to back) and dequeue (remove from front). Both are O(1).

Where they show up.

Stacks — function calls (the call stack). Undo/redo (recent action goes on top). DFS (depth-first traversal — push neighbours, pop one off, recurse). Expression parsing (operator precedence, balanced parentheses). Backtracking algorithms.

Queues — BFS (breadth-first traversal — enqueue neighbours, dequeue the front). Task scheduling (jobs in submission order). Producer-consumer patterns. Async event loops. Message queues like Kafka, RabbitMQ.

In Python:

For a stack — use list. append() pushes; pop() removes from the end. O(1) on both. The list IS a stack.

For a queue — use collections.deque, NOT list. append() and popleft() are both O(1). list.pop(0) is O(n) because it shifts all elements left. This is the most common Python perf bug I see in junior code.

The rule — pick by access pattern, then pick by Python's right structure. Stack = list. Queue = deque. Don't conflate them.

Given a string of brackets like '({[]})' — is it balanced? Each opening bracket has a matching closing bracket of the same type, in the right order. The stack solves it elegantly.

The pattern — walk the string left to right. On opening brackets, push them onto a stack. On closing brackets, pop the top of the stack and check it's the matching opener. End with the stack empty — balanced. End with non-empty stack or any mismatch — not balanced.

Why a stack is the right structure — closing brackets match the MOST RECENT unclosed opening bracket. That's exactly stack semantics. Last in, first out.

The pattern generalises far beyond parentheses.

HTML/XML parsers. Open tags push; close tags pop and check.

Markdown rendering. Bold/italic markers in nested order.

Function call frames. Each call pushes a frame; each return pops one.

Undo/redo. Each action pushes onto an undo stack; each undo pops to a redo stack.

Backtracking algorithms. Push state at decision points; pop to backtrack.

The broader pattern is 'process tokens left to right, defer some to a stack, resolve when a closing token arrives'. Once you can recognise it, you'll see it constantly. Compilers parse with it. Many DP problems unfold with stack-based dispatch.

A tip for the parentheses problem specifically — use a dict to map closers to openers. {')' : '(', ']': '[', '}': '{'}. Then on a closer, pop and compare to dict[closer]. Cleaner than chained if-statements.

A fun extension — given a string with letters AND brackets, find the longest valid balanced substring. Stack-based, but trickier. Worth solving once for fluency.

Memorise this template. Adapt the 'neighbours' function. You've solved a quarter of all graph and grid problems.

from collections import deque

def bfs(start, neighbours):
    q = deque([start])
    seen = {start}
    order = []
    while q:
        node = q.popleft()
        order.append(node)
        for nb in neighbours(node):
            if nb not in seen:
                seen.add(nb)
                q.append(nb)
    return order

The shape — a deque as the queue, a set tracking seen nodes (so we don't revisit), a loop that pops from the front, processes the node, and enqueues unseen neighbours.

Why BFS visits in distance order — because it's a queue. The first node enqueued is the start. Its neighbours are enqueued next, all distance 1. Then their neighbours, all distance 2. Distance grows monotonically as nodes leave the queue. This is why BFS finds shortest paths in unweighted graphs.

What the 'neighbours' function does — encapsulates how you get the adjacent nodes. For a graph stored as adjacency list, return graph[node]. For a grid, return the four (or eight) cardinal neighbours that are in-bounds. For a state-space search, return the legal next states.

Variations.

Level-order traversal — track the level you're on by keeping a separate counter or processing the queue in batches of len(q) at a time.

Shortest path — track parent pointers as you visit; reconstruct the path from end to start at the end.

Multi-source BFS — start with multiple nodes in the queue. All are 'distance 0'. The closest source to each unseen node is found in O(V + E).

Word ladder, knight's tour, friendship-degrees, num-islands — all variations on this template. Code the template once; reach for it forever.

This is a tip I should put on a billboard. It's the most-common Python perf bug I see in junior code, and the fix is one import line.

Bad:

q = []
q.append(x)         # add to back — O(1), fine
q.pop(0)            # remove from front — O(n), DISASTER

list.pop(0) is O(n) because removing from the front means shifting every other element left by one position. In a queue with thousands of items, every pop touches thousands of elements. Your nominally-O(n) BFS becomes O(n²).

The fix is collections.deque (double-ended queue):

from collections import deque
q = deque()
q.append(x)         # O(1)
q.popleft()         # O(1) — !

Deque is implemented as a doubly-linked list of fixed-size blocks. Append, appendleft, pop, popleft are all O(1). Random access is O(n) (it's not designed for indexing) — for that, use list.

The broader rule — pick the right Python structure for your access pattern.

Front-and-back access (queue, double-ended pipe) — deque.

Back-only access (stack) — list.

Min/max retrieval (priority queue) — heapq (we cover Day 24).

Key-based access — dict.

Unique items, membership tests — set.

Sorted-on-insert — bisect on a list, OR sortedcontainers' SortedList.

The time you save by using the right structure on day one is more than the time you'd spend understanding why your code got slow.

Never use list.pop(0) or list.insert(0, x). They look innocent. They're not.

End of Day 20. Two-thirds through DSA week one. The structural foundations are mostly in place; tomorrow we wrap with sliding window deep dive.

What we covered today.

Morning, the difference between stack and queue boils down to access pattern — LIFO versus FIFO. Stack for back-and-forth, queue for steady flow. Picking the right one matches the structure to the problem.

Midday, the parentheses pattern. Walk the string, push openers, pop and check on closers. End empty = balanced. The pattern generalises to HTML parsing, function call frames, undo/redo, and any 'most recent unclosed thing' situation.

Afternoon, the BFS template. Deque + seen set + while loop. The shape is the same for graphs, grids, state-space searches. Adapt the 'neighbours' function to your problem; the rest is reusable.

Evening, the most-common Python performance bug. Using list as a queue with .pop(0) — quadratic. Use collections.deque — linear. One import line, dramatic speedup.

A reflection at the day-20 mark. We've now covered all the basic structures (array, string, linked list, hash map, set, stack, queue) and most of the common patterns (two-pointer, sliding window, BFS, dedup, group-by). Tomorrow's sliding window post and Friday's wrap consolidate everything; then week 4 goes deeper into recursion, search, sort, trees, graphs, and DP.

Tomorrow, Day 21, sliding window deep dive. The pattern that solves most 'longest/shortest/best subrange' problems. We've used it once in the longest-substring problem; tomorrow we generalise.

See you in the morning.