Stacks & Queues

Two disciplines for "what comes out next"#

Arrays and linked lists let you insert and remove data almost anywhere. Stacks and queues are deliberately more restrictive: each only allows adding and removing data at specific ends, in a specific order. That restriction isn't a weakness — it's exactly what makes them the right fit for an enormous range of real problems, from undo buttons to task schedulers.

Stacks: Last-In, First-Out (LIFO)#

Analogy: a pile of plates. You can only take a plate off the top of the pile, and you can only put a new plate on top too. The very last plate you put down is the very first one you'll pick back up. That's a stack, and that behavior has a name: LIFO — Last In, First Out.

A stack supports exactly two core operations:

• push — add an item to the top.
• pop — remove and return the item from the top.

Usually paired with a peek (look at the top item without removing it) and an is_empty check.

In Python, a plain list already makes a perfectly good stack — append() and pop() (with no argument) both operate on the end of the list, which we simply treat as "the top":

class Stack:
    def __init__(self):
        self._items = []

    def push(self, item):
        self._items.append(item)          # O(1) amortized — add to the "top"

    def pop(self):
        if self.is_empty():
            raise IndexError("pop from an empty stack")
        return self._items.pop()          # O(1) — remove from the "top"

    def peek(self):
        if self.is_empty():
            raise IndexError("peek at an empty stack")
        return self._items[-1]

    def is_empty(self):
        return len(self._items) == 0


s = Stack()
s.push(1)
s.push(2)
s.push(3)
print(s.pop())    # 3 — the last one pushed is the first one popped
print(s.peek())   # 2 — now on top
print(s.pop())    # 2

Every operation here is O(1), because we always work at the end of the underlying list — never the front, where you'd pay the O(n) shifting cost from the arrays page.

Real uses for a stack#

• Undo functionality — every action you take gets pushed onto a stack; hitting "undo" pops the most recent one and reverses it. This is precisely why undo always reverses your most recent action first.
• Browser back button — every page you visit gets pushed onto a "history" stack; clicking back pops the most recently visited page.
• Function call stack — when a function calls another function, the calling function's state is pushed onto the call stack, and it's popped back off when the called function returns. This is literally how recursion works under the hood, and it's why runaway recursion causes a "stack overflow."
• Balanced-symbol checking — matching parentheses, brackets, and braces (see the worked problem below).

Queues: First-In, First-Out (FIFO)#

Analogy: a checkout line at a grocery store. The first person to join the line is the first person served. New people join at the back; people leave from the front. That's a queue, and its behavior is called FIFO — First In, First Out.

A queue supports two core operations:

• enqueue — add an item to the back.
• dequeue — remove and return the item from the front.

Here's a subtlety worth calling out explicitly: a plain Python list is a poor choice for a queue. list.pop(0) (removing from the front) is an O(n) operation, because — as covered on the arrays page — every remaining element has to shift left. If you built a queue on a plain list, every single dequeue would silently cost O(n).

Python solves this with collections.deque ("double-ended queue"), which is implemented internally so that adding or removing from either end is O(1):

from collections import deque

class Queue:
    def __init__(self):
        self._items = deque()

    def enqueue(self, item):
        self._items.append(item)          # O(1) — add to the back

    def dequeue(self):
        if self.is_empty():
            raise IndexError("dequeue from an empty queue")
        return self._items.popleft()      # O(1) — remove from the front

    def peek(self):
        if self.is_empty():
            raise IndexError("peek at an empty queue")
        return self._items[0]

    def is_empty(self):
        return len(self._items) == 0


q = Queue()
q.enqueue("first")
q.enqueue("second")
q.enqueue("third")
print(q.dequeue())   # "first" — the first one enqueued is the first one out
print(q.dequeue())   # "second"

Real uses for a queue#

• Breadth-First Search (BFS) traversal — exploring a tree or graph level by level relies on a queue: visit a node, enqueue all its neighbors, then move to whatever was enqueued earliest. You'll use this directly on the graphs page.
• Task scheduling — a print queue, a job queue processed by background workers, a request queue in a web server — all process work in the order it arrived, which is exactly FIFO behavior.
• Buffering data streams — anywhere data arrives faster than it can be processed (video frames, network packets), a queue holds the backlog in arrival order.

Stack vs Queue at a glance#

Classic problem: valid parentheses#

Given a string containing only the characters ()[]{}, determine whether the brackets are properly balanced — every opening bracket has a matching closing bracket of the same type, in the correct order. For example, "({[]})" is valid; "(]" and "([)]" are not.

This is a textbook stack problem: walk through the string, and every time you see an opening bracket, push it. Every time you see a closing bracket, it must match whatever is currently on top of the stack (the most recently opened, still-unclosed bracket) — if it doesn't match, or the stack is empty when you need a match, the string is invalid.

def is_valid_parentheses(s: str) -> bool:
    stack = []
    pairs = {')': '(', ']': '[', '}': '{'}   # maps a closing bracket to its opener

    for char in s:
        if char in "([{":
            stack.append(char)                       # opening bracket: push it
        elif char in ")]}":
            if not stack or stack.pop() != pairs[char]:
                return False                          # mismatched or nothing to match
        # any other character is ignored in this simplified version

    return len(stack) == 0   # valid only if every opener found its closer


print(is_valid_parentheses("({[]})"))  # True
print(is_valid_parentheses("([)]"))    # False
print(is_valid_parentheses("(("))      # False — unmatched opener left over

Trace it on "([)]" (the tricky "looks balanced but isn't" case):

1. '(' — push. Stack: ['(']
2. '[' — push. Stack: ['(', '[']
3. ')' — closing bracket. Pop the top: '['. But pairs[')'] is '(', and '[' != '(' → mismatch, return False immediately.

This correctly rejects the string, because the ) arrived while the most recently opened bracket was [, not ( — exactly the kind of ordering violation a stack is built to catch. The algorithm runs in O(n) time (one pass over the string) and O(n) space in the worst case (e.g., a string of nothing but opening brackets, all sitting on the stack at once).

Common mistakes#

• Using a plain list as a queue. list.pop(0) is O(n); use collections.deque and popleft() instead, or every dequeue silently costs far more than it should.
• Forgetting to check for an empty stack/queue before popping. Popping from empty is a common source of crashes — always guard with an is_empty() check (as the valid-parentheses solution does with if not stack).
• Mixing up which end is "active." It's easy to accidentally pop from the wrong end when implementing these by hand — always be explicit about which end represents "top" (stack) or "front"/"back" (queue).
• Forgetting that a non-empty stack at the end means an invalid result in problems like valid-parentheses — an opener with no matching closer ("((") never triggers a mismatch mid-loop, so the final len(stack) == 0 check is essential, not optional.