Coding Patterns - Mastering Stacks

Intuition

A stack is a linear data structure that follows the Last In, First Out (LIFO) principle. The most recently added element is the first one to be removed. Stacks are particularly useful for problems involving reversals, balanced structures, and tracking previous states.

Think of a stack as a stack of plates: you add a new plate on top, and when you remove one, you take the top plate first.

Stack Strategies

1. Balanced Parentheses and Brackets

• Push opening brackets onto the stack.

• Pop when encountering closing brackets.

• Validate proper nesting.

2. Expression Evaluation

• Convert infix to postfix or evaluate postfix expressions using a stack.

3. Monotonic Stack

• Maintain increasing or decreasing order in the stack.

• Useful for problems like “Next Greater Element” or “Largest Rectangle in Histogram.”

4. Undo Mechanisms

• Store previous states to backtrack easily.

When To Use Stacks

Use stacks when:

• The problem requires backtracking or undoing operations.

• You need to evaluate or parse expressions.

• You’re working with nested structures like parentheses or tags.

• You need efficient nearest greater/smaller element queries.

Real-World Example

Text Editors (Undo Feature): Each operation is pushed onto a stack. When “undo” is pressed, the most recent operation is popped and reversed.

Web Browsers (Navigation History): The back button uses a stack to store previously visited pages.

Coding Example 1: Valid Parentheses

def is_valid_parentheses(s):
    stack = []
    mapping = {')': '(', ']': '[', '}': '{'}

    for char in s:
        if char in mapping.values():
            stack.append(char)
        elif char in mapping:
            if not stack or stack[-1] != mapping[char]:
                return False
            stack.pop()
    return not stack

# Example usage
print(is_valid_parentheses("()[]{}"))  # True
print(is_valid_parentheses("(]"))      # False

Coding Example 2: Next Greater Element

def next_greater(nums):
    res = [-1] * len(nums)
    stack = []  # stores indices

    for i in range(len(nums)):
        while stack and nums[i] > nums[stack[-1]]:
            idx = stack.pop()
            res[idx] = nums[i]
        stack.append(i)

    return res

# Example usage
print(next_greater([2, 1, 2, 4, 3]))  # [4, 2, 4, -1, -1]

Framework

1. Identify LIFO Behavior: Check if the problem requires last-seen-first-used logic.

2. Choose Stack Representation: Use list (Python) or explicit Stack class.

3. Push/Pop Elements: Based on problem constraints (open/close symbols, order tracking).

4. Apply Variations: Balanced checks, monotonic stacks, or history tracking.

5. Return Result: Based on processed state of the stack.

Key Points

• Stacks operate on the LIFO principle.

• Common problems: parentheses validation, expression evaluation, monotonic stack.

• Real-world applications: undo functionality, browser history.

• Powerful for sequence and backtracking problems.

Practice Exercise

Exercise: Implement a function to evaluate a postfix expression using a stack.

Sample Solution:

def evaluate_postfix(expression):
    stack = []
    for token in expression.split():
        if token.isdigit():
            stack.append(int(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(int(a / b))  # integer division
    return stack[0]

# Example usage
expr = "2 1 + 3 *"  # (2 + 1) * 3
print(evaluate_postfix(expr))  # 9