Stack Pattern

The Stack pattern is a linear sequence storage mechanism operating on a Last-In, First-Out (LIFO) order, which is ideal for tracking nested scopes, verifying matching pairs, and tracking histories.

Recognition Signals

You should consider this pattern if you see any of the following cues in the problem description:

• The problem involves matching open and closed delimiters (brackets, HTML tags, quotes).
• You need to track the history of elements to backtrack to them (e.g. browser history, undo operations).
• You need to build a Monotonic Stack (storing elements in strictly increasing or decreasing order to find the next larger or smaller element).
• The task requires evaluating mathematical expressions or nested function calls.

How It Works

Instead of checking all pairs or nested combinations (which takes quadratic time), you push incoming elements onto a stack. When you encounter a closing or matching element, you pop from the top of the stack and verify the relationship.

For example, to verify if parentheses match:

1. Initialize an empty stack: [].
2. Input string: "()"
3. Read '(': push onto stack: ['('].
4. Read ')': pop from stack '('. They match.
5. End of string, stack is empty. Return true.

Complexity, With Caveats

• Time Complexity: O(1) time per push or pop operation. A complete scan of an array of size n takes O(n) total time.
• Space Complexity: O(n) auxiliary space. In the worst case (e.g. all open parentheses like "(((("), you must store every element in the stack before starting to pop.

Minimal Code Template

import java.util.Stack;

public class StackTemplate {
    // Matching Delimiters (Valid Parentheses)
    public boolean isValidParentheses(String s) {
        Stack<Character> stack = new Stack<>();
        for (char c : s.toCharArray()) {
            if (c == '(') {
                stack.push(')');
            } else if (c == '{') {
                stack.push('}');
            } else if (c == '[') {
                stack.push(']');
            } else {
                if (stack.isEmpty() || stack.pop() != c) {
                    return false;
                }
            }
        }
        return stack.isEmpty();
    }
}

# Matching Delimiters (Valid Parentheses)
def is_valid_parentheses(s: str) -> bool:
    stack = []
    mapping = {")": "(", "}": "{", "]": "["}

    for char in s:
        if char in mapping:
            # pop from stack if not empty, otherwise use placeholder
            top_element = stack.pop() if stack else "#"
            if mapping[char] != top_element:
                return False
        else:
            stack.append(char)

    return not stack

#include <string>
#include <stack>
#include <unordered_map>

class StackTemplate {
public:
    // Matching Delimiters (Valid Parentheses)
    bool isValidParentheses(std::string s) {
        std::stack<char> stack;
        for (char c : s) {
            if (c == '(') stack.push(')');
            else if (c == '{') stack.push('}');
            else if (c == '[') stack.push(']');
            else {
                if (stack.empty() || stack.top() != c) {
                    return false;
                }
                stack.pop();
            }
        }
        return stack.empty();
    }
};

Where This Pattern Falls Short

• Queue-like access: If you need to access elements in First-In, First-Out (FIFO) order (e.g. processing tasks in arrival sequence), a stack will reverse the order, which is incorrect. You must use a Queue instead.
• Random lookup: Stacks only expose the top element. If you need to inspect or modify elements in the middle of the collection, a stack is the wrong tool; you should use a List or Hash Table.

Related Patterns, Compared

• Queue: choose this instead when you need to process elements in the order they arrived, rather than processing the most recent element first.
• Monotonic Stack: choose this specialized sub-pattern when you need to find the next greater or smaller element in an array in linear time.

Frequently Asked Questions

Why is a stack used in recursion? Because the computer uses an internal call stack to track function execution states. When a function calls itself, the system pushes the current local state onto the call stack and starts the child call.

What is a Monotonic Stack? A monotonic stack is a stack that maintains its elements in sorted order. For example, in a decreasing monotonic stack, you pop elements that are smaller than the incoming element before pushing it.

What does this pattern test in interviews? It tests your ability to handle nested patterns, balance brackets, and manage history states efficiently.