Stacks and Monotonic Stacks in Java

A stack is the right structure whenever the most recent unfinished thing is the one you need next. In Java the first decision is which class, and the historical answer is the wrong one.

ArrayDeque, not Stack

import java.util.*;

public class WhichStack {
    public static void main(String[] args) {
        Stack<Integer> legacy = new Stack<>();
        Deque<Integer> modern = new ArrayDeque<>();

        for (int i = 1; i <= 3; i++) { legacy.push(i); modern.push(i); }

        System.out.println("Stack iteration:       " + legacy);
        System.out.println("ArrayDeque iteration:  " + modern);
        System.out.println("Stack pop order:       " + legacy.pop() + legacy.pop() + legacy.pop());
        System.out.println("ArrayDeque pop order:  " + modern.pop() + modern.pop() + modern.pop());

        Stack<Integer> s = new Stack<>();
        s.push(10); s.push(20);
        System.out.println("Stack.get(0):          " + s.get(0) + "  (index access on a stack)");

        try { new ArrayDeque<Integer>().push(null); }
        catch (NullPointerException e) { System.out.println("ArrayDeque rejects null"); }
    }
}

$ java WhichStack.java
Stack iteration:       [1, 2, 3]
ArrayDeque iteration:  [3, 2, 1]
Stack pop order:       321
ArrayDeque pop order:  321
Stack.get(0):          10  (index access on a stack)
ArrayDeque rejects null

Both pop in the same order. Iteration is where they differ, and the difference is silent — migrating a Stack to an ArrayDeque reverses any code that iterated or printed it.

Why prefer the newer one:

• Stack extends Vector, so push, pop, and peek are all synchronized and pay an uncontended lock on every call.
• Vector gives you get(0), insertElementAt, remove(3) — operations a stack should not have.
• The Stack Javadoc itself recommends Deque for new code.

Measured on ten million push/pop pairs:

import java.util.*;

public class StackCost {
    public static void main(String[] args) {
        int n = 10_000_000;

        long t0 = System.nanoTime();
        Stack<Integer> legacy = new Stack<>();
        for (int i = 0; i < n; i++) legacy.push(i);
        while (!legacy.isEmpty()) legacy.pop();
        long t1 = System.nanoTime();

        Deque<Integer> modern = new ArrayDeque<>();
        for (int i = 0; i < n; i++) modern.push(i);
        while (!modern.isEmpty()) modern.pop();
        long t2 = System.nanoTime();

        System.out.printf("Stack       %7.1f ms%n", (t1-t0)/1e6);
        System.out.printf("ArrayDeque  %7.1f ms%n", (t2-t1)/1e6);
        System.out.printf("ratio: %.1fx%n", (double)(t1-t0)/(t2-t1));
    }
}

$ java StackCost.java
Stack        318.4 ms
ArrayDeque   127.9 ms
ratio: 2.5x

2.5x, and both still box every int. For a hot loop over primitives, an int[] with a manual top index beats both — mention it only if the constraints justify it.

Matching: the canonical use

import java.util.*;

public class Brackets {
    static boolean isValid(String s) {
        Deque<Character> stack = new ArrayDeque<>();
        Map<Character, Character> pairs = Map.of(')', '(', ']', '[', '}', '{');
        for (char c : s.toCharArray()) {
            if (pairs.containsValue(c)) stack.push(c);
            else if (pairs.containsKey(c)) {
                if (stack.isEmpty() || stack.pop() != pairs.get(c)) return false;
                // note: pop() returns Character, pairs.get returns Character — unboxed by !=
            }
        }
        return stack.isEmpty();       // leftovers mean unclosed brackets
    }

    public static void main(String[] args) {
        for (String s : new String[]{"()[]{}", "(]", "([)]", "([{}])", "", "(", ")"})
            System.out.printf("%-8s -> %s%n", "\"" + s + "\"", isValid(s));
    }
}

$ java Brackets.java
"()[]{}"  -> true
"(]"      -> false
"([)]"    -> false
"([{}])"  -> true
""        -> true
"("       -> false
")"       -> false

Two cases people forget: stack.isEmpty() before popping (input ")"), and stack.isEmpty() in the return (input "("). Without the second, "(" returns true.

The stack.pop() != pairs.get(c) comparison unboxes both Character values, so it compares char values, not references — correct here. Had one side been an Object, it would have compared references and silently failed for values above 127. Writing !Objects.equals(...) is the version that cannot break.

Monotonic stack: next greater element

import java.util.*;

public class NextGreater {
    static int[] brute(int[] nums) {
        int[] out = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            out[i] = -1;
            for (int j = i + 1; j < nums.length; j++)
                if (nums[j] > nums[i]) { out[i] = nums[j]; break; }
        }
        return out;
    }

    static int[] monotonic(int[] nums) {
        int[] out = new int[nums.length];
        Arrays.fill(out, -1);
        Deque<Integer> stack = new ArrayDeque<>();     // indices, decreasing values
        for (int i = 0; i < nums.length; i++) {
            while (!stack.isEmpty() && nums[i] > nums[stack.peek()])
                out[stack.pop()] = nums[i];            // nums[i] answers everything smaller
            stack.push(i);
        }
        return out;                                    // anything left has no greater element
    }

    public static void main(String[] args) {
        System.out.println(Arrays.toString(monotonic(new int[]{2, 1, 2, 4, 3})));

        int[] big = new int[100_000];
        for (int i = 0; i < big.length; i++) big[i] = big.length - i;   // worst case: decreasing

        long t0 = System.nanoTime(); int[] a = brute(big);      long t1 = System.nanoTime();
        int[] b = monotonic(big);                               long t2 = System.nanoTime();

        System.out.printf("brute     O(n^2)  %8.2f ms%n", (t1-t0)/1e6);
        System.out.printf("monotonic O(n)    %8.2f ms%n", (t2-t1)/1e6);
        System.out.printf("identical: %s   speedup: %.0fx%n",
                          Arrays.equals(a, b), (double)(t1-t0)/(t2-t1));
    }
}

$ java NextGreater.java
[4, 2, 4, -1, -1]
brute     O(n^2)   3184.20 ms
monotonic O(n)        4.87 ms
identical: true   speedup: 654x

The stack holds indices, not values, because the answer must be written back to the right position. The values at those indices are decreasing — that is the “monotonic” part, and it is what makes the pop correct: when nums[i] beats the top, it beats everything below it too.

The amortised argument, stated the way an interviewer wants:

“It looks like a nested loop, but each index is pushed exactly once and popped at most once. The total number of pops over the whole run is bounded by n, so the inner while does not multiply the outer loop — total work is at most 2n. O(n) time, O(n) space in the worst case when the input is strictly decreasing and nothing ever pops.”

Daily temperatures — the same stack, distances instead of values

import java.util.*;

public class DailyTemperatures {
    static int[] dailyTemperatures(int[] t) {
        int[] out = new int[t.length];
        Deque<Integer> stack = new ArrayDeque<>();
        for (int i = 0; i < t.length; i++) {
            while (!stack.isEmpty() && t[i] > t[stack.peek()]) {
                int j = stack.pop();
                out[j] = i - j;                  // distance, not value
            }
            stack.push(i);
        }
        return out;
    }
    public static void main(String[] args) {
        System.out.println(Arrays.toString(dailyTemperatures(new int[]{73,74,75,71,69,72,76,73})));
        System.out.println(Arrays.toString(dailyTemperatures(new int[]{30,40,50,60})));
        System.out.println(Arrays.toString(dailyTemperatures(new int[]{30,20,10})));
    }
}

$ java DailyTemperatures.java
[1, 1, 4, 2, 1, 1, 0, 0]
[1, 1, 1, 0]
[0, 0, 0]

Identical to next-greater-element except for one line: out[j] = i - j instead of out[j] = nums[i]. Recognising that they are one problem is worth more than having memorised both.

Largest rectangle — where the sentinel earns its place

import java.util.*;

public class Histogram {
    static int largestRectangleArea(int[] heights) {
        Deque<Integer> stack = new ArrayDeque<>();
        int best = 0;
        for (int i = 0; i <= heights.length; i++) {
            int h = (i == heights.length) ? 0 : heights[i];   // sentinel flushes the stack
            while (!stack.isEmpty() && heights[stack.peek()] > h) {
                int height = heights[stack.pop()];
                int left = stack.isEmpty() ? -1 : stack.peek();
                best = Math.max(best, height * (i - left - 1));
            }
            stack.push(i);
        }
        return best;
    }
    public static void main(String[] args) {
        System.out.println(largestRectangleArea(new int[]{2,1,5,6,2,3}));
        System.out.println(largestRectangleArea(new int[]{2,4}));
        System.out.println(largestRectangleArea(new int[]{5}));
        System.out.println(largestRectangleArea(new int[]{}));
    }
}

$ java Histogram.java
10
4
5
0

Two tricks here that are worth naming rather than reproducing from memory:

• The loop runs to heights.length inclusive with a virtual height of 0, which forces every remaining bar off the stack. Without it, a non-decreasing input like [1,2,3] never pops and returns 0.
• The width is i - left - 1 where left is the new stack top after popping — the bar below is the first one shorter on the left, so the rectangle spans strictly between them.

Note stack.push(i) inside the loop pushes heights.length on the final iteration. It is never read, because the loop ends — harmless, and simpler than special-casing it.

Recognising it

SIGNAL                                          PATTERN
matching pairs, nesting, balance                plain stack
"undo", "most recent unfinished"                plain stack
evaluate expression / RPN                       plain stack
"next greater / smaller element"                monotonic stack of indices
"days until warmer", "span"                     monotonic stack, store the distance
largest rectangle, trapping rain water          monotonic stack with a sentinel
iterative DFS or tree traversal                 explicit stack replacing recursion

Practice

Stack:      [1, 2, 3]
ArrayDeque: [3, 2, 1]

Stack 318.4 ms      ArrayDeque 127.9 ms      2.5x

"(" -> true      (wrong; should be false)

"Each index is pushed once and popped at most once, so total pops <= n.
 The inner while does not multiply the outer loop — at most 2n operations."

Next: linked lists and trees — reference manipulation, the dummy-head idiom, and iterative traversal with an explicit ArrayDeque.