Free lesson · DSA Mastery - Interview Prep, End to End

Introduction to Stacks

Medium4 min readdsastacks

Introduction to Stacks

A stack is the simplest of the "restricted access" data structures, and one of the most quietly powerful. It enforces a single discipline - last in, first out (LIFO) - and from that one rule emerges the machinery behind expression evaluation, balanced-bracket checking, undo systems, depth-first traversal, backtracking, and the function call stack your program runs on right now. This introduction lays out the stack's operations and guarantees, the mental model of "the most recent thing is the one you deal with first," and the two great problem families this module is organized around: standard stack problems and the monotonic stack.

If you internalize one idea here, make it this: a stack is what you reach for whenever the thing you need next is the thing you saw most recently.

What a Stack Is

A stack stores elements in a pile. You can only touch the top: you push a new element onto the top, pop the top element off, and peek at the top without removing it. Every operation is O(1) - no searching, no shifting, no index arithmetic. The element you pushed most recently is the first one you'll pop; the element you pushed first is buried deepest and comes out last.

Deque<Integer> stack = new ArrayDeque<>();
stack.push(1);          // [1]
stack.push(2);          // [1, 2]  (2 on top)
stack.push(3);          // [1, 2, 3]
int top = stack.peek(); // 3, not removed
stack.pop();            // removes 3 -> [1, 2]
stack.pop();            // removes 2 -> [1]

graph TD
    A["push 3 → top"] --> B["3"]
    B --> C["2"]
    C --> D["1 ← bottom"]
    E["pop removes 3 first (LIFO)"]

    style A fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style B fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style C fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style D fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style E fill:#dc2626,stroke:#ef4444,color:#f1f5f9

This diagram shows a stack holding one, two, three with three on top. Push adds to the top and pop removes from the top, so the most recently added element, three, comes off first. This is the last-in-first-out discipline.

Why LIFO Is the Whole Point

The LIFO rule sounds limiting, but it's exactly the structure that matches a huge class of problems where nesting or recency governs the logic. Brackets close in reverse order of opening - the last bracket opened must be the first closed - which is LIFO. A function returns to its most recent caller - LIFO. An undo reverses your most recent action - LIFO. When you process a sequence and need to "remember things until a matching event arrives, then resolve the most recent one first," a stack is the natural fit, and usually the optimal one.

Implementation Choices

In Java, prefer ArrayDeque as a stack (push, pop, peek) over the legacy Stack class (which is synchronized and slower). Internally it's a resizable array, giving amortized O(1) operations and good cache behavior. You can also use a plain array with a top index, or build one on a linked list - but ArrayDeque is the idiomatic, efficient default. A few conventions used throughout this module:

• push(x) adds to the top; pop() removes and returns the top; peek() returns the top without removing.
• Always check isEmpty() before pop/peek to avoid underflow.
• When a stack holds indices rather than values (common in monotonic-stack problems), the value is recovered as array[stack.peek()].

The Two Problem Families

This module is organized around the two ways stacks show up in interviews.

Standard stack problems (16.2–16.19). The stack is used in its most direct role: track nested or pending state and resolve it in LIFO order. Balanced parentheses, expression evaluation (Reverse Polish, calculators), string cleanup (remove adjacent duplicates, stars, duplicate letters), path simplification, and collision-style simulations (asteroids, car fleets). The unifying move is "push pending items; when a closing or resolving event arrives, pop and reconcile."

Monotonic stack (16.20–16.37). A specialized discipline where the stack is kept sorted (increasing or decreasing) by popping elements that violate the order before pushing a new one. This single idea answers an entire genre of questions - "next greater element," "previous smaller element," "how far until a larger value," "largest rectangle in a histogram" - in O(n) time, replacing the obvious O(n²) nested scan. It's one of the highest-leverage patterns in all of array and stack interviewing, which is why it gets its own introduction (16.20) and the back half of this module.

graph TD
    A["Stack (LIFO)"] --> B["Standard problems (16.2-16.19)<br/>track & resolve nested/pending state"]
    A --> C["Monotonic stack (16.20-16.37)<br/>maintain sorted order for O(n) range queries"]

    style A fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style B fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style C fill:#4338ca,stroke:#6366f1,color:#f1f5f9

This diagram shows the two families. Standard stack problems use the last-in-first-out rule to track and resolve nested or pending state. The monotonic stack maintains a sorted order to answer next-greater and similar range queries in linear time.

When to Reach for a Stack

In an interview, a few signals should make you think "stack":

• Matching or nesting: brackets, tags, function calls - anything that opens and closes in reverse order.
• Most-recent-first resolution: when an incoming event resolves against the latest pending item (asteroid collisions, adjacent-duplicate removal).
• Expression evaluation: operators and operands processed by precedence or postfix order.
• "Next/previous greater or smaller": the monotonic-stack signature - for each element, find the nearest element on one side satisfying an inequality.
• Replacing recursion: any depth-first process can be made iterative with an explicit stack (you'll see this echo the tree and graph sections later).

A Note on Reading the Code

Throughout this module, stacks hold either values or indices depending on what the problem needs. Watch that distinction closely: storing indices lets you compute distances and widths (essential for Daily Temperatures, Largest Rectangle), while storing values suffices for pure matching and evaluation. Each topic states which it uses and why, and every algorithm comes with a frame-by-frame trace of the stack's contents so you can watch the LIFO discipline play out.

Let's begin with the canonical stack problem - the one that defines the entire standard family. Valid Parentheses asks whether a string of brackets is properly balanced and nested, and its solution is the purest expression of "push openers, pop and match on closers" you'll ever write.

Back to DSA Mastery - Interview Prep, End to End