Stacks: Last In, First Out

Terminology

LIFO (Last In, First Out): An ordering principle where the most recently added element is the first one removed. Stacks follow LIFO ordering.
Push: The operation that adds an element to the top of the stack.
Pop: The operation that removes and returns the element at the top of the stack.
Peek (also called Top): Returns the top element without removing it.
Stack frame: A block of memory on the call stack that stores a function's local variables, parameters, and return address.
Stack overflow: An error that occurs when the call stack exceeds its allocated memory, typically caused by unbounded recursion.
Infix notation: Standard mathematical notation where operators sit between operands, e.g. 3 + 4.
Postfix notation (Reverse Polish Notation): A notation where operators follow their operands, e.g. 3 4 +. No parentheses are needed because evaluation order is unambiguous.
Amortized $O(1)$: An operation that is $O(1)$ on average over a sequence of operations, even though individual operations may occasionally cost more (e.g. when a dynamic array resizes).

What & Why

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

Why does this matter? Stacks are everywhere in computing. Every function call your program makes pushes a frame onto the call stack. Every time you hit "undo" in a text editor, a stack is involved. Compilers use stacks to parse expressions and validate matching brackets. Backtracking algorithms like depth-first search rely on stacks (explicitly or via recursion) to remember where to go next.

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.

Key properties:

LIFO ordering: the most recently added element is always the first removed
O(1) push, pop, and peek: all core operations are constant time
Restricted access: you can only interact with the top element
Two common implementations: array-backed (contiguous, cache-friendly) and linked-list-backed (no capacity limit)

How It Works

The Stack Model

A stack exposes three core operations. push(x) places element $x$ on top. pop() removes and returns the top element. peek() returns the top element without removing it. All three run in $O(1)$ time.

Array-Backed Stack

The most common implementation uses a dynamic array. A top index tracks the position of 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, just like a standard dynamic array.

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

Linked-List-Backed Stack

Alternatively, you can implement a stack as a singly linked list where push inserts at the head and pop removes from the head. Each operation is $O(1)$ with no amortization needed, since there's no resizing. The trade-off is pointer overhead per element and poor cache locality due to scattered heap allocations.

The Call Stack

Every running program has a call stack managed by the operating system. When a function is called, a new stack frame is pushed containing the function's local variables, parameters, and the return address (where to resume after the function completes). When the function returns, its frame is popped.

This is why recursion works: each recursive call gets its own frame with its own local state. It's also why infinite recursion causes a stack overflow: the call stack has a fixed size (typically 1-8 MB), and unbounded recursion exhausts it.

Expression Evaluation with Stacks

Stacks are the standard tool for evaluating arithmetic expressions. The two classic algorithms are:

Postfix (Reverse Polish) evaluation: scan tokens left to right. If the token is a number, push it. If it's an operator, pop two operands, apply the operator, and push the result. When you're done, the stack holds the final answer.

For example, evaluating 3 4 + 2 * (which is infix (3 + 4) * 2):

Push 3. Stack: [3]
Push 4. Stack: [3, 4]
See +: pop 4 and 3, push 3 + 4 = 7. Stack: [7]
Push 2. Stack: [7, 2]
See *: pop 2 and 7, push 7 * 2 = 14. Stack: [14]

Result: 14.

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

Operation	Array-backed	Linked-list-backed	Notes
push(x)	$O(1)$ amortized	$O(1)$	Array may resize on overflow
pop()	$O(1)$	$O(1)$	Decrement index or unlink head
peek()	$O(1)$	$O(1)$	Read without removal
isEmpty()	$O(1)$	$O(1)$	Check size or head pointer
Search	$O(n)$	$O(n)$	Must pop or iterate to find

Space Complexity

An array-backed stack holding $n$ elements uses $O(n)$ space. Due to the doubling strategy, the allocated capacity is at most $2n$, so the worst-case space overhead is a factor of 2:

$n \leq \text{capacity} \leq 2n$

A linked-list-backed stack uses exactly $n$ nodes, but each node carries pointer overhead. On a 64-bit system:

$\text{Space}_{\text{linked}} = n \times (\text{sizeof}(\text{value}) + 8) \text{ bytes}$

For small value types, the pointer overhead can be significant. For large value types, it's negligible.

Implementation

Array-Backed Stack (Pseudocode)

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 (Pseudocode)

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 (Pseudocode)

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

Call stacks: every programming language runtime uses a stack to manage function calls, local variables, and return addresses. This is the most fundamental use of stacks in computing.
Undo/redo: text editors, design tools, and IDEs maintain an undo stack of actions. Each action is pushed on edit; "undo" pops the last action and pushes it onto a redo stack.
Browser back/forward: navigating to a new page pushes the current URL onto the back stack. Clicking "back" pops from the back stack and pushes onto the forward stack.
Expression parsing: compilers and calculators use stacks for operator-precedence parsing, converting infix to postfix (Shunting Yard algorithm), and evaluating postfix expressions.
DFS and backtracking: depth-first search uses a stack (explicitly or via recursion) to explore graph nodes. Backtracking algorithms like maze solving and N-Queens push choices onto a stack and pop when they hit dead ends.
Syntax validation: linters and IDEs use stacks to check balanced brackets, matching HTML tags, and properly nested scopes.

Key Takeaways

A stack is a LIFO data structure with three core operations: push, pop, and peek, all running in $O(1)$ time
Array-backed stacks are the default choice: cache-friendly, simple, and amortized $O(1)$ push via dynamic array doubling
The call stack is a hardware/OS-level stack that manages function invocations, making recursion possible
Stacks are the go-to tool for expression evaluation (postfix), bracket matching, and any problem involving nested or reversible operations
When you see a problem that requires "process the most recent thing first" or "undo the last action," reach for a stack