DSA Patterns: Stack

The Stack pattern is a go-to tool when you're dealing with nested structures, reverse-order processing, or problems that need memory of what came before.

It’s not just a data structure — it’s a mindset. And the more problems you solve with it, the more intuitive it becomes.

---

📌 When to Use the Stack Pattern

Reach for a stack when:

• You're dealing with balanced expressions (like parentheses or HTML tags)
• The problem asks for next greater/smaller element
• You need to track order of things (especially in reverse)
• You’re simulating undo/redo, function calls, or evaluation logic

---

🌍 Real-World Use Cases

To internalize the power of a stack, just look around:

• Undo/Redo in editors → Each action is pushed/popped
• Browser history → Last visited page is the first to go back to
• Call stack in programming → Tracks recursive function calls
• Expression evaluators → Stack is used to evaluate math like ["2", "1", "+", "3", "*"]
• Maze/DFS traversal → Paths are pushed as you go deeper, popped to backtrack

---

🧠 Core Idea

Stacks are LIFO — Last In, First Out.

At every point, the top of the stack is the most recent item you're still waiting to resolve.

When that condition is satisfied, you pop it and move on.

---

🧪 Problem 1: Valid Parentheses

Leetcode 20 - Valid Parentheses
👉 https://leetcode.com/problems/valid-parentheses/

🧩 The Problem

Given a string containing only '(', ')', '{', '}', '[', ']', determine if the input is valid (i.e., well-formed and properly nested).

🚫 Brute Force

Try matching pairs manually, but this falls apart with nesting and multiple types.

✅ Why Stack Works

• Push opening brackets
• On closing, pop and validate the top
• If anything’s unmatched or out of order → invalid

✅ Code

public boolean isValid(String s) {
    Stack<Character> stack = new Stack<>();
    for (char c : s.toCharArray()) {
        if (c == '(' || c == '{' || c == '[') {
            stack.push(c);
        } else {
            if (stack.isEmpty()) return false;
            char top = stack.pop();
            if ((c == ')' && top != '(') ||
                (c == '}' && top != '{') ||
                (c == ']' && top != '[')) {
                return false;
            }
        }
    }
    return stack.isEmpty();
}

🧪 Dry Run

Input: "({[]})"
Stack evolves:
( → { → [ → pop ] → pop } → pop ) → stack empty → ✅

💡 Takeaway

When things open and close in reverse order, Stack is the cleanest solution.

---

🧪 Problem 2: Daily Temperatures

Leetcode 739 - Daily Temperatures
👉 https://leetcode.com/problems/daily-temperatures/

🧩 The Problem

Given a list of temperatures, return a list where res[i] is the number of days to wait until a warmer temperature.

Return 0 if there is no such future day.

🚫 Brute Force

Check each future day for every temperature → O(n²) time.

✅ Why Stack Works

You track indices of unresolved days in a monotonic decreasing stack.
When a warmer day comes, resolve all colder days still on top.

✅ Code

public int[] dailyTemperatures(int[] temps) {
    int n = temps.length;
    int[] res = new int[n];
    Stack<Integer> stack = new Stack<>(); // store indices

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

    return res;
}

🧪 Dry Run

Input: [73, 74, 75, 71, 69, 72, 76, 73]

- i = 0, temp = 73 → push → stack = [0], res = [0, 0, 0, 0, 0, 0, 0, 0]
No previous temp to compare. Push index 0 to wait for a warmer day.

- i = 1, temp = 74 → pop 0 → res[0] = 1 → push → stack = [1], res = [1, 0, 0, 0, 0, 0, 0, 0]
74 > 73 → pop index 0, set res[0] = 1 (1 day wait). Push 1 to wait for warmer day than 74.

- i = 2, temp = 75 → pop 1 → res[1] = 1 → push → stack = [2], res = [1, 1, 0, 0, 0, 0, 0, 0]
75 > 74 → pop index 1, set res[1] = 1. Push 2 to wait for warmer day than 75.

- i = 3, temp = 71 → push → stack = [2, 3], res = [1, 1, 0, 0, 0, 0, 0, 0]
71 < 75 → can't resolve anything, push 3 and wait.

- i = 4, temp = 69 → push → stack = [2, 3, 4], res = [1, 1, 0, 0, 0, 0, 0, 0]
69 < 71 → still colder than all above, push 4 and wait.

- i = 5, temp = 72 → pop 4 → res[4] = 1 → pop 3 → res[3] = 2 → push → stack = [2, 5], res = [1, 1, 0, 2, 1, 0, 0, 0]
72 > 69 → res[4] = 5 - 4 = 1.  
Then 72 > 71 → res[3] = 5 - 3 = 2. Push 5 to wait for warmer than 72.

- i = 6, temp = 76 → pop 5 → res[5] = 1 → pop 2 → res[2] = 4 → push → stack = [6], res = [1, 1, 4, 2, 1, 1, 0, 0]
76 > 72 → res[5] = 6 - 5 = 1.  
Then 76 > 75 → res[2] = 6 - 2 = 4. Push 6 to wait for warmer than 76.

- i = 7, temp = 73 → push → stack = [6, 7], res = [1, 1, 4, 2, 1, 1, 0, 0]
73 < 76 → can't resolve anything. Push 7 to wait.

✅ Final res: [1, 1, 4, 2, 1, 1, 0, 0]

💡 Takeaway

When you’re waiting for a condition (like a warmer day) and want to resolve earlier values — stack gives you the right order.

---

📚 Coding Templates

✅ Balanced Brackets

for (char c : input) {
    if (opening) stack.push(c);
    else {
        if (stack is empty OR top doesn’t match) → invalid
        else stack.pop();
    }
}

---

✅ Monotonic Stack (Next Greater Element)

for (i from n-1 to 0) {
    while (!stack.empty() && stack.peek() <= nums[i])
        stack.pop();
    result[i] = stack.empty() ? -1 : stack.peek();
    stack.push(nums[i]);
}

---

✅ Postfix Expression Evaluation

for (token in input) {
    if (operator) → pop two, compute, push result
    else → parse and push number
}

---

🎯 Sample Problems to Internalize Stack

---

🧭 Final Thoughts

The Stack pattern is powerful because it allows you to:

• Remember unresolved work
• Resolve things in reverse order
• Handle nested logic cleanly

Once you start solving problems this way, stack-based solutions will feel like second nature.