Stacks: The Magic of LIFO

Chapter 5: Stacks — The Magic of LIFO

You stack plates one on top of another, and when you need one, you take it from the top. You hit the browser's "back" button, and it takes you to the last page you visited. You press Ctrl+Z in your editor, and it undoes the last action you performed.

These three scenarios share a common mathematical structure: the stack. The last element placed in is the first one taken out — Last In, First Out, or LIFO.

Stacks appear deceptively simple, but they are one of the most fundamental abstractions in computer science. Your program's ability to call functions, recurse, parse expressions, and undo operations — all of these rely on stacks working behind the scenes. Understanding stacks means understanding one of the core mechanisms of computation itself.

Level 1 · What You Need to Know

1.1 The Basic Concept of a Stack

A stack is a restricted linear data structure. It only allows insertion and deletion at one end, called the top.

A stack supports three core operations:

Additional operations:

• is_empty() — check whether the stack is empty
• size() — return the number of elements in the stack

Why the restriction? An array allows random access to any position. A linked list allows insertion and deletion at any point. A stack deliberately restricts itself to "only operate at the top." This restriction brings semantic clarity and implementation efficiency. When you see a stack, you immediately know: the most recently inserted item will be the first one removed. This constraint makes elegant solutions to many problems possible.

Formal description of the LIFO property:

Given a stack S on which we perform push(a₁), push(a₂), ..., push(aₙ) in sequence, then performing n pop() operations yields the sequence aₙ, aₙ₋₁, ..., a₁. That is: the reverse of the input sequence.

1.2 Implementing a Stack with Python's list

Python's list naturally supports stack operations:

class Stack:
    """Stack implementation based on Python list"""
    
    def __init__(self):
        self._data = []
    
    def push(self, item):
        """Push element onto the top — O(1) amortized"""
        self._data.append(item)
    
    def pop(self):
        """Remove and return the top element — O(1) amortized
        
        Raises:
            IndexError: if the stack is empty
        """
        if self.is_empty():
            raise IndexError("pop from empty stack")
        return self._data.pop()
    
    def peek(self):
        """View the top element without removing it — O(1)
        
        Raises:
            IndexError: if the stack is empty
        """
        if self.is_empty():
            raise IndexError("peek from empty stack")
        return self._data[-1]
    
    def is_empty(self):
        """Check whether the stack is empty — O(1)"""
        return len(self._data) == 0
    
    def size(self):
        """Return the number of elements — O(1)"""
        return len(self._data)
    
    def __repr__(self):
        return f"Stack({self._data})"


# Usage example
s = Stack()
s.push(10)
s.push(20)
s.push(30)
print(s.peek())   # 30
print(s.pop())    # 30
print(s.pop())    # 20
print(s.size())   # 1

Why not just use a bare list? In practice, many people do use list's append and pop directly as a stack. Wrapping it in a class offers:

1. Interface restriction: prevents accidental use of insert, del, or other non-stack operations
2. Semantic clarity: stack.push(x) communicates intent better than items.append(x)
3. Error handling: provides meaningful error messages when operating on an empty stack

But in interviews or competitions, using a bare list is perfectly fine:

# Concise style for interviews/competitions
stack = []
stack.append(42)      # push
top = stack[-1]       # peek
val = stack.pop()     # pop
is_empty = len(stack) == 0

1.3 The Call Stack

Every time your program calls a function, the computer pushes a stack frame onto a structure called the "call stack." When the function returns, its stack frame is popped off.

def multiply(a, b):
    return a * b

def square(x):
    return multiply(x, x)

def print_square(n):
    result = square(n)
    print(result)

print_square(5)

The call stack evolves as print_square(5) executes:

Step 1: print_square(5) is called
    ┌─────────────────┐
    │ print_square     │  ← top
    │   n = 5          │
    └─────────────────┘

Step 2: square(5) is called
    ┌─────────────────┐
    │ square           │  ← top
    │   x = 5          │
    ├─────────────────┤
    │ print_square     │
    │   n = 5          │
    └─────────────────┘

Step 3: multiply(5, 5) is called
    ┌─────────────────┐
    │ multiply         │  ← top
    │   a = 5, b = 5   │
    ├─────────────────┤
    │ square           │
    │   x = 5          │
    ├─────────────────┤
    │ print_square     │
    │   n = 5          │
    └─────────────────┘

Step 4: multiply returns 25, its frame is popped
    ┌─────────────────┐
    │ square           │  ← top
    │   x = 5          │
    │   (receives 25)  │
    ├─────────────────┤
    │ print_square     │
    │   n = 5          │
    └─────────────────┘

Step 5: square returns 25, its frame is popped
    ┌─────────────────┐
    │ print_square     │  ← top
    │   n = 5          │
    │   result = 25    │
    └─────────────────┘

Step 6: print(25), then print_square returns, stack is empty
    (empty stack)

Recursion is simply a function calling itself — each call pushes a new frame onto the call stack:

def factorial(n):
    if n <= 1:
        return 1
    return n * factorial(n - 1)

# At maximum depth, factorial(5) has 5 frames on the call stack:
# factorial(1)  ← top
# factorial(2)
# factorial(3)
# factorial(4)
# factorial(5)  ← bottom

Each level has its own local variable n. This is why recursion can "remember" the state at each level — they live in different stack frames.

1.4 Parentheses Matching

Problem: Given a string containing only (), [], and {}, determine whether it is valid.

Valid parentheses sequences: "()", "()[]{}", "{[()]}", "([{}])"

Invalid parentheses sequences: "(]", "([)]", "{{", ")"

Core idea: When you encounter an opening bracket, push it. When you encounter a closing bracket, pop and check if it matches.

def is_valid_parentheses(s: str) -> bool:
    """
    Check whether a parentheses sequence is valid.
    
    Time complexity: O(n) — each character is pushed and popped at most once
    Space complexity: O(n) — worst case all opening brackets
    """
    stack = []
    # Map each closing bracket to its corresponding opening bracket
    matching = {')': '(', ']': '[', '}': '{'}
    
    for char in s:
        if char in '([{':
            # Opening bracket: push onto stack
            stack.append(char)
        elif char in ')]}':
            # Closing bracket: check if top of stack matches
            if not stack:
                return False  # Stack empty, no matching opening bracket
            if stack.pop() != matching[char]:
                return False  # Top of stack doesn't match
    
    # After traversal, stack should be empty (all brackets matched)
    return len(stack) == 0


# Tests
assert is_valid_parentheses("()") == True
assert is_valid_parentheses("()[]{}") == True
assert is_valid_parentheses("{[()]}") == True
assert is_valid_parentheses("(]") == False
assert is_valid_parentheses("([)]") == False
assert is_valid_parentheses("{") == False

Why is a stack the perfect data structure here? Because the core rule of bracket matching is: the last bracket opened must be the first one closed. This is precisely LIFO.

1.5 Expression Evaluation

1.5.1 Infix, Prefix, and Postfix Expressions

The mathematical expressions we write daily are infix expressions (operator between operands):

3 + 4 * 2

Evaluating this expression requires knowledge of operator precedence (multiplication before addition) and associativity. This is intuitive for humans but cumbersome for machines.

Postfix expressions (also called Reverse Polish Notation, RPN) place operators after their operands:

3 4 2 * +

Advantages of postfix expressions:

1. No parentheses needed
2. No precedence rules needed
3. Can be evaluated with a single left-to-right scan

1.5.2 Evaluating Postfix Expressions

The algorithm is elegantly simple:

1. Scan from left to right
2. When you encounter a number, push it onto the stack
3. When you encounter an operator, pop two operands, compute the result, push it back
4. The final element remaining on the stack is the result

def eval_rpn(tokens: list[str]) -> int:
    """
    Evaluate a Reverse Polish Notation expression.
    
    tokens: each element is a number string or operator "+", "-", "*", "/"
    
    Time complexity: O(n)
    Space complexity: O(n)
    """
    stack = []
    operators = {'+', '-', '*', '/'}
    
    for token in tokens:
        if token in operators:
            # Note: the first popped value is the right operand
            b = stack.pop()
            a = stack.pop()
            if token == '+':
                stack.append(a + b)
            elif token == '-':
                stack.append(a - b)
            elif token == '*':
                stack.append(a * b)
            elif token == '/':
                # Note: truncation toward zero
                stack.append(int(a / b))
        else:
            stack.append(int(token))
    
    return stack[0]


# Example: "3 + 4 * 2" in postfix
print(eval_rpn(["3", "4", "2", "*", "+"]))  # 11

# Example: "(1 + 2) * (3 + 4)" in postfix
print(eval_rpn(["1", "2", "+", "3", "4", "+", "*"]))  # 21

1.5.3 Infix to Postfix: The Shunting-yard Algorithm

This algorithm was invented by Edsger Dijkstra in 1961. Its name comes from the railroad shunting yard — train cars are rearranged onto different tracks, just as tokens are rearranged between the output queue and the operator stack.

Algorithm rules:

1. Number: output directly
2. Left parenthesis (: push onto operator stack
3. Right parenthesis ): pop operators from stack and output until left parenthesis is found (discard the left parenthesis)
4. Operator op:
   • While the top of the operator stack has precedence ≥ op's precedence, pop and output
   • Then push op onto the stack
5. End of input: pop all remaining operators and output them

def infix_to_postfix(expression: str) -> list[str]:
    """
    Convert infix expression to postfix (Shunting-yard algorithm).
    
    Supports +, -, *, / and parentheses.
    Assumes valid input with tokens separated by spaces.
    """
    precedence = {'+': 1, '-': 1, '*': 2, '/': 2}
    output = []
    op_stack = []
    
    tokens = expression.split()
    
    for token in tokens:
        if token.lstrip('-').isdigit():
            # Number (including negatives)
            output.append(token)
        elif token == '(':
            op_stack.append(token)
        elif token == ')':
            # Pop until left parenthesis
            while op_stack and op_stack[-1] != '(':
                output.append(op_stack.pop())
            op_stack.pop()  # Discard the left parenthesis
        elif token in precedence:
            # Operator: pop all operators with higher or equal precedence
            while (op_stack and 
                   op_stack[-1] != '(' and 
                   op_stack[-1] in precedence and
                   precedence[op_stack[-1]] >= precedence[token]):
                output.append(op_stack.pop())
            op_stack.append(token)
    
    # Pop all remaining operators
    while op_stack:
        output.append(op_stack.pop())
    
    return output


# Tests
print(infix_to_postfix("3 + 4 * 2"))
# ['3', '4', '2', '*', '+']

print(infix_to_postfix("( 1 + 2 ) * ( 3 + 4 )"))
# ['1', '2', '+', '3', '4', '+', '*']

print(infix_to_postfix("3 + 4 * 2 / ( 1 - 5 )"))
# ['3', '4', '2', '*', '1', '5', '-', '/', '+']

The complete evaluation pipeline: Infix → Shunting-yard → Postfix → Postfix evaluation → Result

def evaluate_expression(expression: str) -> float:
    """Complete expression evaluation: infix → postfix → result"""
    postfix = infix_to_postfix(expression)
    return eval_rpn(postfix)

print(evaluate_expression("3 + 4 * 2"))           # 11
print(evaluate_expression("( 1 + 2 ) * ( 3 + 4 )"))  # 21

1.6 The Min Stack

Problem: Design a stack that, in addition to push, pop, and peek, supports a get_min() operation that returns the minimum element in the stack. All operations must run in O(1) time.

Key insight: If we only keep a single variable tracking the current minimum, once that minimum is popped, we lose track of the new minimum. The solution: use an auxiliary stack that synchronously records the minimum at each state.

class MinStack:
    """
    Stack supporting O(1) minimum retrieval.
    
    Approach: maintain an auxiliary stack min_stack whose top always holds
    the current minimum of the main stack.
    On each push, record the new minimum in min_stack.
    On each pop, also pop min_stack.
    """
    
    def __init__(self):
        self._stack = []
        self._min_stack = []  # min_stack[i] = min(stack[0..i])
    
    def push(self, val: int) -> None:
        self._stack.append(val)
        # If min_stack is empty or new value <= current min, push new min
        if not self._min_stack or val <= self._min_stack[-1]:
            self._min_stack.append(val)
        else:
            # Otherwise repeat the current min (keep stacks in sync)
            self._min_stack.append(self._min_stack[-1])
    
    def pop(self) -> int:
        self._min_stack.pop()
        return self._stack.pop()
    
    def peek(self) -> int:
        return self._stack[-1]
    
    def get_min(self) -> int:
        """O(1) retrieval of the current minimum"""
        return self._min_stack[-1]


# Usage example
ms = MinStack()
ms.push(5)
ms.push(3)
ms.push(7)
ms.push(1)
print(ms.get_min())  # 1
ms.pop()             # pops 1
print(ms.get_min())  # 3
ms.pop()             # pops 7
print(ms.get_min())  # 3
ms.pop()             # pops 3
print(ms.get_min())  # 5

Space optimization: In the implementation above, min_stack is the same length as the main stack. You can push to min_stack only when the minimum changes, but the pop logic becomes more complex. For interviews, the above approach is clearest.

Level 2 · Deeper Understanding

2.1 The Internal Structure of a Stack Frame

In Level 1 we saw the macroscopic behavior of the call stack. Now let's zoom into a single stack frame.

When a function is called, the CPU allocates a block of memory on the call stack — the stack frame. A typical stack frame contains:

High Address
┌──────────────────────────┐
│  Arguments from caller    │  (pushed by caller)
├──────────────────────────┤
│  Return address           │  (pushed by call instruction)
├──────────────────────────┤  ← Frame Pointer (FP/RBP)
│  Saved previous FP        │
├──────────────────────────┤
│  Local variable 1         │
│  Local variable 2         │
│  ...                      │
├──────────────────────────┤
│  Temporary computation    │
├──────────────────────────┤  ← Stack Pointer (SP/RSP)
Low Address

The role of each component:

1. Arguments: Data passed from the caller. On x86-64, the first 6 integer arguments are passed via registers (rdi, rsi, rdx, rcx, r8, r9); additional arguments go through the stack.

2. Return address: The instruction the CPU should jump back to after the function completes. This is automatically pushed by the call instruction.

3. Saved frame pointer: Used to restore the base address of the previous frame, forming a linked list of frames.

4. Local variables: Variables defined within the function are stored here.

5. Temporary space: Intermediate results of expression evaluation.

The Python equivalent:

Although Python uses a virtual machine rather than directly manipulating the hardware stack, the concept is the same. Each Python stack frame (PyFrameObject) contains:

import sys

def show_frame_info():
    frame = sys._getframe()  # Get the current stack frame
    print(f"Function: {frame.f_code.co_name}")
    print(f"Locals: {frame.f_locals}")
    print(f"Line number: {frame.f_lineno}")
    print(f"Caller: {frame.f_back.f_code.co_name}")

def caller():
    x = 42
    show_frame_info()

caller()
# Output:
# Function: show_frame_info
# Locals: {'frame': <frame at 0x...>}
# Line number: 5
# Caller: caller

2.2 Stack Overflow

The operating system allocates a fixed-size stack space for each thread (typically 1-8 MB). When recursion goes too deep or local variables are too large, the stack space is exhausted — this is a stack overflow.

# This causes RecursionError (Python's stack overflow protection)
def infinite_recursion():
    return infinite_recursion()

# Python's default recursion depth limit is 1000
import sys
print(sys.getrecursionlimit())  # 1000

# Even non-infinite recursion can overflow if too deep
def deep_recursion(n):
    if n == 0:
        return 0
    return deep_recursion(n - 1) + 1

# deep_recursion(10000)  # RecursionError!

Common causes of stack overflow:

1. Infinite recursion: forgetting the base case, or having a base case that's never reached
2. Excessive recursion depth: input data is large, recursion reaches thousands or tens of thousands of levels
3. Oversized local variables: allocating huge arrays on the stack (more common in C/C++)

Prevention strategies:

# Strategy 1: Increase recursion limit (treats symptoms, not cause)
sys.setrecursionlimit(100000)

# Strategy 2: Convert to iteration (use explicit stack, see Section 2.5)

# Strategy 3: Tail call optimization (Python doesn't support it, but
# languages like Scheme do)
# Tail recursion: the recursive call is the last operation in the function
def factorial_tail(n, acc=1):
    if n <= 1:
        return acc
    return factorial_tail(n - 1, n * acc)  # tail call

2.3 Implementing DFS with a Stack

The recursive version of depth-first search (DFS) inherently uses the call stack. We can implement a completely equivalent non-recursive version using an explicit stack.

Graph DFS — Recursive:

def dfs_recursive(graph: dict, start: str, visited: set = None) -> list:
    """
    Graph DFS (recursive version)
    graph: adjacency list {node: [neighbors]}
    """
    if visited is None:
        visited = set()
    
    visited.add(start)
    result = [start]
    
    for neighbor in graph[start]:
        if neighbor not in visited:
            result.extend(dfs_recursive(graph, neighbor, visited))
    
    return result

Graph DFS — Explicit Stack:

def dfs_iterative(graph: dict, start: str) -> list:
    """
    Graph DFS (explicit stack version)
    
    Note: traversal order may differ slightly from recursive version
    (depends on push order of neighbors), but both are valid DFS.
    """
    visited = set()
    stack = [start]
    result = []
    
    while stack:
        node = stack.pop()
        if node in visited:
            continue
        
        visited.add(node)
        result.append(node)
        
        # Push neighbors in reverse order so that the first neighbor
        # is processed first (matching recursive version's order)
        for neighbor in reversed(graph[node]):
            if neighbor not in visited:
                stack.append(neighbor)
    
    return result


# Test
graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': ['F'],
    'F': []
}

print(dfs_recursive(graph, 'A'))  # ['A', 'B', 'D', 'E', 'F', 'C']
print(dfs_iterative(graph, 'A'))  # ['A', 'B', 'D', 'E', 'F', 'C']

Binary tree preorder traversal — Explicit Stack:

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def preorder_iterative(root: TreeNode) -> list[int]:
    """Preorder traversal: root → left → right"""
    if not root:
        return []
    
    result = []
    stack = [root]
    
    while stack:
        node = stack.pop()
        result.append(node.val)
        # Push right first, then left
        # Since stack is LIFO, left will be processed first
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)
    
    return result

2.4 Implementing a Queue with Two Stacks

Problem: Implement a queue using two stacks, supporting enqueue and dequeue operations.

Core idea: A stack is LIFO, a queue is FIFO. If we pour all elements from one stack into another, the order is reversed. Two reversals = original order = FIFO.

class QueueWithTwoStacks:
    """
    Queue implemented with two stacks.
    
    in_stack: handles enqueue (all enqueue operations push here)
    out_stack: handles dequeue (dequeue pops from here)
    
    When out_stack is empty and dequeue is needed,
    pour all elements from in_stack into out_stack.
    
    Amortized analysis: each element is pushed/popped at most twice
    (into in_stack once, out of in_stack once, into out_stack once,
    out of out_stack once), so each operation has O(1) amortized cost.
    """
    
    def __init__(self):
        self._in_stack = []   # enqueue stack
        self._out_stack = []  # dequeue stack
    
    def enqueue(self, item) -> None:
        """Enqueue — O(1)"""
        self._in_stack.append(item)
    
    def dequeue(self):
        """Dequeue — amortized O(1)"""
        if not self._out_stack:
            # out_stack empty: pour in_stack into it
            if not self._in_stack:
                raise IndexError("dequeue from empty queue")
            while self._in_stack:
                self._out_stack.append(self._in_stack.pop())
        return self._out_stack.pop()
    
    def peek(self):
        """View front element — amortized O(1)"""
        if not self._out_stack:
            if not self._in_stack:
                raise IndexError("peek from empty queue")
            while self._in_stack:
                self._out_stack.append(self._in_stack.pop())
        return self._out_stack[-1]
    
    def is_empty(self) -> bool:
        return not self._in_stack and not self._out_stack
    
    def size(self) -> int:
        return len(self._in_stack) + len(self._out_stack)


# Test
q = QueueWithTwoStacks()
q.enqueue(1)
q.enqueue(2)
q.enqueue(3)
print(q.dequeue())  # 1 (FIFO!)
q.enqueue(4)
print(q.dequeue())  # 2
print(q.dequeue())  # 3
print(q.dequeue())  # 4

Formal proof using the Potential Method:

Define potential function Phi = number of elements in in_stack.

• enqueue: actual cost = 1 (push to in_stack), Phi increases by 1. Amortized cost = 1 + 1 = 2.
• dequeue (out_stack non-empty): actual cost = 1 (pop from out_stack), Phi unchanged. Amortized cost = 1.
• dequeue (out_stack empty, in_stack has k elements): actual cost = k (pour) + 1 (pop), Phi decreases by k. Amortized cost = (k + 1) - k = 1.

Therefore, each operation has O(1) amortized cost.

2.5 Recursion Elimination: The General Method

Any recursion can be rewritten as iteration + explicit stack. The general approach:

Idea: Simulate the call stack. Each "stack frame" of the recursive function becomes an element on our explicit stack. A frame must record: current arguments, which step we're at (simulating the "return address"), and intermediate results.

Example: Recursive merge sort → iterative

First, the recursive version:

def merge_sort_recursive(arr: list) -> list:
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort_recursive(arr[:mid])
    right = merge_sort_recursive(arr[mid:])
    return merge(left, right)

def merge(left: list, right: list) -> list:
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result

General recursion elimination template:

def recursive_to_iterative_template():
    """
    General template for converting recursion to iteration.
    
    Core idea:
    1. Use an explicit stack to simulate the call stack
    2. Each frame records: arguments + state (which step) + partial results
    3. Use a state machine to simulate different "phases" of execution
    """
    # Define a frame: (args, state, partial_results)
    
    stack = [(initial_args, 'ENTER', {})]
    return_value = None
    
    while stack:
        args, state, partial = stack[-1]
        
        if state == 'ENTER':
            # Corresponds to function entry
            if base_case(args):
                return_value = base_result(args)
                stack.pop()
            else:
                # Prepare first recursive call
                stack[-1] = (args, 'AFTER_FIRST_CALL', partial)
                stack.append((sub_args_1, 'ENTER', {}))
        
        elif state == 'AFTER_FIRST_CALL':
            # First recursive call has returned
            partial['first_result'] = return_value
            # Prepare second recursive call
            stack[-1] = (args, 'AFTER_SECOND_CALL', partial)
            stack.append((sub_args_2, 'ENTER', {}))
        
        elif state == 'AFTER_SECOND_CALL':
            # Second recursive call has also returned
            partial['second_result'] = return_value
            # Combine results
            return_value = combine(partial['first_result'], 
                                   partial['second_result'])
            stack.pop()
    
    return return_value

Concrete example: Iterative inorder traversal of a binary tree

def inorder_iterative(root: TreeNode) -> list[int]:
    """
    Inorder traversal: left → root → right
    
    Approach: keep going left and pushing onto stack.
    When you can't go further left, pop and process, then go right.
    """
    result = []
    stack = []
    current = root
    
    while current or stack:
        # Go all the way left, pushing each node
        while current:
            stack.append(current)
            current = current.left
        
        # Pop the leftmost unprocessed node
        current = stack.pop()
        result.append(current.val)
        
        # Move to right subtree
        current = current.right
    
    return result

When should you use an explicit stack instead of recursion?

1. Recursion depth might be large (> 1000): Python's default limit is 1000 levels
2. Performance-sensitive code: function calls have overhead (creating frames, saving registers)
3. Need finer control: e.g., need to pause/resume traversal

Level 3 · Want to Know More

3.1 The History of the Stack

The concept of a stack did not exist from the beginning of computing. Its invention passed through several key milestones:

1946 — Alan Turing's Subroutine Concept

Alan Turing, in his design report for the ACE (Automatic Computing Engine), described the concept of "subroutines" — reusable blocks of code that could be called repeatedly. However, he did not yet have an explicit stack concept; at that time, subroutines achieved "return" by modifying addresses within instructions, and recursion was not supported.

1955 — Friedrich Bauer and Klaus Samelson

At the Technical University of Munich, Friedrich Bauer and Klaus Samelson independently invented the stack data structure (they called it "Keller" — German for "cellar," vividly comparing it to a cellar where you store and retrieve items from the top). They used the stack for translating arithmetic expressions, which was the origin of stacks in compilers.

1957 — The Stack Patent

Bauer and Samelson filed a patent for "a method for the automatic processing of coded data using a processing machine with progressively composed expressions into sub-expressions" (German patent DE1094019). This is possibly one of the earliest software-related patents in computer science.

1958 — Hardware Stacks

Charles Hamblin in Australia proposed the idea of making the stack a direct part of the processor architecture — the stack machine. Later, the Burroughs B5000 (1961) became the first commercial computer built on a stack architecture.

1960 — The Recursion Debate

The ALGOL 60 language committee had a heated debate about whether to support recursion. Supporting recursion necessarily required a runtime stack (call stack). Dijkstra strongly advocated for recursion, and ultimately this feature was included in the ALGOL 60 standard. From that point on, the call stack became standard in virtually all programming languages.

3.2 Dijkstra's Shunting-yard Algorithm

Edsger W. Dijkstra published the Shunting-yard Algorithm in 1961, designed to convert infix expressions to postfix expressions (or evaluate them directly). The algorithm is important because it elegantly solves the problem of operator precedence and associativity.

Origin of the name:

A railroad shunting yard is a facility used to rearrange the order of train cars. Cars enter from one track, are temporarily stored on sidings, and exit on another track in a different order. In the algorithm:

• Input track = the token stream of the infix expression
• Siding = the operator stack
• Output track = the postfix expression

Handling operator associativity:

Left-associative operators (like +, -, *, /): pop when stack top precedence ≥ current operator. Right-associative operators (like exponentiation ^): pop only when stack top precedence > current operator.

def shunting_yard_full(expression: str) -> list[str]:
    """
    Full shunting-yard algorithm with right-associative and unary operators.
    """
    precedence = {'+': 2, '-': 2, '*': 3, '/': 3, '^': 4}
    right_associative = {'^'}
    
    output = []
    op_stack = []
    tokens = tokenize(expression)  # Assumes a tokenizer exists
    
    for token in tokens:
        if is_number(token):
            output.append(token)
        elif is_function(token):
            op_stack.append(token)
        elif token == '(':
            op_stack.append(token)
        elif token == ')':
            while op_stack[-1] != '(':
                output.append(op_stack.pop())
            op_stack.pop()  # Discard '('
            # If top is a function, pop it too
            if op_stack and is_function(op_stack[-1]):
                output.append(op_stack.pop())
        elif token in precedence:
            while (op_stack and 
                   op_stack[-1] != '(' and
                   op_stack[-1] in precedence and
                   (precedence[op_stack[-1]] > precedence[token] or
                    (precedence[op_stack[-1]] == precedence[token] and
                     token not in right_associative))):
                output.append(op_stack.pop())
            op_stack.append(token)
    
    while op_stack:
        output.append(op_stack.pop())
    
    return output

Why did Dijkstra invent this algorithm? In the early 1960s, compilers needed to convert human-written expressions into machine instructions. Infix expressions are hard for machines to process (they require handling precedence and parentheses), while postfix expressions can be executed by a simple stack machine. The shunting-yard algorithm is the key step in this transformation.

3.3 The Role of Stacks in Compilers

Stacks play important roles in multiple phases of compilers and interpreters:

1. Lexical Analysis

Some lexical analyzers use stacks to handle nested comments or string interpolation:

# Parsing nested Python f-strings requires a stack
# f"{'nested' + f'{42}'}"  — braces can nest

2. Parsing (Syntax Analysis)

Shift-Reduce Parsing is a bottom-up syntax analysis method whose core data structure is a stack:

Input: id + id * id
Grammar: E → E + E | E * E | id

Parsing process (simplified):
Stack            | Input          | Action
                 | id + id * id   | Shift
id               | + id * id      | Reduce (id → E)
E                | + id * id      | Shift
E +              | id * id        | Shift
E + id           | * id           | Reduce (id → E)
E + E            | * id           | Shift (* has higher precedence)
E + E *          | id             | Shift
E + E * id       |                | Reduce (id → E)
E + E * E        |                | Reduce (E * E → E)
E + E            |                | Reduce (E + E → E)
E                |                | Accept

3. Runtime Virtual Machines

Python's bytecode interpreter (CPython VM) is a stack-based virtual machine:

import dis

def add(a, b):
    return a + b

dis.dis(add)
# Output:
#   0 LOAD_FAST    0 (a)       ← push a onto operand stack
#   2 LOAD_FAST    1 (b)       ← push b onto operand stack
#   4 BINARY_ADD                ← pop two operands, push result
#   6 RETURN_VALUE              ← pop result and return

Java's JVM is also a stack-based VM. In contrast, Lua's VM and Android's Dalvik VM are register-based.

3.4 Forth: A Language Built Entirely on Stacks

Forth is a programming language invented by Charles Moore in 1970. Its unique characteristic: the programmer directly manipulates the stack. No variable declarations, no expression syntax — everything is done through stack operations.

\ Forth: calculate (3 + 4) * 5
3 4 + 5 *       \ result: 35

\ Define a "word" (function) that squares a number
: square  ( n -- n^2 )  dup * ;

\ Use it
7 square .       \ prints 49

\ Define factorial
: factorial  ( n -- n! )
    1 swap          \ stack: 1 n
    1+ 1 do         \ loop i from 1 to n
        i *         \ multiply accumulator
    loop
;

5 factorial .    \ prints 120

Forth's design philosophy:

1. Minimalist: the entire language core can be implemented in a few KB
2. Extensible: defining a new word is extending the language
3. Direct: the programmer explicitly controls data flow on the stack

Forth is still used in embedded systems today (e.g., Open Firmware, Sun/Apple boot firmware). PostScript (precursor to PDF) and Bitcoin Script are also stack-based languages.

A simplified Forth interpreter in Python:

class ForthInterpreter:
    """Simplified Forth interpreter"""
    
    def __init__(self):
        self.stack = []
        self.dictionary = {}  # User-defined words
        
        # Built-in operations
        self.builtins = {
            '+': lambda: self._binary_op(lambda a, b: a + b),
            '-': lambda: self._binary_op(lambda a, b: a - b),
            '*': lambda: self._binary_op(lambda a, b: a * b),
            '/': lambda: self._binary_op(lambda a, b: a // b),
            'dup': lambda: self.stack.append(self.stack[-1]),
            'drop': lambda: self.stack.pop(),
            'swap': lambda: self._swap(),
            'over': lambda: self.stack.append(self.stack[-2]),
            '.': lambda: print(self.stack.pop()),
            '.s': lambda: print(self.stack),
        }
    
    def _binary_op(self, op):
        b = self.stack.pop()
        a = self.stack.pop()
        self.stack.append(op(a, b))
    
    def _swap(self):
        self.stack[-1], self.stack[-2] = self.stack[-2], self.stack[-1]
    
    def execute(self, code: str):
        tokens = code.split()
        i = 0
        while i < len(tokens):
            token = tokens[i]
            
            if token == ':':
                # Define a new word
                name = tokens[i + 1]
                body = []
                i += 2
                while tokens[i] != ';':
                    body.append(tokens[i])
                    i += 1
                self.dictionary[name] = body
            elif token in self.builtins:
                self.builtins[token]()
            elif token in self.dictionary:
                # Execute user-defined word (recursive)
                self.execute(' '.join(self.dictionary[token]))
            else:
                # Try to push as a number
                self.stack.append(int(token))
            i += 1


# Usage
forth = ForthInterpreter()
forth.execute(": square dup * ;")
forth.execute("7 square .")       # 49
forth.execute("3 4 + 5 * .")      # 35

Level 4 · Practice and Interviews

4.1 Performance Characteristics of Python list as a Stack

Python's list is backed by a dynamic array. append and pop (end operations) have O(1) amortized time complexity.

Why "amortized" rather than strict O(1)?

When the dynamic array is full and needs to grow, Python allocates a larger array (roughly 1.125x the original size) and copies all elements over. This single operation is O(n), but since resizing happens with decreasing frequency, the cost amortized over all appends is still O(1).

import sys

# Observe list's memory allocation strategy
lst = []
prev_size = 0
for i in range(100):
    new_size = sys.getsizeof(lst)
    if new_size != prev_size:
        print(f"len={i:3d}, size={new_size:5d} bytes, "
              f"capacity≈{(new_size - 56) // 8}")  # 64-bit system
        prev_size = new_size
    lst.append(i)

# Output (approximate):
# len=  0, size=   56 bytes, capacity≈0
# len=  1, size=   88 bytes, capacity≈4
# len=  5, size=  120 bytes, capacity≈8
# len=  9, size=  184 bytes, capacity≈16
# len= 17, size=  248 bytes, capacity≈24
# ...

Comparison with collections.deque:

deque can also be used as a stack (via append/pop), also O(1). The differences:

• list: contiguous memory, cache-friendly, but front insertion/deletion is O(n)
• deque: implemented as a block-linked list, O(1) operations at both ends

For pure stack operations (only operating at the end), list is typically faster due to more compact memory layout.

import timeit

# Performance comparison
setup = "from collections import deque"

# list as stack
t_list = timeit.timeit(
    "s = []\nfor i in range(10000): s.append(i)\nfor i in range(10000): s.pop()",
    number=1000
)

# deque as stack
t_deque = timeit.timeit(
    "s = deque()\nfor i in range(10000): s.append(i)\nfor i in range(10000): s.pop()",
    setup=setup,
    number=1000
)

print(f"list:  {t_list:.3f}s")
print(f"deque: {t_deque:.3f}s")
# Typically list is slightly faster or on par

4.2 High-Frequency Interview Problems

4.2.1 Valid Parentheses (LeetCode #20)

This is the bracket matching problem from Level 1. Interview pitfalls to watch for:

def isValid(s: str) -> bool:
    stack = []
    mapping = {')': '(', ']': '[', '}': '{'}
    
    for char in s:
        if char in mapping:
            # Pitfall 1: popping from empty stack raises an error
            top = stack.pop() if stack else '#'
            if top != mapping[char]:
                return False
        else:
            stack.append(char)
    
    # Pitfall 2: don't forget to check if stack is empty
    return not stack

Interview follow-ups:

• "What if the input contains non-bracket characters?" → Just ignore them
• "What if there's only one type of bracket?" → A counter suffices, no stack needed
• "What if you need to find the first mismatched position?" → Store indices in the stack

4.2.2 Daily Temperatures (LeetCode #739) — Monotonic Stack

Problem: Given a daily temperature array, return how many days you need to wait for a warmer temperature for each day.

Input:  [73, 74, 75, 71, 69, 72, 76, 73]
Output: [1,  1,  4,  2,  1,  1,  0,  0]

The brute-force solution is O(n^2). Using a monotonic stack achieves O(n).

def daily_temperatures(temperatures: list[int]) -> list[int]:
    """
    Monotonic stack solution.
    
    Maintain a monotonically decreasing stack (storing indices).
    For each new temperature, if it's higher than the temperature
    corresponding to the stack top, then that day has found its answer.
    
    Time complexity: O(n) — each element is pushed and popped at most once
    Space complexity: O(n)
    """
    n = len(temperatures)
    result = [0] * n
    stack = []  # Stores indices; corresponding temperatures are decreasing
    
    for i in range(n):
        # Current temperature is higher than stack top: stack top found answer
        while stack and temperatures[i] > temperatures[stack[-1]]:
            prev_idx = stack.pop()
            result[prev_idx] = i - prev_idx
        stack.append(i)
    
    # Elements remaining in stack have no warmer day after them; result stays 0
    return result


# Test
temps = [73, 74, 75, 71, 69, 72, 76, 73]
print(daily_temperatures(temps))
# [1, 1, 4, 2, 1, 1, 0, 0]

The essence of the monotonic stack: For each element in an array, find the first element to its right (or left) that is greater (or smaller). This is a general solution for a class of problems, which we will explore in depth in Chapter 6.

4.2.3 Evaluate Reverse Polish Notation (LeetCode #150)

This is the eval_rpn from Level 1. Key interview considerations:

def evalRPN(tokens: list[str]) -> int:
    stack = []
    
    for token in tokens:
        if token in {'+', '-', '*', '/'}:
            b, a = stack.pop(), stack.pop()  # Note the order!
            if token == '+': stack.append(a + b)
            elif token == '-': stack.append(a - b)
            elif token == '*': stack.append(a * b)
            elif token == '/':
                # Pitfall: Python's // rounds toward negative infinity,
                # but the problem requires truncation toward zero
                # -7 // 2 = -4 (Python), but problem wants -3
                stack.append(int(a / b))  # int() truncates toward zero
        else:
            stack.append(int(token))
    
    return stack[0]

Key pitfalls:

1. Order of a and b: the first popped value is b (right operand)
2. Division truncation direction: Python's // rounds toward negative infinity, but the problem requires truncation toward zero

4.2.4 Basic Calculator (LeetCode #224)

Problem: Implement a basic calculator supporting +, -, (, ), and spaces.

Input: "(1+(4+5+2)-3)+(6+8)"
Output: 23

This is simpler than the shunting-yard algorithm since only addition and subtraction exist (same precedence), but nested parentheses need handling:

def calculate(s: str) -> int:
    """
    Basic calculator: supports +, -, parentheses.
    
    Core idea: use a stack to save the state outside parentheses
    (current result and sign).
    On '(', push current result and sign, restart calculation.
    On ')', combine the result inside parentheses with saved state.
    
    Time complexity: O(n)
    Space complexity: O(n)
    """
    stack = []
    result = 0       # Current accumulated result
    sign = 1         # Current sign: +1 or -1
    num = 0          # Number currently being built
    
    for char in s:
        if char.isdigit():
            num = num * 10 + int(char)
        elif char == '+':
            result += sign * num
            num = 0
            sign = 1
        elif char == '-':
            result += sign * num
            num = 0
            sign = -1
        elif char == '(':
            # Save current state, restart
            stack.append(result)
            stack.append(sign)
            result = 0
            sign = 1
        elif char == ')':
            # Add current number to result
            result += sign * num
            num = 0
            # Restore from stack: pop sign first, then previous result
            result = stack.pop() * result + stack.pop()
    
    # Don't forget the last number
    result += sign * num
    return result


# Tests
print(calculate("1 + 1"))                 # 2
print(calculate("2 - 1 + 2"))             # 3
print(calculate("(1+(4+5+2)-3)+(6+8)"))   # 23
print(calculate("-(2 + 3)"))              # -5

4.3 Stack vs Recursion: When to Use an Explicit Stack

Practical case: File system traversal

import os

# Recursive version (may overflow on deeply nested directories)
def find_files_recursive(directory, extension):
    results = []
    for entry in os.listdir(directory):
        path = os.path.join(directory, entry)
        if os.path.isfile(path) and path.endswith(extension):
            results.append(path)
        elif os.path.isdir(path):
            results.extend(find_files_recursive(path, extension))
    return results

# Explicit stack version (safe, no depth limit)
def find_files_iterative(directory, extension):
    results = []
    stack = [directory]
    
    while stack:
        current_dir = stack.pop()
        try:
            for entry in os.listdir(current_dir):
                path = os.path.join(current_dir, entry)
                if os.path.isfile(path) and path.endswith(extension):
                    results.append(path)
                elif os.path.isdir(path):
                    stack.append(path)
        except PermissionError:
            continue  # Skip directories without permission
    
    return results

4.4 Common Pitfalls and Best Practices

Pitfall 1: Popping from an empty stack

# Wrong: popping without checking
def bad_code(stack):
    return stack.pop()  # If stack is empty → IndexError

# Correct: check first
def good_code(stack):
    if not stack:
        return None  # Or raise a custom exception
    return stack.pop()

Pitfall 2: Peeking without checking

# Wrong
top = stack[-1]  # If stack is empty → IndexError

# Correct
top = stack[-1] if stack else None

Pitfall 3: Operand order

# In postfix expression evaluation:
b = stack.pop()  # Right operand
a = stack.pop()  # Left operand
result = a - b   # NOT b - a!

# Mnemonic: the first pushed is the left operand (appeared earlier)

Pitfall 4: Using the front of a list as the stack top

# Wrong (performance disaster): using list's front as stack top
stack.insert(0, item)  # O(n)!
stack.pop(0)           # O(n)!

# Correct: always use the end of list as stack top
stack.append(item)     # O(1) amortized
stack.pop()            # O(1) amortized

Pitfall 5: Recursion + global state

# Pitfall: modifying global/shared state in recursion
visited = set()  # Global

def dfs(node):
    visited.add(node)
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs(neighbor)

# If you call dfs multiple times, visited doesn't automatically reset!
# Fix: pass as parameter, or reset before each call

4.5 Comprehensive Exercise: A Complete Expression Calculator

Integrating everything from this chapter, let's implement a calculator supporting +, -, *, /, parentheses, and unary negation:

class Calculator:
    """
    Complete mathematical expression calculator.
    
    Supports:
    - Arithmetic: +, -, *, /
    - Parentheses: ()
    - Unary negation: -3, -(2+1)
    - Multi-digit numbers and decimals: 123, 3.14
    
    Implementation: Shunting-yard (infix → postfix) + postfix evaluation
    """
    
    def __init__(self):
        self.precedence = {'+': 1, '-': 1, '*': 2, '/': 2, 'NEG': 3}
        self.right_assoc = {'NEG'}
    
    def tokenize(self, expression: str) -> list:
        """Lexical analysis: break string into token list"""
        tokens = []
        i = 0
        prev_token = None
        
        while i < len(expression):
            if expression[i].isspace():
                i += 1
                continue
            
            if expression[i].isdigit() or expression[i] == '.':
                # Read a number (including decimals)
                j = i
                while j < len(expression) and (expression[j].isdigit() or expression[j] == '.'):
                    j += 1
                tokens.append(('NUM', float(expression[i:j])))
                prev_token = 'NUM'
                i = j
            elif expression[i] == '-' and (prev_token is None or prev_token in ('(', 'OP')):
                # Unary negation
                tokens.append(('OP', 'NEG'))
                prev_token = 'OP'
                i += 1
            elif expression[i] in '+-*/':
                tokens.append(('OP', expression[i]))
                prev_token = 'OP'
                i += 1
            elif expression[i] == '(':
                tokens.append(('LPAREN', '('))
                prev_token = '('
                i += 1
            elif expression[i] == ')':
                tokens.append(('RPAREN', ')'))
                prev_token = 'NUM'  # '-' after ')' is binary
                i += 1
            else:
                raise ValueError(f"Unexpected character: {expression[i]}")
        
        return tokens
    
    def to_postfix(self, tokens: list) -> list:
        """Shunting-yard algorithm: token list → postfix expression"""
        output = []
        op_stack = []
        
        for token_type, token_value in tokens:
            if token_type == 'NUM':
                output.append(token_value)
            elif token_type == 'LPAREN':
                op_stack.append('(')
            elif token_type == 'RPAREN':
                while op_stack[-1] != '(':
                    output.append(op_stack.pop())
                op_stack.pop()
            elif token_type == 'OP':
                while (op_stack and op_stack[-1] != '(' and
                       op_stack[-1] in self.precedence and
                       (self.precedence[op_stack[-1]] > self.precedence[token_value] or
                        (self.precedence[op_stack[-1]] == self.precedence[token_value] and
                         token_value not in self.right_assoc))):
                    output.append(op_stack.pop())
                op_stack.append(token_value)
        
        while op_stack:
            output.append(op_stack.pop())
        
        return output
    
    def evaluate_postfix(self, postfix: list) -> float:
        """Evaluate postfix expression"""
        stack = []
        
        for token in postfix:
            if isinstance(token, float):
                stack.append(token)
            elif token == 'NEG':
                stack.append(-stack.pop())
            else:
                b = stack.pop()
                a = stack.pop()
                if token == '+': stack.append(a + b)
                elif token == '-': stack.append(a - b)
                elif token == '*': stack.append(a * b)
                elif token == '/': stack.append(a / b)
        
        return stack[0]
    
    def calculate(self, expression: str) -> float:
        """Evaluate the expression"""
        tokens = self.tokenize(expression)
        postfix = self.to_postfix(tokens)
        return self.evaluate_postfix(postfix)


# Tests
calc = Calculator()
print(calc.calculate("3 + 4 * 2"))           # 11.0
print(calc.calculate("(1 + 2) * (3 + 4)"))   # 21.0
print(calc.calculate("-3 + 4"))              # 1.0
print(calc.calculate("-(2 + 3) * 4"))        # -20.0
print(calc.calculate("10 / 3"))              # 3.333...

Chapter Summary

The stack is one of the most fundamental data structures in computer science. Its LIFO property makes it naturally suited for problems involving "nesting" and "pairing."

Key takeaways:

Next chapter preview: In Chapter 6, we will study queues — the "dual" of stacks. From BFS to sliding windows, from priority queues to monotonic queues, the applications of queues are equally fascinating.