Stack

Back to DSA & Algorithms/00 - Roadmap Overview

What is a Stack?

A stack is a collection where the last element added is the first one removed — LIFO (Last In, First Out). Think of a stack of plates: you put plates on top, and you take plates from the top.

PUSH 1    PUSH 2    PUSH 3    POP       POP
                    ┌───┐
            ┌───┐   │ 3 │    ┌───┐
  ┌───┐     │ 2 │   │ 2 │    │ 2 │     ┌───┐
  │ 1 │     │ 1 │   │ 1 │    │ 1 │     │ 1 │
  └───┘     └───┘   └───┘    └───┘     └───┘
                              → 3       → 2

Operations

Operation	Time	What it does
`push(x)`	O(1)	Add element to top
`pop()`	O(1)	Remove and return top element
`peek()` / `top()`	O(1)	Look at top without removing
`isEmpty()`	O(1)	Check if stack is empty
`size()`	O(1)	Number of elements

Java Implementation

java
// Use ArrayDeque as a stack (NOT the legacy Stack class)
Deque<Integer> stack = new ArrayDeque<>();
stack.push(1);              // push
stack.push(2);              // push
stack.push(3);              // push
int top = stack.peek();     // peek → 3
int val = stack.pop();      // pop → 3
stack.size();               // size → 2
stack.isEmpty();            // isEmpty → false

// NEVER use java.util.Stack — it's synchronized, legacy, and extends Vector
// NEVER use stack iteration order for stack logic — iterate manually via pop/peek

When to Use a Stack

The magic question: "Do I need to process things in reverse order?" or "Do I need to remember what came before and come back to it?"

Common signals:

Matching pairs (parentheses, tags)
Undo/redo operations
Expression evaluation
"Next greater/smaller element"
DFS (iterative)
Nested structures (directories, JSON, HTML)

Pattern 1: Matching / Balancing

What it is

Use a stack to match opening elements with closing elements. Push opening elements, pop when you see the matching closing element.

When to use it

"Are these parentheses/brackets valid?"
"Decode nested strings"
"Evaluate nested expressions"

The Mental Model

You're reading a book with nested footnotes. When you hit a footnote¹, you put a bookmark (push). When the footnote ends, you go back to your bookmark (pop). If you finish reading but still have bookmarks left, something wasn't closed properly.

Step-by-Step: Valid Parentheses

java
// Problem: Are the brackets valid?
// "()" → true, "()[]{}" → true, "(]" → false, "([)]" → false

public boolean isValid(String s) {
    Deque<Character> stack = new ArrayDeque<>();
    // Map each closing bracket to its opening partner
    Map<Character, Character> pairs = Map.of(')', '(', ']', '[', '}', '{');

    for (char c : s.toCharArray()) {
        if (pairs.containsKey(c)) {
            // It's a closing bracket
            // Check if the top of stack has the matching opener
            if (stack.isEmpty() || stack.peek() != pairs.get(c)) {
                return false;
            }
            stack.pop();  // Match found! Remove the opener
        } else {
            // It's an opening bracket — push it
            stack.push(c);
        }
    }

    // Valid only if no unmatched openers remain
    return stack.isEmpty();
}

// Walkthrough: "({[]})"
// c='(': push → stack=['(']
// c='{': push → stack=['(', '{']
// c='[': push → stack=['(', '{', '[']
// c=']': closer! top='[' matches → pop → stack=['(', '{']
// c='}': closer! top='{' matches → pop → stack=['(']
// c=')': closer! top='(' matches → pop → stack=[]
// Stack empty → true ✓

// Walkthrough: "([)]"
// c='(': push → stack=['(']
// c='[': push → stack=['(', '[']
// c=')': closer! top='[' ≠ '(' → false ✗

Decode String

java
// "3[a2[c]]" → "accaccacc"
// Nested! Inner-most evaluates first — perfect for stack.

public String decodeString(String s) {
    Deque<String> stringStack = new ArrayDeque<>();
    Deque<Integer> countStack = new ArrayDeque<>();
    StringBuilder current = new StringBuilder();
    int num = 0;

    for (char c : s.toCharArray()) {
        if (Character.isDigit(c)) {
            num = num * 10 + (c - '0');  // Handle multi-digit numbers like "12"
        } else if (c == '[') {
            // Save current state and start fresh
            stringStack.push(current.toString());
            countStack.push(num);
            current = new StringBuilder();
            num = 0;
        } else if (c == ']') {
            // Pop previous state, build result
            int repeat = countStack.pop();
            String prevString = stringStack.pop();
            StringBuilder temp = new StringBuilder(prevString);
            for (int i = 0; i < repeat; i++) {
                temp.append(current);
            }
            current = temp;
        } else {
            current.append(c);
        }
    }

    return current.toString();
}

// Walkthrough: "3[a2[c]]"
// '3': num=3
// '[': push ("", 3), reset. stringStack=[""], countStack=[3], current="", num=0
// 'a': current="a"
// '2': num=2
// '[': push ("a", 2), reset. stringStack=["","a"], countStack=[3,2], current=""
// 'c': current="c"
// ']': pop ("a",2) → current = "a" + "c"*2 = "acc"
// ']': pop ("",3)  → current = "" + "acc"*3 = "accaccacc"

Problems

20. Valid Parentheses - Easy
394. Decode String - Medium
32. Longest Valid Parentheses - Hard
22. Generate Parentheses - Medium (backtracking)

Pattern 2: Monotonic Stack

What it is

A stack that maintains elements in a specific order (always increasing or always decreasing). When a new element violates the order, you pop elements until the order is restored.

When to use it

"For each element, find the next greater element"
"For each element, find the next smaller element"
"For each element, find the previous greater/smaller element"
"Largest rectangle in histogram"

The Mental Model

Imagine people standing in a line. A very tall person arrives. Every shorter person in front of them is now "overshadowed" — they've found their "next taller person". The tall person pushes them out (pop). The stack always contains people in decreasing height order.

People arriving: [2, 1, 4, 3]

Stack (decreasing):
  2 arrives: stack = [2]
  1 arrives: 1 < 2, push → stack = [2, 1]
  4 arrives: 4 > 1 → 1's "next greater" is 4! Pop.
             4 > 2 → 2's "next greater" is 4! Pop.
             stack = [4]
  3 arrives: 3 < 4, push → stack = [4, 3]
  Done: 4 and 3 have no next greater → -1

Step-by-Step: Next Greater Element

java
// For each element, find the first element to its RIGHT that is greater.
// Input:  [2, 1, 2, 4, 3]
// Output: [4, 2, 4, -1, -1]

public int[] nextGreaterElement(int[] nums) {
    int n = nums.length;
    int[] result = new int[n];
    Arrays.fill(result, -1);
    Deque<Integer> stack = new ArrayDeque<>();  // Stores INDICES (not values)

    for (int i = 0; i < n; i++) {
        // While current element is greater than stack top
        // → stack top has found its "next greater"
        while (!stack.isEmpty() && nums[i] > nums[stack.peek()]) {
            int idx = stack.pop();
            result[idx] = nums[i];  // nums[i] is the next greater for nums[idx]
        }

        stack.push(i);
    }

    return result;
}

// Walkthrough: [2, 1, 2, 4, 3]
// i=0, val=2: stack=[] → push 0. stack=[0]
// i=1, val=1: 1 < nums[0]=2 → push 1. stack=[0,1]
// i=2, val=2: 2 > nums[1]=1 → pop 1, result[1]=2
//             2 = nums[0]=2 (not >) → push 2. stack=[0,2]
// i=3, val=4: 4 > nums[2]=2 → pop 2, result[2]=4
//             4 > nums[0]=2 → pop 0, result[0]=4
//             push 3. stack=[3]
// i=4, val=3: 3 < nums[3]=4 → push 4. stack=[3,4]
// Done: indices 3,4 still in stack → result[3]=-1, result[4]=-1
// Result: [4, 2, 4, -1, -1] ✓

Daily Temperatures

java
// For each day, how many days until warmer?
// Input:  [73, 74, 75, 71, 69, 72, 76, 73]
// Output: [1,  1,  4,  2,  1,  1,  0,  0]

public int[] dailyTemperatures(int[] temperatures) {
    int n = temperatures.length;
    int[] result = new int[n];
    Deque<Integer> stack = new ArrayDeque<>();  // Indices of days waiting for a warmer day

    for (int i = 0; i < n; i++) {
        while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
            int prevDay = stack.pop();
            result[prevDay] = i - prevDay;  // Days waited
        }
        stack.push(i);
    }

    return result;
}

Largest Rectangle in Histogram (Classic Hard)

java
// Find the largest rectangle that can be formed in a histogram.
// This is THE most important monotonic stack problem.

public int largestRectangleArea(int[] heights) {
    Deque<Integer> stack = new ArrayDeque<>();  // Stores indices, heights in increasing order
    int maxArea = 0;
    int n = heights.length;

    for (int i = 0; i <= n; i++) {
        int currentHeight = (i == n) ? 0 : heights[i];  // Sentinel: forces all remaining bars to be processed
        // When current height is shorter than stack top,
        // the stack top can no longer extend right → calculate its area
        while (!stack.isEmpty() && currentHeight < heights[stack.peek()]) {
            int h = heights[stack.pop()];       // Height of the bar
            // Width: from current stack top (left boundary) to i (right boundary)
            int w = stack.isEmpty() ? i : i - stack.peek() - 1;
            maxArea = Math.max(maxArea, h * w);
        }

        stack.push(i);
    }

    return maxArea;
}

// Key insight:
// For each bar, we want to know: how far LEFT and RIGHT can it extend?
// It can extend until it hits a shorter bar.
// The monotonic stack tracks "previous shorter" (left boundary)
// and when we pop, the current element is "next shorter" (right boundary)

Also see 17 - Monotonic Stack & Queue for more detail.

Problems

496. Next Greater Element I - Easy
739. Daily Temperatures - Medium
84. Largest Rectangle in Histogram - Hard
85. Maximal Rectangle - Hard
503. Next Greater Element II - Medium (circular)

Pattern 3: Expression Evaluation

What it is

Use a stack to evaluate mathematical expressions, respecting operator precedence and parentheses.

The Mental Model

You're reading a math expression left to right. When you see a number, save it. When you see an operator, save it. When you see a higher-precedence operator, evaluate it immediately. When you see a closing parenthesis, evaluate everything back to the opening one.

Step-by-Step: Reverse Polish Notation

java
// Reverse Polish: operators come AFTER operands
// "2 1 + 3 *" means (2 + 1) * 3 = 9

public int evalRPN(String[] tokens) {
    Deque<Integer> stack = new ArrayDeque<>();

    for (String token : tokens) {
        switch (token) {
            case "+": {
                int b = stack.pop();
                int a = stack.pop();
                stack.push(a + b);
                break;
            }
            case "-": {
                int b = stack.pop();
                int a = stack.pop();
                stack.push(a - b);
                break;
            }
            case "*": {
                int b = stack.pop();
                int a = stack.pop();
                stack.push(a * b);
                break;
            }
            case "/": {
                int b = stack.pop();  // Second operand (popped first!)
                int a = stack.pop();  // First operand
                stack.push(a / b);    // Truncates toward zero in Java
                break;
            }
            default:
                stack.push(Integer.parseInt(token));
        }
    }

    return stack.pop();
}

// Walkthrough: ["2", "1", "+", "3", "*"]
// "2": push 2. stack=[2]
// "1": push 1. stack=[2, 1]
// "+": pop 1, pop 2. push 2+1=3. stack=[3]
// "3": push 3. stack=[3, 3]
// "*": pop 3, pop 3. push 3*3=9. stack=[9]
// Answer: 9

// GOTCHA: Pop order matters! b first, then a.
// For subtraction: a - b, NOT b - a

Basic Calculator II (With Precedence)

java
// "3+2*2" = 7 (not 10, because * has higher precedence)

public int calculate(String s) {
    Deque<Integer> stack = new ArrayDeque<>();
    int num = 0;
    char prevOp = '+';

    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);

        if (Character.isDigit(c)) {
            num = num * 10 + (c - '0');
        }

        if ((!Character.isDigit(c) && c != ' ') || i == s.length() - 1) {
            switch (prevOp) {
                case '+': stack.push(num); break;
                case '-': stack.push(-num); break;
                case '*': stack.push(stack.pop() * num); break;
                case '/': stack.push(stack.pop() / num); break;
            }
            prevOp = c;
            num = 0;
        }
    }

    int result = 0;
    for (int n : stack) {
        result += n;
    }
    return result;
}

// Key insight: Process * and / immediately (they have higher precedence).
// For + and -, just push to stack (process at the end by summing).

Problems

150. Evaluate Reverse Polish Notation - Medium
227. Basic Calculator II - Medium
224. Basic Calculator - Hard

Pattern 4: Stack for State Management

What it is

Use a stack to track the "current context" in nested or hierarchical structures.

Step-by-Step

java
// Simplify Unix Path: "/a/./b/../../c/" → "/c"
public String simplifyPath(String path) {
    Deque<String> stack = new ArrayDeque<>();

    for (String part : path.split("/")) {
        if (part.equals("..")) {
            if (!stack.isEmpty()) {
                stack.pop();         // Go up one directory
            }
        } else if (!part.isEmpty() && !part.equals(".")) {
            stack.push(part);        // Enter directory
        }
        // Skip empty parts (from "//") and "." (current dir)
    }

    StringBuilder result = new StringBuilder();
    for (String dir : stack) {
        result.insert(0, "/" + dir);
    }
    return result.length() == 0 ? "/" : result.toString();
}

// "/a/./b/../../c/"
// Split: ["", "a", ".", "b", "..", "..", "c", ""]
// "a": push → [a]
// ".": skip (current dir)
// "b": push → [a, b]
// "..": pop → [a]
// "..": pop → []
// "c": push → [c]
// Result: "/c"

Asteroid Collision

java
// Positive asteroids move right, negative move left.
// When they collide, smaller one explodes. Equal = both explode.
// Input: [5, 10, -5] → [5, 10] (10 beats -5)

public int[] asteroidCollision(int[] asteroids) {
    Deque<Integer> stack = new ArrayDeque<>();

    for (int ast : asteroids) {
        boolean alive = true;

        // Collision happens when: stack top is positive AND current is negative
        while (!stack.isEmpty() && ast < 0 && stack.peek() > 0) {
            if (stack.peek() < Math.abs(ast)) {
                stack.pop();            // Stack top explodes, continue checking
            } else if (stack.peek() == Math.abs(ast)) {
                stack.pop();            // Both explode
                alive = false;
                break;
            } else {
                alive = false;          // Current asteroid explodes
                break;
            }
        }

        if (alive) {
            stack.push(ast);
        }
    }

    int[] result = new int[stack.size()];
    for (int i = result.length - 1; i >= 0; i--) {
        result[i] = stack.pop();
    }
    return result;
}

Problems

Pattern 5: Min Stack (Design)

What it is

Design a stack that supports push, pop, top, and getMin — all in O(1).

Key Insight

Keep a second stack (or pairs) that tracks the minimum at each level. When you push, record what the minimum is AT THAT MOMENT. When you pop, you also pop the minimum.

java
class MinStack {
    private Deque<int[]> stack;  // each entry: [value, currentMinimum]

    public MinStack() {
        stack = new ArrayDeque<>();
    }

    public void push(int val) {
        int currentMin = stack.isEmpty() ? val : Math.min(val, stack.peek()[1]);
        stack.push(new int[]{val, currentMin});
    }

    public void pop() {
        stack.pop();
    }

    public int top() {
        return stack.peek()[0];
    }

    public int getMin() {
        return stack.peek()[1];
    }
}

// push(3): stack = [(3, 3)]
// push(5): stack = [(3, 3), (5, 3)]      min is still 3
// push(1): stack = [(3, 3), (5, 3), (1, 1)]  min is now 1
// getMin() → 1
// pop():   stack = [(3, 3), (5, 3)]       min goes back to 3!
// getMin() → 3

Problems

155. Min Stack - Medium

Things You MUST Be Aware Of

1. Empty Stack

java
// ALWAYS check if stack is empty before pop() or peek()
if (!stack.isEmpty()) {
    int val = stack.pop();
}
// Otherwise: NoSuchElementException

2. Stack vs Queue

Stack: LIFO — push() + pop()        → like a stack of plates
Queue: FIFO — offer() + poll()      → like a line at a store

// If you accidentally use java.util.Stack, it's synchronized and legacy
// Use ArrayDeque for both stacks and queues
// For stack: push() / pop() / peek()
// For queue: offer() / poll() / peek()

3. Monotonic Stack Direction

"Next GREATER element" → Decreasing monotonic stack (pop when current > top)
"Next SMALLER element" → Increasing monotonic stack (pop when current < top)

Trick to remember:
  - You POP elements that found their answer
  - The stack stores elements still WAITING for their answer
  - If looking for "next greater": elements in stack are waiting for something bigger
    → stack is in decreasing order (big at bottom, small at top)

4. Circular Arrays

java
// For circular "next greater", iterate through the array TWICE
// Use modulo: i % n

for (int i = 0; i < 2 * n; i++) {
    int actualIndex = i % n;
    // Process nums[actualIndex]
}

5. What the Stack Actually Stores

java
// Sometimes you store VALUES: for evaluation, matching
// Sometimes you store INDICES: for "distance" or "width" calculations
// Choose based on what information you need when popping

// For "how many days until warmer?" → store indices (need distance)
// For "evaluate expression" → store values (need the numbers)

Decision Guide

Matching brackets/tags?
  └── Push openers, pop on closers (Pattern 1)

"Next greater/smaller element"?
  └── Monotonic stack (Pattern 2)

Evaluate expression?
  └── Operator stack + operand stack (Pattern 3)

Nested structures (paths, JSON)?
  └── Stack tracks current context (Pattern 4)

"Design stack with getMin()"?
  └── Pair each value with its running minimum (Pattern 5)

"Largest rectangle in histogram"?
  └── Increasing monotonic stack — THE classic (Pattern 2)