Stack is a fundamental linear data structure in Java that enforces Last-In-First-Out (LIFO) behavior — elements are added and removed exclusively from one end, the top. This constraint makes stacks indispensable for tasks like expression evaluation, syntax validation, backtracking, and monotonic sequence analysis. This article first clarifies core stack concepts and idiomatic Java implementations, then walks through six carefully selected LeetCode problems — each illustrating a distinct pattern where stack-based reasoning unlocks an efficient, elegant solution.

Core Stack Mechanics in Java

Before diving into problem-solving, it's essential to understand how stacks behave and how they're best realized in modern Java.

Key Behavioral Properties

• LIFO Enforcement: All insertions (push) and removals (pop) occur at the top; direct access to internal elements is disallowed.
• Atomic Top Operations:
  • push(E): Adds element to top; size increases by one.
  • pop(): Removes and returns top element; size decreases by one.
  • peek(): Returns top element without removal.
• Capacity Model: Most standard implementations (e.g., ArrayDeque) grow dynamically. Fixed-capacity variants require explicit handling or custom wrappers.

Recommended Implementations

Java does not define a dedicated Stack interface. Instead, stack semantics are achieved via classes implementing Deque, with ArrayDeque being the de facto standard for new code:

Best Practice: Prefer Deque<E> stack = new ArrayDeque<>();. Use push(), pop(), and peek() — these map cleanly to stack semantics and avoid confusion with queue-oriented offer()/poll().

Basic Operations Example

import java.util.ArrayDeque;
import java.util.Deque;

public class StackDemo {
  public static void main(String[] args) {
    Deque<String> stack = new ArrayDeque<>();

    // Push three elements
    stack.push("first");
    stack.push("second");
    stack.push("third"); // 'third' is now at the top

    System.out.println("Top: " + stack.peek()); // third
    System.out.println("Popped: " + stack.pop()); // third
    System.out.println("Size: " + stack.size()); // 2
    System.out.println("Empty? " + stack.isEmpty()); // false
  }
}

LeetCode Problem Walkthroughs

1. Valid Parentheses (LeetCode #20)

Goal: Determine if a string of brackets is properly nested and closed.

Insight: Each closing bracket must match the most recent unmatched opening bracket — a perfect fit for LIFO.

Algorithm: Push opening brackets onto the stack. When encountering a closing bracket, verify it matches the top of the stack and pop. At the end, the stack must be empty.

import java.util.*;

class Solution {
  public boolean isValid(String s) {
    Map<Character, Character> pairs = Map.of(')', '(', '}', '{', ']', '[');
    Deque<Character> stack = new ArrayDeque<>();

    for (char c : s.toCharArray()) {
      if (pairs.containsKey(c)) {
        if (stack.isEmpty() || stack.pop() != pairs.get(c)) {
          return false;
        }
      } else {
        stack.push(c);
      }
    }
    return stack.isEmpty();
  }
}

2. Min Stack (LeetCode #155)

Goal: Design a stack supporting O(1) retrieval of the minimum value.

Insight: Maintain a parallel stack tracking the minimum seen so far at each depth.

Algorithm: On push(x), push x onto the main stack and also onto the min-stack if x <= currentMin. On pop(), pop both stacks if the value equals the current min.

import java.util.ArrayDeque;
import java.util.Deque;

class MinStack {
  private final Deque<Integer> values;
  private final Deque<Integer> mins;

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

  public void push(int x) {
    values.push(x);
    if (mins.isEmpty() || x <= mins.peek()) {
      mins.push(x);
    }
  }

  public void pop() {
    if (!values.isEmpty()) {
      int x = values.pop();
      if (!mins.isEmpty() && x == mins.peek()) {
        mins.pop();
      }
    }
  }

  public int top() { return values.peek(); }
  public int getMin() { return mins.peek(); }
}

3. Evaluate Reverse Polish Notation (LeetCode #150)

Goal: Compute the result of a postfix arithmetic expression.

Insight: Postfix notation eliminates operator precedence ambiguity: operands precede their operators, making stack evaluation natural.

Algorithm: Push numbers onto the stack. On hitting an operator, pop the two most recent numbers (the second-popped is the left operand), apply the operator, and push the result back.

import java.util.*;

class Solution {
  public int evalRPN(String[] tokens) {
    Deque<Integer> stack = new ArrayDeque<>();
    Set<String> ops = Set.of("+", "-", "*", "/");

    for (String t : tokens) {
      if (ops.contains(t)) {
        int b = stack.pop(); // right operand
        int a = stack.pop(); // left operand
        switch (t) {
          case "+": stack.push(a + b); break;
          case "-": stack.push(a - b); break;
          case "*": stack.push(a * b); break;
          case "/": stack.push(a / b); break; // integer division is sufficient
        }
      } else {
        stack.push(Integer.parseInt(t));
      }
    }
    return stack.pop();
  }
}

4. Daily Temperatures (LeetCode #739)

Goal: For each day, find how many days until a warmer temperature occurs.

Insight: A monotonic decreasing stack of indices efficiently tracks unresolved "colder" days, resolving them as soon as a warmer day appears.

Algorithm: Iterate temperatures. While current temp > temp[stack.peek()], resolve that index (result = currentIdx - poppedIdx). Push current index.

import java.util.*;

class Solution {
  public int[] dailyTemperatures(int[] temps) {
    int n = temps.length;
    int[] result = new int[n];
    Deque<Integer> stack = new ArrayDeque<>(); // indices of unresolved days

    for (int i = 0; i < n; i++) {
      while (!stack.isEmpty() && temps[i] > temps[stack.peek()]) {
        int j = stack.pop();
        result[j] = i - j;
      }
      stack.push(i);
    }
    return result;
  }
}

5. Validate Stack Sequences (LeetCode #31)

Goal: Given push and pop sequences, determine if the pop sequence is feasible.

Insight: Simulate the process: greedily push from the input sequence until the next required pop value is on top.

Algorithm: Use a stack and pointer into the push array. For each expected pop value, push until it’s on top (or exhaust push array), then pop. If top never matches, return false.

import java.util.*;

class Solution {
  public boolean validateStackSequences(int[] pushed, int[] popped) {
    Deque<Integer> stack = new ArrayDeque<>();
    int i = 0; // pointer in pushed array

    for (int val : popped) {
      while ((stack.isEmpty() || stack.peek() != val) && i < pushed.length) {
        stack.push(pushed[i++]);
      }
      if (!stack.isEmpty() && stack.peek() == val) {
        stack.pop();
      } else {
        return false;
      }
    }
    return true;
  }
}

6. Simplify Path (LeetCode #71)

Goal: Convert an absolute Unix path to its canonical form, resolving . (current dir) and .. (parenet dir).

Insight: Directory navigation is inherently hierarchical and reversible — ideal for stack-based path construction.

Algorithm: Split on /, ignore empty strings and ., pop for .., push otherwise. Join remaining parts with /.

import java.util.*;

class Solution {
  public String simplifyPath(String path) {
    String[] parts = path.split("/");
    Deque<String> stack = new ArrayDeque<>();

    for (String p : parts) {
      if (p.isEmpty() || p.equals(".")) continue;
      if (p.equals("..")) {
        if (!stack.isEmpty()) stack.pop();
      } else {
        stack.push(p);
      }
    }

    if (stack.isEmpty()) return "/";
    StringBuilder sb = new StringBuilder();
    for (String dir : stack) {
      sb.append("/").append(dir);
    }
    return sb.toString();
  }
}

Strategic Takeaways

• Prefer ArrayDeque: It’s faster, more flexible, and aligns with modern Java conventions.
• Monotonic Stacks Solve "Next Greater/Smaller": Maintain order (increasing/decreasing) to defer computation until context is known.
• Double Stacks Handle Auxiliary State: When you need O(1) accesss to metadata (min, max, history), pair a primary stack with a secondary one.
• Simulate When Order Matters: Problems involving sequences of operations (push/pop, directory traversal) often yield to direct simulation using a stack.