Stacks: Last In, First Out

Terminology

What & Why

Why Stacks Matter

A stack is a linear data structure that follows the LIFO principle: the last element pushed on is the first one popped off. Think of a stack of plates: you always add to the top and remove from the top.

The Minimal Interface

The interface is intentionally minimal: push, pop, peek. This constraint is what makes stacks powerful. By restricting access to one end, you get a data structure that naturally models nested, reversible, and recursive processes.

How It Works

Array-Backed Stack

The most common implementation uses a dynamic array. A top index tracks the topmost element. Pushing increments top and writes to that slot. Popping reads from top and decrements it. When the array fills up, it doubles in capacity.

This approach is cache-friendly because elements are stored contiguously. Most languages use this strategy: JavaScript arrays with push/pop, Python lists, Java's ArrayDeque.

Linked-List-Backed Stack

Alternatively, a singly linked list where push inserts at the head and pop removes from the head. Each operation is strict $O(1)$ with no amortization. The trade-off is pointer overhead per element and poor cache locality.

The Call Stack

Every running program has a call stack managed by the OS. When a function is called, a new stack frame is pushed containing local variables, parameters, and the return address. When the function returns, its frame is popped.

Expression Evaluation with Stacks

Stacks are the standard tool for evaluating arithmetic expressions. The postfix (Reverse Polish) algorithm: scan tokens left to right. Numbers get pushed. Operators pop two operands, apply, and push the result.

Bracket Matching

Scan a string of brackets. For every opening bracket, push it. For every closing bracket, pop and check that it matches. If the stack is empty at the end and every bracket matched, the string is valid.

Complexity Analysis

Array vs Linked List Trade-offs

Space Complexity

An array-backed stack holding $n$ elements uses $O(n)$ space. Due to doubling, allocated capacity is at most $2n$:

A linked-list stack uses exactly $n$ nodes, but each carries pointer overhead:

Implementation

Array-Backed Stack

STRUCTURE ArrayStack:
    data ← empty array
    top ← -1

FUNCTION push(stack, value):
    stack.top ← stack.top + 1
    stack.data[stack.top] ← value

FUNCTION pop(stack):
    IF stack.top = -1 THEN ERROR "Stack underflow"
    value ← stack.data[stack.top]
    stack.top ← stack.top - 1
    RETURN value

FUNCTION peek(stack):
    IF stack.top = -1 THEN ERROR "Stack is empty"
    RETURN stack.data[stack.top]

FUNCTION isEmpty(stack):
    RETURN stack.top = -1

Postfix Expression Evaluator

FUNCTION evaluatePostfix(tokens):
    stack ← new ArrayStack

    FOR EACH token IN tokens:
        IF token is a number THEN
            push(stack, token)
        ELSE
            b ← pop(stack)
            a ← pop(stack)
            result ← apply(token, a, b)
            push(stack, result)

    RETURN pop(stack)

Bracket Matching

FUNCTION isBalanced(input):
    stack ← new ArrayStack
    pairs ← { ')':'(', ']':'[', '}':'{' }

    FOR EACH char IN input:
        IF char IN '([{' THEN
            push(stack, char)
        ELSE IF char IN ')]}' THEN
            IF isEmpty(stack) THEN RETURN false
            IF pop(stack) ≠ pairs[char] THEN RETURN false

    RETURN isEmpty(stack)

Real-World Applications

Key Takeaways