Stacks and queues — the basics

Two of the simplest possible data structures, defined entirely by which end you're allowed to add and remove from — and that one restriction is what makes each one useful.

Beginner

4 min read

A stack: last in, first out (LIFO)

stack = []
stack.append(1)     # [1]
stack.append(2)     # [1, 2]
stack.append(3)     # [1, 2, 3]
stack.pop()          # returns 3 -> [1, 2]
stack.pop()          # returns 2 -> [1]

A stack only allows adding and removing from one end — the "top." The last item pushed on is always the first one popped off, which is why it's called LIFO (last in, first out). Python doesn't have a dedicated stack type because a plain list already does the job perfectly: .append() pushes onto the top, .pop() (with no argument, meaning "the last element") pops it back off — both O(1) operations, for exactly the reasons the arrays-and-strings lesson covers about why operating at the end of a list is fast.

The mental model: a stack of plates

You can only take a plate off the top of a stack of plates, and you can only add a new one to the top — you can't grab one from the middle without first removing everything above it. This is the entire definition of a stack, and it's also exactly what makes it useful: it naturally models any "most recently added, handle it first" situation. The call stack (covered in the recursion lesson) is a real stack in exactly this sense — the most recently called function is the first one to finish and return.

Where stacks show up in real problems

def is_balanced(s):
    stack = []
    pairs = {")": "(", "]": "[", "}": "{"}
    for char in s:
        if char in "([{":
            stack.append(char)
        elif char in ")]}":
            if not stack or stack.pop() != pairs[char]:
                return False
    return len(stack) == 0

Checking whether parentheses/brackets are balanced ("(a[b]c)" is balanced, "(a[b)c]" isn't) is the classic stack problem: push every opening bracket, and every closing bracket must match whatever's currently on top of the stack — the most recently opened bracket has to be the next one closed. This "most recent thing must be resolved first" shape is exactly LIFO, which is why a stack — not a list used some other way, not a queue — is the natural fit.

A queue: first in, first out (FIFO)

from collections import deque
 
queue = deque()
queue.append(1)          # add to the back:      [1]
queue.append(2)           #                        [1, 2]
queue.popleft()            # remove from the front: returns 1 -> [2]

A queue allows adding at one end and removing from the other — the first item added is the first one removed, FIFO (first in, first out), exactly like a real line of people: whoever's been waiting longest gets served next. collections.deque (double-ended queue) is Python's standard choice for this — a plain list can technically act as a queue (list.pop(0) removes from the front), but that's O(n), since removing from the front of a list requires shifting every remaining element over, exactly the cost the arrays-and-strings lesson covers. deque is specifically built to make both ends O(1).

Where queues show up: anything processed in arrival order

A real-world queue — a print queue, a task queue, a message queue (covered in its own system-design lesson) — processes items in the order they arrived, which is precisely FIFO behavior. In algorithms specifically, a queue is the structure behind breadth-first search (BFS, covered in an earlier DSA flashcard) — visiting nodes level by level means processing them in the exact order they were first discovered, which is exactly what a queue naturally enforces.

The one-sentence way to tell them apart

A stack answers "what did I add most recently?" A queue answers "what did I add longest ago, that's still waiting?" Same basic idea — a sequence you add to and remove from — with the single difference of which end removal happens from, and that single difference is what makes each one the right (or completely wrong) tool for a given problem.