Data Structures: The Stack

A stack is a last-in-first-out (LIFO) data structure that only allows insertion and deletion at the top. It can be implemented with an array or a linked list.

The reason the stack deserves its own post is that it's just about the simplest data structure there is, yet it's everywhere: function calls, exception stack traces, the browser's back button, an editor's undo — all the same model underneath. Plenty of problems that look complicated (bracket matching, expression evaluation) become instantly clear once you think of using a stack. Understanding the stack is also a prerequisite for understanding recursion and call-stack overflow issues.

Basic Concepts

In a stack, insertion and deletion are usually called push and pop. When an element is inserted, it goes on top of the stack; when an element is removed, it comes off the top. The top of the stack holds the most recently added element; the bottom holds the earliest.

Think of a stack as a pile of plates: a new plate can only go on top, and you can only take plates from the top. That "single opening" constraint is exactly where the stack's value lies — it naturally remembers "who came in last", making it perfect for anything that needs to "retrace its steps".

Stacks are used everywhere. For instance, function calls and recursive calls in a computer are implemented with a stack. When a function is called, its arguments, return address, and local variables are pushed onto the stack; when the function returns, that information is popped back off.

Basic Operations

The basic operations of a stack:

push(element): push an element onto the top of the stack.

pop(): pop an element off the top of the stack.

top(): return the top element without modifying the stack.

isEmpty(): check whether the stack is empty.

size(): return the number of elements in the stack.

Note the difference between pop and top: pop removes the top element and returns it, while top (called peek in some implementations) just "takes a look" and leaves the stack unchanged. Mixing these two up is a common source of bugs.

Implementing a stack with an array is very direct — just maintain an index pointing at the top:

// A simple array-based stack, core logic only
public class ArrayStack {
    private int[] data;
    private int top = -1; // index of the top element; -1 means empty

    public ArrayStack(int capacity) {
        data = new int[capacity];
    }

    public void push(int element) {
        // In real code, grow the array or throw a stack-full exception here
        data[++top] = element; // advance the top pointer first, then write
    }

    public int pop() {
        // Should throw on an empty stack; check omitted here
        return data[top--]; // return the top element and move the pointer back
    }

    public int top() {
        return data[top]; // read only, no modification
    }

    public boolean isEmpty() {
        return top == -1;
    }

    public int size() {
        return top + 1;
    }
}

A linked-list implementation treats the list head as the top of the stack: push is a head insertion, pop deletes the head node. The advantage is that you don't need to pre-allocate capacity.

Complexity Analysis

A stack's time complexity is O(1), because every operation happens at the top. Its space complexity, however, is O(n), since all elements have to be stored.

Put another way: the stack's efficiency comes precisely from its restrictions. Because insertion and deletion in the middle aren't allowed, every operation reduces to a single read or write at the top — no shifting of other elements, no traversal. The one exception in the array implementation is the copy during resizing, but amortized, push is still constant time.

Classic Applications

In computing, stacks are widely used in function calls, expression evaluation, compilers, operating systems, and more.

1. Function calls: when a function is called, its arguments, return address, and local variables are pushed onto the stack, and popped off when the function returns. This is the function call stack, the foundation of how function calls work.
2. Expression evaluation: when a computer evaluates an expression, a stack is typically involved. For example, converting an infix expression to postfix requires a stack to hold operators so the expression's value is computed correctly.
3. Compilers: while translating source code into target code, compilers use stacks for parsing and code generation. In a compiler, stacks hold information about variables, functions, statements, and so on.
4. Operating systems: process scheduling, interrupt handling, and similar OS features also rely on stacks. When a process is interrupted, the OS pushes the current process's context (register values, program counter, etc.) onto a stack, then runs the interrupt handler. When the handler finishes, the OS pops the context back off and resumes the process.

These four scenarios share one thing: a nested "enter — process — exit in reverse order" structure. Nested function calls, nested brackets, nested interrupts — they're fundamentally the same class of problem, which is why they all map onto the stack model. Bracket matching, monotonic stacks, and the iterative form of depth-first traversal you meet in coding exercises are all extensions of the same idea.

Gotchas

1. Empty-stack operations: calling pop or top on an empty stack is either undefined behavior or throws outright. Either check with isEmpty first or explicitly rely on exception handling — don't just assume.

2. Stack overflow: recursion is fundamentally consuming the call stack, and going too deep overflows it (StackOverflowError in Java). For recursion of uncontrolled depth, rewrite it as an iterative version with an explicit stack and a loop, moving the data onto the heap.

tip

In Java, avoid java.util.Stack — it extends Vector, its methods carry synchronization overhead, and the design is dated. The official docs recommend ArrayDeque as a stack.

3. Confusing pop with top: calling pop when you only meant to read the top silently drops an element — a class of bug that's especially hard to track down inside a loop.

Wrapping Up

The stack is the textbook case of trading constraints for efficiency: expose only one opening at the top, and in exchange every operation costs O(1), while naturally fitting anything nested or backtracking-shaped. Once you've internalized push/pop/top and the LIFO mental model, the function call stack, expression evaluation, and the rest are just the same model applied at different levels.