Stack Applications

TL;DR

Stacks enable checking balanced parentheses by matching closing brackets with most recent opening. Expression evaluation converts infix to postfix using precedence rules. Monotonic stacks efficiently find next/previous greater/smaller elements in O(n) time. Histogram and trapping water problems use monotonic decreasing stacks. Understanding when stack properties (LIFO ordering) solve problems elegantly is crucial.

Core Concepts

Expression Evaluation

Infix notation: Standard mathematical notation (a + b). Requires operator precedence rules.

Postfix notation: Operands precede operators (a b +). No precedence needed; evaluate left-to-right.

Conversion (infix to postfix): Use stack for operators. When encountering operator, pop higher-precedence operators to output. O(n) time.

Postfix evaluation: Scan left-to-right. Push operands, pop two and apply operator on encountering operator. Final result is sole stack element.

Parentheses Matching

Valid parentheses: All opening brackets have matching closing brackets in correct order.

Algorithm: Push opening brackets, pop and verify match on closing brackets. Stack empty at end = valid.

Multiple types: Handle (), [], . Maintain mapping of opening to closing brackets.

Monotonic Stack

Monotonic increasing stack: Stack maintains elements in increasing order. When new element smaller, pop until insertion point found.

Monotonic decreasing stack: Stack maintains elements in decreasing order. When new element larger, pop until insertion point found.

Next greater element: For each element, find nearest greater element to right using decreasing monotonic stack. O(n) vs O(n²) brute force.

Key insight: Each element pushed and popped once, giving O(n) total despite nested loops.

Next/Previous Greater/Smaller

Next greater: While traversing right, pop smaller elements from decreasing stack. Current element is next greater for popped elements.

Previous greater: Traverse left-to-right, pop smaller elements from increasing stack. Top of stack is previous greater.

Histogram Problems

Largest rectangle: For each bar, find leftmost and rightmost bars >= current height. Area = height * width. Use monotonic stack for O(n) vs O(n²).

Trapping water: For each position, water level = min(max_left, max_right). Water trapped = water_level - bar_height. Two-pass or stack approach.

Key Algorithms

Valid Parentheses Checker

Push opening, pop and verify closing. O(n) time, O(n) space.

Infix to Postfix Converter

Operator precedence handled by stack. O(n) time, O(n) space.

Next Greater Element Finder

Monotonic decreasing stack. O(n) time, O(n) space.

Largest Rectangle in Histogram

Monotonic increasing stack of indices. O(n) time, O(n) space.

Practical Example

Python

# Valid parentheses
def is_valid_parentheses(s):
    stack = []
    pairs = {'(': ')', '[': ']', '{': '}'}
    for char in s:
        if char in pairs:
            stack.append(char)
        else:
            if not stack or pairs[stack.pop()] != char:
                return False
    return not stack

# Next greater element
def next_greater_element(nums):
    result = [-1] * len(nums)
    stack = []
    for i in range(len(nums) - 1, -1, -1):
        while stack and stack[-1] <= nums[i]:
            stack.pop()
        if stack:
            result[i] = stack[-1]
        stack.append(nums[i])
    return result

# Largest rectangle in histogram
def largest_rectangle(heights):
    stack = []
    max_area = 0
    for i, h in enumerate(heights):
        start = i
        while stack and stack[-1][1] > h:
            index, height = stack.pop()
            area = height * (i - index)
            max_area = max(max_area, area)
            start = index
        if h > 0:
            stack.append((start, h))
    for index, height in stack:
        area = height * (len(heights) - index)
        max_area = max(max_area, area)
    return max_area

# Trapping rain water
def trap_water(heights):
    if not heights:
        return 0
    left_max = [0] * len(heights)
    right_max = [0] * len(heights)
    left_max[0] = heights[0]
    for i in range(1, len(heights)):
        left_max[i] = max(left_max[i-1], heights[i])
    right_max[-1] = heights[-1]
    for i in range(len(heights) - 2, -1, -1):
        right_max[i] = max(right_max[i+1], heights[i])
    water = 0
    for i in range(len(heights)):
        water += min(left_max[i], right_max[i]) - heights[i]
    return water

# Test
print(is_valid_parentheses("()[]{}"))  # True
print(next_greater_element([1, 2, 1]))  # [2, -1, -1]
print(largest_rectangle([2, 1, 5, 6, 2, 3]))  # 10
print(trap_water([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]))  # 6

Java

import java.util.*;

public class StackApplications {
    static boolean isValidParentheses(String s) {
        Stack<Character> stack = new Stack<>();
        Map<Character, Character> pairs = new HashMap<>();
        pairs.put('(', ')');
        pairs.put('[', ']');
        pairs.put('{', '}');

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

    static int[] nextGreaterElement(int[] nums) {
        int[] result = new int[nums.length];
        Arrays.fill(result, -1);
        Stack<Integer> stack = new Stack<>();
        for (int i = nums.length - 1; i >= 0; i--) {
            while (!stack.isEmpty() && stack.peek() <= nums[i]) {
                stack.pop();
            }
            if (!stack.isEmpty()) {
                result[i] = stack.peek();
            }
            stack.push(nums[i]);
        }
        return result;
    }

    public static void main(String[] args) {
        System.out.println(isValidParentheses("()[]{}"));
        System.out.println(Arrays.toString(nextGreaterElement(new int[]{1, 2, 1})));
    }
}

Common Pitfalls

warning

Forgetting to check stack empty: Popping from empty stack causes exceptions. Always check before popping.

Incorrect operator precedence: Operator precedence must match mathematical rules. Verify precedence handling in conversion algorithms.

Monotonic stack direction confusion: Increasing vs decreasing matters. Mixing them reverses results.

Not handling edge cases: Empty input, single element, all same elements can break algorithms.

Off-by-one in histogram: Width calculation needs careful indexing. Use index of popped element vs current element.

Advanced Applications

Compiler Expression Parsing

Stacks are fundamental in compiler design for parsing and evaluating expressions with precedence:

def evaluate_expression(expression: str) -> float:
    """Evaluate mathematical expression with full operator precedence."""
    precedence = {'+': 1, '-': 1, '*': 2, '/': 2, '^': 3}

    def infix_to_postfix(infix: str) -> str:
        """Convert infix to postfix notation."""
        postfix = []
        op_stack = []

        tokens = infix.split()
        for token in tokens:
            if token.isdigit():
                postfix.append(token)
            elif token in precedence:
                while (op_stack and op_stack[-1] != '(' and
                       op_stack[-1] in precedence and
                       precedence[op_stack[-1]] >= precedence[token]):
                    postfix.append(op_stack.pop())
                op_stack.append(token)
            elif token == '(':
                op_stack.append(token)
            elif token == ')':
                while op_stack and op_stack[-1] != '(':
                    postfix.append(op_stack.pop())
                op_stack.pop()

        while op_stack:
            postfix.append(op_stack.pop())
        return ' '.join(postfix)

    def evaluate_postfix(postfix: str) -> float:
        """Evaluate postfix expression."""
        stack = []
        for token in postfix.split():
            if token.isdigit():
                stack.append(float(token))
            else:
                b = stack.pop()
                a = stack.pop()
                if token == '+': stack.append(a + b)
                elif token == '-': stack.append(a - b)
                elif token == '*': stack.append(a * b)
                elif token == '/': stack.append(a / b)
                elif token == '^': stack.append(a ** b)
        return stack[0]

    postfix = infix_to_postfix(expression)
    return evaluate_postfix(postfix)

# Test
result = evaluate_expression("3 + 4 * 2 / ( 1 - 5 ) ^ 2")
print(result)  # Respects operator precedence correctly

Daily Temperatures Problem

Find the next day with warmer temperature using monotonic stack:

def daily_temperatures(temperatures):
    """For each day, find days until warmer temperature."""
    n = len(temperatures)
    result = [0] * n
    stack = []  # Stack of (temperature, index)

    for i, temp in enumerate(temperatures):
        while stack and stack[-1][0] < temp:
            prev_temp, prev_index = stack.pop()
            result[prev_index] = i - prev_index
        stack.append((temp, i))

    return result

# Test
temps = [73, 74, 75, 71, 69, 72, 76, 73]
print(daily_temperatures(temps))  # [1, 1, 4, 2, 1, 1, 0, 0]

Removing K Digits

Remove k digits to form smallest number using monotonic stack:

def remove_k_digits(num_str: str, k: int) -> str:
    """Remove k digits to get smallest number."""
    if k >= len(num_str):
        return "0"

    stack = []
    to_remove = k

    for digit in num_str:
        while stack and to_remove and stack[-1] > digit:
            stack.pop()
            to_remove -= 1
        stack.append(digit)

    # Remove remaining digits from end if needed
    stack = stack[:len(stack) - to_remove]

    result = ''.join(stack).lstrip('0')
    return result if result else "0"

# Test
print(remove_k_digits("1432219", 3))  # "1219"
print(remove_k_digits("10200", 1))     # "200"

Complex Examples: Sliding Window Maximum

Find maximum in each sliding window using monotonic decreasing stack:

def sliding_window_maximum(nums, k):
    """Find max in each sliding window of size k."""
    if not nums or k == 0:
        return []

    result = []
    dq = collections.deque()  # Stores indices of useful elements

    for i, num in enumerate(nums):
        # Remove indices outside current window
        while dq and dq[0] < i - k + 1:
            dq.popleft()

        # Remove smaller elements (they can't be max while current is in queue)
        while dq and nums[dq[-1]] < num:
            dq.pop()

        dq.append(i)

        # First valid window is at index k-1
        if i >= k - 1:
            result.append(nums[dq[0]])

    return result

# Test
print(sliding_window_maximum([1, 3, -1, -3, 5, 3, 6, 7], 3))
# [3, 3, 5, 5, 6, 7]

Performance Analysis Deep Dive

For various stack applications:

Problem	Brute Force	Stack Solution	Complexity
Next Greater Element	Nested loops	Monotonic stack	O(n²) → O(n)
Trapping Water	Multiple passes	One pass with stack	O(n) same, cleaner
Largest Rectangle	Check all rectangles	Monotonic stack	O(n²) → O(n)
Validate Parentheses	Recursion	Stack	O(n) same, iterative

Self-Check

1. Explain why monotonic stack solves next greater element in O(n) vs O(n²) brute force. Each element is pushed/popped exactly once despite nested loops.
2. How does infix-to-postfix conversion handle operator precedence with stacks? Higher precedence operators are popped first based on comparison in the algorithm.
3. Why does trapping water require knowing both left and right maximums? Water level at position i is min(max_left, max_right); volume is (min_level - height[i]).
4. How are monotonic stacks different from regular stacks? They maintain an invariant (increasing or decreasing) by selective popping, enabling efficient algorithms.

One Takeaway

info

Stacks enable elegant solutions for problems requiring matching, ordering, or range queries. Monotonic stacks particularly solve next/previous greater/smaller and histogram problems efficiently. Master stack properties: LIFO ordering, constant push/pop, and how to maintain stack invariants like monotonicity. Understanding when to apply monotonic stacks separates good engineers from great ones.

References

• Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.