Stack

1. Core Operations

All stack operations occur at one end, known as the "top" of the stack. They are all highly efficient.

• Push: Adds a new element to the top of the stack. (O(1))
• Pop: Removes the top element from the stack. (O(1))
• Peek (or Top): Looks at the top element without removing it. (O(1))

2. Common Applications

• Function Call Management: This is the "call stack" that manages active function calls in a program. When a function is called, a frame is pushed; when it returns, the frame is popped.
• Undo/Redo Functionality: Stacks can store states or commands, allowing a user to easily revert to a previous state.
• Syntax Parsing and Expression Evaluation: Stacks are key for parsing expressions, like converting from infix to postfix notation, or evaluating a postfix expression.
• Backtracking Algorithms: While often implemented with recursion (which uses the call stack), an explicit stack can be used for iterative versions of Depth-First Search (DFS) or other backtracking problems.

3. Monotonic Stack

A monotonic stack is a powerful pattern where the elements in the stack are always in a sorted order (either increasing or decreasing). It's used to solve problems that involve finding the "next greater element" or "previous smaller element" for all elements in an array, typically in O(n) time.

Example: Next Greater Element. To find the next greater element for each number, you iterate through the array. For each element, you pop from the stack as long as the current element is greater than the element at the top of the stack. The popped element's "next greater element" is the current element. Then, you push the current element onto the stack.

4. Classic Problems

Valid Parentheses

This is the quintessential stack problem. Iterate through the string. If you see an opening bracket ('(', '{', '['), push it onto the stack. If you see a closing bracket, check if the stack is empty or if the top of the stack is not the matching opening bracket. If either is true, the string is invalid. At the end, an empty stack means the string was valid.

class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        close_to_open = {")": "(", "}": "{", "]": "["}
        
        for char in s:
            if char in close_to_open:
                if stack and stack[-1] == close_to_open[char]:
                    stack.pop()
                else:
                    return False
            else:
                stack.append(char)
                    
        return not stack

Min Stack

A design problem where you must create a stack that supports `push`, `pop`, `top`, and retrieving the minimum element in constant time. The common solution is to use a second stack (the "min stack") that stores the minimum element seen so far at each stage.

class MinStack:
    def __init__(self):
        self.stack = []
        self.min_stack = []

    def push(self, val: int) -> None:
        self.stack.append(val)
        val = min(val, self.min_stack[-1] if self.min_stack else val)
        self.min_stack.append(val)

    def pop(self) -> None:
        self.stack.pop()
        self.min_stack.pop()

    def top(self) -> int:
        return self.stack[-1]

    def getMin(self) -> int:
        return self.min_stack[-1]

Evaluate Reverse Polish Notation (RPN)

RPN is a mathematical notation in which every operator follows all of its operands. It's perfectly suited for a stack. Iterate through the tokens. If a token is a number, push it onto the stack. If it's an operator, pop the top two numbers, perform the operation, and push the result back onto the stack.

from typing import List

class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        stack = []
        for c in tokens:
            if c == "+":
                stack.append(stack.pop() + stack.pop())
            elif c == "-":
                a, b = stack.pop(), stack.pop()
                stack.append(b - a)
            elif c == "*":
                stack.append(stack.pop() * stack.pop())
            elif c == "/":
                a, b = stack.pop(), stack.pop()
                stack.append(int(b / a))
            else:
                stack.append(int(c))
        return stack[0]

Largest Rectangle in Histogram

A classic hard problem that uses a monotonic (increasing) stack. Iterate through the heights. When you encounter a height that is less than the height at the top of the stack, you know you've found the right boundary for the bar at the top. You can then pop from the stack, calculate the area for that bar, and update the max area. The stack stores indices, not heights.

from typing import List

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        maxArea = 0
        stack = [] # pair: (index, height)

        for i, h in enumerate(heights):
            start = i
            while stack and stack[-1][1] > h:
                index, height = stack.pop()
                maxArea = max(maxArea, height * (i - index))
                start = index
            stack.append((start, h))

        for i, h in stack:
            maxArea = max(maxArea, h * (len(heights) - i))
        
        return maxArea