The stack is one of the most versatile data structures in coding interviews. Whether you’re matching parentheses, evaluating expressions, or finding the next greater element in an array, a stack gives you an elegant O(n) solution. This guide collects the essential Java templates you’ll need, organized by pattern so you can quickly find the right approach for any stack problem.

New to Stack problems? A stack is Last-In-First-Out (LIFO). The key insight: whenever a problem asks you to match, nest, or find the “next greater/smaller” element, think stack.

Quick Reference

| Pattern | Signal Phrases | Key Idea | |—|—|—| | Parentheses | “valid brackets”, “minimum remove” | Match open/close pairs | | Expression | “calculate”, “evaluate” | Operator precedence via stack | | Next Greater | “next greater”, “next warmer day” | Monotonic decreasing stack | | Next Smaller | “next smaller”, “stock span” | Monotonic increasing stack | | Histogram | “largest rectangle”, “maximal rectangle” | Expand left/right using stack | | Sliding Window Max | “maximum in window” | Monotonic deque |

Contents

Parentheses Matching

When to use: matching brackets, nested structures

Use stack’s LIFO property to match opening and closing brackets in reverse order.

Parentheses Matching — Step-by-Step for ({[]}) ( { [ ] } ) Step 1: ( push ( Step 2: { push { ( Step 3: [ push [ { ( Step 4: ] match [ → pop ✓ { ( Step 5: } match { → pop ✓ ( Step 6: ) match ( → pop ✓ empty Result: Valid ✓ — Stack is empty after processing all characters
ID Title Link Solution
20 Valid Parentheses Link Solution
921 Minimum Add to Make Valid Parentheses Link Solution
1249 Minimum Remove to Make Valid Parentheses Link Solution 
// import java.util.*;
static boolean isValid(String s) {
    Deque<char> st = new ArrayDeque<>();
    HashMap<char, char> map = {
        {'}', '{'}, {']', '['}, {')', '('}
    }
    for (char c : s.toCharArray()) {
        if(c == '{' || c == '[' || c == '(') {
            st.offer(c);
        } else {
            if(st.length == 0 || st.peek() != map[c]) return false;
            st.poll();
        }
    }
    return st.length == 0;
}
ID Title Link Solution
20 Valid Parentheses Link Solution
921 Minimum Add to Make Valid Parentheses Link Solution
1249 Minimum Remove to Make Valid Parentheses Link Solution

Expression Evaluation

When to use: calculate expression, operator precedence

Use stack to handle operator precedence and parentheses in mathematical expressions.

ID Title Link Solution
150 Evaluate Reverse Polish Notation Link Solution
224 Basic Calculator Link Solution
227 Basic Calculator II Link Solution
772 Basic Calculator III Link Solution 
// import java.util.*;
static int calculate(String s) {
    Deque<Integer> stk = new ArrayDeque<>();
    int result = 0, num = 0, sign = 1;

    for (char c : s.toCharArray()) {
        if(isdigit(c)) {
            num = num 10 + (c - '0');
        } else if(c == '+' || c == '-') {
            result += sign num;
            sign = (c == '+') ? 1 : -1;
            num = 0;
        } else if(c == '(') {
            stk.offer(result);
            stk.offer(sign);
            result = 0;
            sign = 1;
        } else if(c == ')') {
            result += sign num;
            result *= stk.peek(); stk.poll();
            result += stk.peek(); stk.poll();
            num = 0;
        }
    }
    return result + sign num;
}
ID Title Link Solution
150 Evaluate Reverse Polish Notation Link Solution
224 Basic Calculator Link Solution
227 Basic Calculator II Link Solution
772 Basic Calculator III Link Solution

Nested Structure Processing

Use stack to process nested structures like strings, expressions, or function calls.

ID Title Link Solution
394 Decode String Link Solution
636 Exclusive Time of Functions Link Solution
71 Simplify Path Link - 
// import java.util.*;
static String decodeString(String s) {
    Deque<String> st = new ArrayDeque<>();
    String curr = "";
    int k = 0;

    for (char c : s.toCharArray()) {
        if(isdigit(c)) {
            k = k 10 + (c - '0');
        } else if(c == '[') {
            st.offer(String.valueOf(k));
            st.offer(curr);
            curr = "";
            k = 0;
        } else if(c == ']') {
            String prev = st.peek(); st.poll();
            int count = Integer.parseInt(st.peek()); st.poll();
            String temp = "";
            for(int i = 0; i < count; i++) temp += curr;
            curr = prev + temp;
        } else {
            curr += c;
        }
    }
    return curr;
}
ID Title Link Solution
394 Decode String Link Solution
636 Exclusive Time of Functions Link Solution
71 Simplify Path Link -

Monotonic Stack & Deque Patterns

When to use: next greater/smaller element, histogram problems

Eight common patterns that cover nearly all monotonic stack / deque problems. Recognize the pattern by this clue: “find the next/previous smaller/greater element, or determine how far an element can extend.”

Monotonic Stack — Next Greater Element for [2, 1, 4, 3] 2 1 4 3 Step 1: push 2 2 stack: [2] Step 2: push 1 (1 < 2, no pop) 1 2 stack: [2, 1] Step 3: push 4 4 > 1 → pop, ans[1]=4 4 > 2 → pop, ans[0]=4 4 stack: [4] Step 4: push 3 (3 < 4, no pop) 3 4 stack: [4, 3] Result: [4, 4, -1, -1] Elements left on the stack have no next greater element → -1

Pattern 1: Next Greater Element

Find the first element to the right that is strictly greater. Use a monotonic decreasing stack (top is smallest).

ID Title Link Solution
496 Next Greater Element I Link Solution
739 Daily Temperatures Link Solution
503 Next Greater Element II Link Solution
901 Online Stock Span Link -
1944 Visible People in Queue Link Solution

Pattern 2: Next Smaller Element

Same idea but reversed comparison. Use a monotonic increasing stack (top is largest).

ID Title Link Solution
1475 Final Prices With Special Discount Link -
84 Largest Rectangle in Histogram Link Solution

Pattern 3: Previous Greater / Smaller Element

Instead of looking right, find the left boundary. Scan left-to-right, the stack top is the previous greater/smaller.

Finding both previous smaller and next smaller defines the range where an element is the minimum – critical for range-based counting.

ID Title Link Solution
907 Sum of Subarray Minimums Link -
2104 Sum of Subarray Ranges Link -

Pattern 4: Histogram Expansion

Each bar expands left and right until hitting a shorter bar. Width = right_smaller - left_smaller - 1.

Combine next smaller (right boundary) and previous smaller (left boundary) to compute the maximum rectangle.

Largest Rectangle in Histogram — [2, 1, 5, 6, 2, 3] 2 1 5 6 2 3 area = 10 0 1 2 3 4 5 width = 2 height = 5
ID Title Link Solution
84 Largest Rectangle in Histogram Link Solution
42 Trapping Rain Water Link Solution

Pattern 5: Matrix → Histogram Trick

Convert each row of a binary matrix into a histogram of heights, then run the histogram algorithm on each row.

ID Title Link Solution
85 Maximal Rectangle Link -

Pattern 6: Monotonic Deque (Sliding Window Max/Min)

When to use: sliding window maximum/minimum

Maintain a monotonic decreasing deque of indices for sliding window maximum. Remove smaller elements from back, remove out-of-window elements from front.

Sliding Window Maximum — k = 3 1 3 -1 -3 5 3 6 7 0 1 2 3 4 5 6 7 Window [0..2] 1 3 -1 deque: 3 -1 max = 3 Window [1..3] 3 -1 -3 deque: 3 -1 -3 max = 3 Window [2..4] -1 -3 5 deque: 5 max = 5 Window [3..5] -3 5 3 deque: 5 3 max = 5 Output: [3, 3, 5, 5, 6, 7]
ID Title Link Solution
239 Sliding Window Maximum Link Solution

Pattern 7: Greedy Stack (Remove Digits / Lexicographic Optimization)

When to use: remove digits, lexicographic optimization

Use the stack to maintain an optimal ordering. While the stack top is worse than the current element and we still have removals left, pop it.

ID Title Link Solution
402 Remove K Digits Link -
316 Remove Duplicate Letters Link Solution

Pattern 8: Prefix Sum + Monotonic Deque

Find the shortest subarray with sum at least k. Combine prefix sums with an increasing deque to efficiently find the closest valid left boundary.

ID Title Link Solution
862 Shortest Subarray with Sum at Least K Link Solution

Practice Roadmap

Follow this progression from basics to advanced:

Step Focus Problems
1 Basics Next Greater Element I (496), Daily Temperatures (739)
2 Core Stack Mastery Next Greater Element II (503), Online Stock Span (901)
3 Histogram Largest Rectangle in Histogram (84), Maximal Rectangle (85)
4 Advanced Range Counting Sum of Subarray Minimums (907), Sum of Subarray Ranges (2104)
5 Deque + Advanced Sliding Window Maximum (239), Shortest Subarray with Sum at Least K (862) 
// import java.util.*;
int[]nextGreater(int[] nums) {
    int n = nums.length;
    int[]ans(n, -1);
    Deque<Integer> st = new ArrayDeque<>();

    for (int i = 0; i < n; i++) {
        while (!st.isEmpty() && nums[st.peek()] < nums[i]) {
            ans[st.peek()] = nums[i];
            st.poll();
        }
        st.offer(i);
    }
    return ans;
}
ID Title Link Solution
496 Next Greater Element I Link Solution
739 Daily Temperatures Link Solution
503 Next Greater Element II Link Solution
901 Online Stock Span Link -
1944 Visible People in Queue Link Solution

Pattern 2: Next Smaller Element

Same idea but reversed comparison. Use a monotonic increasing stack (top is largest).

// import java.util.*;
int[]nextSmaller(int[] nums) {
    int n = nums.length;
    int[]ans(n, -1);
    Deque<Integer> st = new ArrayDeque<>();

    for (int i = 0; i < n; i++) {
        while (!st.isEmpty() && nums[st.peek()] > nums[i]) {
            ans[st.peek()] = nums[i];
            st.poll();
        }
        st.offer(i);
    }
    return ans;
}
ID Title Link Solution
1475 Final Prices With Special Discount Link -
84 Largest Rectangle in Histogram Link Solution

Pattern 3: Previous Greater / Smaller Element

Instead of looking right, find the left boundary. Scan left-to-right, the stack top is the previous greater/smaller.

Finding both previous smaller and next smaller defines the range where an element is the minimum – critical for range-based counting.

// import java.util.*;
// Previous smaller element (strictly)
int[]prevSmaller(int[] nums) {
    int n = nums.length;
    int[]ans(n, -1);
    Deque<Integer> st = new ArrayDeque<>();

    for (int i = 0; i < n; i++) {
        while (!st.isEmpty() && nums[st.peek()] >= nums[i])
            st.poll();
        if (!st.isEmpty()) ans[i] = st.peek();
        st.offer(i);
    }
    return ans;
}
ID Title Link Solution
907 Sum of Subarray Minimums Link -
2104 Sum of Subarray Ranges Link -

Pattern 4: Histogram Expansion

Each bar expands left and right until hitting a shorter bar. Width = right_smaller - left_smaller - 1.

Combine next smaller (right boundary) and previous smaller (left boundary) to compute the maximum rectangle.

// import java.util.*;
static int largestRectangleArea(int[] heights) {
    int n = heights.length, ans = 0;
    Deque<Integer> st = new ArrayDeque<>();

    for (int i = 0; i <= n; i++) {
        int h = (i == n) ? 0 : heights[i];
        while (!st.isEmpty() && heights[st.peek()] > h) {
            int height = heights[st.peek()]; st.poll();
            int width = st.length == 0 ? i : i - st.peek() - 1;
            ans = Math.max(ans, height width);
        }
        st.offer(i);
    }
    return ans;
}
ID Title Link Solution
84 Largest Rectangle in Histogram Link Solution
42 Trapping Rain Water Link Solution

Pattern 5: Matrix → Histogram Trick

Convert each row of a binary matrix into a histogram of heights, then run the histogram algorithm on each row.

static int maximalRectangle(char[][]& matrix) {
    if (matrix.length == 0) return 0;
    int m = matrix.length, n = matrix[0].length, ans = 0;
    int[] heights = new int[n];

    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++)
            heights[j] = (matrix[i][j] == '1') ? heights[j] + 1 : 0;
        ans = Math.max(ans, largestRectangleArea(heights));
    }
    return ans;
}
ID Title Link Solution
85 Maximal Rectangle Link -

Pattern 6: Monotonic Deque (Sliding Window Max/Min)

Maintain a monotonic decreasing deque of indices for sliding window maximum. Remove smaller elements from back, remove out-of-window elements from front.

// import java.util.*;
int[]maxSlidingWindow(int[] nums, int k) {
    ArrayDeque<Integer> dq = new ArrayDeque<>();
    List<Integer> ans = new ArrayList<>();

    for (int i = 0; i < nums.length; i++) {
        while (!dq.isEmpty() && nums[dq.get(dq.size() - 1)] <= nums[i])
            dq.removeLast();
        dq.add(i);
        if (dq.get(0) <= i - k) dq.removeFirst();
        if (i >= k - 1) ans.add(nums[dq.get(0)]);
    }
    return ans;
}
ID Title Link Solution
239 Sliding Window Maximum Link Solution

Pattern 7: Greedy Stack (Remove Digits / Lexicographic Optimization)

Use the stack to maintain an optimal ordering. While the stack top is worse than the current element and we still have removals left, pop it.

static String removeKdigits(String num, int k) {
    String st;
    for (char c : num) {
        while (k > 0 && !st.isEmpty() && st.get(st.size() - 1) > c) {
            st.removeLast();
            k--;
        }
        st.add(c);
    }
    while (k-- > 0) st.removeLast();

    // strip leading zeros
    int start = 0;
    while (start < (int)st.size() && st[start] == '0') start++;
    String ans = st.substring(start);
    return ans.length == 0 ? "0" : ans;
}
ID Title Link Solution
402 Remove K Digits Link -
316 Remove Duplicate Letters Link Solution

Pattern 8: Prefix Sum + Monotonic Deque

Find the shortest subarray with sum at least k. Combine prefix sums with an increasing deque to efficiently find the closest valid left boundary.

// import java.util.*;
static int shortestSubarray(int[] nums, int k) {
    int n = nums.length, ans = n + 1;
    long[]pre(n + 1, 0);
    for (int i = 0; i < n; i++) pre[i + 1] = pre[i] + nums[i];

    ArrayDeque<Integer> dq = new ArrayDeque<>();
    for (int i = 0; i <= n; i++) {
        while (!dq.isEmpty() && pre[i] - pre[dq.get(0)] >= k) {
            ans = Math.min(ans, i - dq.get(0));
            dq.removeFirst();
        }
        while (!dq.isEmpty() && pre[dq.get(dq.size() - 1)] >= pre[i])
            dq.removeLast();
        dq.add(i);
    }
    return ans <= n ? ans : -1;
}
ID Title Link Solution
862 Shortest Subarray with Sum at Least K Link Solution

Practice Roadmap

Follow this progression from basics to advanced:

Step Focus Problems
1 Basics Next Greater Element I (496), Daily Temperatures (739)
2 Core Stack Mastery Next Greater Element II (503), Online Stock Span (901)
3 Histogram Largest Rectangle in Histogram (84), Maximal Rectangle (85)
4 Advanced Range Counting Sum of Subarray Minimums (907), Sum of Subarray Ranges (2104)
5 Deque + Advanced Sliding Window Maximum (239), Shortest Subarray with Sum at Least K (862)

Stack for State Management

Use stack to save and restore state when processing nested or hierarchical structures.

ID Title Link Solution
636 Exclusive Time of Functions Link Solution
394 Decode String Link Solution 
// Example: Tracking function call stack
static void processLogs(String[] logs) {
    stack<int[]> st;  // new int[] {function_id, start_time}
    int[] result = new int[n];

    for(String log: logs) {
        // Parse log entry
        if(isStart) {
            st.offer(new int[] {id, time});
        } else {
            int[] funcIdpair = st.peek(); int funcId = funcIdpair[0]; int startTime = funcIdpair[1];
            st.poll();
            int duration = time - startTime + 1;
            result.put(funcId, result.getOrDefault(funcId, 0) + duration;

            // Subtract from parent if exists
            if(!st.isEmpty()) {
                result[st.peek().first] -= duration;
            }
        }
    }
}
ID Title Link Solution
636 Exclusive Time of Functions Link Solution
394 Decode String Link Solution

Stack Design (Min/Max Stack)

Maintaining extra information (like minimums or frequencies) alongside the primary stack data.

Min Stack — Parallel Main and Min Stacks push(5) main min 5 5 push(3) main min 3 5 3 5 push(7) main min 7 3 5 3 3 5 ↑ min(7, 3) = 3 → push 3 Each push records min(val, minStk.top()) — getMin() is always O(1)
ID Title Link Solution
155 Min Stack Link Solution
716 Max Stack Link - 
// import java.util.*;
class MinStack {
    Deque<Integer> stk, minStk;
    public void push(int val) {
        stk.offer(val);
        if (minStk.length == 0) minStk.offer(val);
        else minStk.offer(Math.min(minStk.peek(), val));
    }
    public void pop() { stk.poll(); minStk.poll(); }
        public int top() { return stk.peek(); }
        public int getMin() { return minStk.peek(); }
}
ID Title Link Solution
155 Min Stack Link Solution
716 Max Stack Link -

Key Patterns

  1. LIFO Property: Stack naturally handles reverse-order matching (parentheses, brackets)
  2. State Preservation: Save state before entering nested structures, restore after exiting
  3. Operator Precedence: Use stack to defer low-precedence operations
  4. Monotonic Order: Maintain sorted order to efficiently find extrema
  5. Index Tracking: Store indices instead of values when you need position information

When to Use Stack

  • ✅ Matching problems (parentheses, brackets, tags)
  • ✅ Expression evaluation with precedence
  • ✅ Nested structure processing
  • ✅ Finding next/previous greater/smaller elements
  • ✅ Reversing order or processing in reverse
  • ✅ Undo/redo functionality
  • ✅ Function call tracking

Common Mistakes

  1. Forgetting to check empty stack before st.top() or st.pop()
  2. Wrong stack order when pushing/popping multiple values
  3. Not resetting state after processing elements
  4. Index vs value confusion in monotonic stack problems

More templates