Stack Applications

1. Introduction: The LIFO Engine

In the previous chapter, we learned that a Stack is a Last-In, First-Out (LIFO) data structure. While the operations are simple (push, pop, peek), the algorithmic applications are massive.

Stacks are fundamentally designed to solve Matching and Reversal problems. Whenever you have a nested structure (like math formulas, HTML tags, or function calls) where the most recently opened item must be the first one closed, you must use a Stack.

Furthermore, Stacks can be augmented to keep track of historical states, allowing you to instantly "time travel" back to previous conditions in $O(1)$ time.

2. Core Application 1: Matching Nested Structures

The most famous Stack problem in computer science is checking for Valid Parentheses.

Problem Statement: (LeetCode 20) Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid. Open brackets must be closed by the same type of brackets, and in the correct order.

The Insight: As we scan the string from left to right, we push open brackets onto a Stack. If we encounter a closing bracket, it MUST match the bracket at the very top of the Stack (the most recently opened one). If it matches, we pop the open bracket off the Stack and continue.

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

public class ValidParentheses {
    public boolean isValid(String s) {
        // Use ArrayDeque instead of legacy Stack
        Deque<Character> stack = new ArrayDeque<>();
        
        for (char c : s.toCharArray()) {
            // Push open brackets
            if (c == '(' || c == '{' || c == '[') {
                stack.push(c);
            } 
            // Handle closing brackets
            else {
                // If there's a closing bracket but no open brackets, invalid!
                if (stack.isEmpty()) return false;
                
                char top = stack.pop();
                
                // Check for mismatch
                if (c == ')' && top != '(') return false;
                if (c == '}' && top != '{') return false;
                if (c == ']' && top != '[') return false;
            }
        }
        
        // If the stack is not empty at the end, an open bracket was left unclosed!
        return stack.isEmpty();
    }
}

Complexity Analysis:

• Time Complexity: $O(N)$ to scan the string.
• Space Complexity: $O(N)$ if the string is entirely open brackets.

3. Core Application 2: Augmented Stacks (State Tracking)

Problem Statement: (LeetCode 155) Design a stack that supports push, pop, top, and retrieving the minimum element in constant time $O(1)$.

The Insight: If we push 5, then 2, then 8, the minimum is 2. If we pop the 8, the minimum is still 2. If we pop the 2, the minimum reverts to 5. To achieve $O(1)$ time travel, we don't just store the values in our Stack. We store a "snapshot" of what the minimum was at the exact moment that value was pushed!

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

public class MinStack {
    // We will store arrays of size 2: [actual_value, minimum_at_this_moment]
    private Deque<int[]> stack;

    public MinStack() {
        stack = new ArrayDeque<>();
    }
    
    public void push(int val) {
        if (stack.isEmpty()) {
            // First element is obviously the minimum
            stack.push(new int[]{val, val});
        } else {
            // Compare new value with the previous minimum snapshot
            int currentMin = stack.peek()[1];
            int newMin = Math.min(val, currentMin);
            stack.push(new int[]{val, newMin});
        }
    }
    
    public void pop() {
        stack.pop();
    }
    
    public int top() {
        return stack.peek()[0]; // Return the actual value
    }
    
    public int getMin() {
        return stack.peek()[1]; // Return the snapshot minimum
    }
}

4. Core Application 3: Postfix Evaluation

Computers struggle to evaluate human math formulas like (3 + 4) * 5 because of parentheses and order of operations (BODMAS/PEMDAS). Instead, compilers convert formulas into Reverse Polish Notation (RPN), which completely eliminates parentheses. (3 + 4) * 5 becomes 3 4 + 5 *.

Problem Statement: (LeetCode 150) Evaluate the value of an arithmetic expression in Reverse Polish Notation.

The Insight: RPN is evaluated strictly using a Stack. If you see a number, push it. If you see an operator (+, -, *, /), pop the top two numbers, apply the operator, and push the result back onto the stack!

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

public class EvaluateRPN {
    public int evalRPN(String[] tokens) {
        Deque<Integer> stack = new ArrayDeque<>();
        
        for (String token : tokens) {
            if (isOperator(token)) {
                // The FIRST number popped is the RIGHT operand!
                int right = stack.pop();
                int left = stack.pop();
                
                if (token.equals("+")) stack.push(left + right);
                else if (token.equals("-")) stack.push(left - right);
                else if (token.equals("*")) stack.push(left * right);
                else if (token.equals("/")) stack.push(left / right); // Integer division
            } else {
                // It's a number. Parse and push.
                stack.push(Integer.parseInt(token));
            }
        }
        
        // The final answer is the only number left on the stack
        return stack.pop();
    }
    
    private boolean isOperator(String s) {
        return s.equals("+") || s.equals("-") || s.equals("*") || s.equals("/");
    }
}

5. Common Mistakes Beginners Make

1. Popping in the wrong order for subtraction/division

   • The Mistake: int a = stack.pop(); int b = stack.pop(); stack.push(a - b);
   • Why it's wrong: In RPN, 3 4 - means 3 - 4. The 4 was pushed last, so it is popped FIRST. a is 4. b is 3. Your code calculates 4 - 3 = 1 instead of -1.
   • The Fix: Explicitly name them right (first pop) and left (second pop).

2. Crashing on EmptyStackException

   • The Mistake: Calling stack.pop() without checking !stack.isEmpty() in Valid Parentheses.
   • Why it's wrong: If the string starts with a closing bracket "]", the stack is empty. Calling pop() instantly crashes your program.

3. Using == to compare Strings in Java

   • The Mistake: if (token == "+")
   • Why it's wrong: Compares memory references, not string values.
   • The Fix: Always use token.equals("+").

6. Interview Q&A

Q1: How would you design a MaxStack? Answer: The exact same way as the MinStack! Just store Math.max(val, currentMax) in the snapshot array.

Q2: How do you parse standard string formulas (e.g., "3+4*5") into a Stack? Answer: (LeetCode 227 - Basic Calculator II). You don't need RPN. You keep a running number and the previous sign. When you hit a new sign, if the previous sign was +, you push the number. If -, push the negative number. If * or /, you pop() the top of the stack, perform the operation with the current number, and push the result! At the end, just sum everything in the stack.

7. Practice Problems

1. Valid Parentheses (LeetCode 20)
   • Goal: Flawless execution of pushing opens and popping/checking closes.
2. Min Stack (LeetCode 155)
   • Goal: Master the Augmented Stack (Snapshot) pattern.
3. Evaluate Reverse Polish Notation (LeetCode 150)
   • Goal: Master operand popping order.

8. Summary

• Matching: Stacks inherently solve problems where the last opened element must be the first closed element (Parentheses, HTML tags).
• Time Travel: To build a MinStack, don't just store the value. Store an Object or Array containing [Value, StateAtThatMoment].
• Parsing: Stacks act as holding pens for numbers until an operator triggers their evaluation.