Stacks

def multiply(a, b):
    return a * b

def square(n):
    return multiply(n, n)

def sum_of_squares(x, y):
    return square(x) + square(y)

result = sum_of_squares(3, 4)  # → 25

class Stack:
    def __init__(self):
        self._data = []  # Python list handles resizing for us

    def push(self, val):
        self._data.append(val)  # O(1) amortized

    def pop(self):
        if self.is_empty():
            raise IndexError("pop from empty stack")
        return self._data.pop()  # O(1) — removes last element

    def peek(self):
        if self.is_empty():
            raise IndexError("peek at empty stack")
        return self._data[-1]  # O(1) — just look, don't remove

    def is_empty(self):
        return len(self._data) == 0

    def __len__(self):
        return len(self._data)

    def __repr__(self):
        # Show top of stack on the right for clarity
        return f"Stack({self._data})"


# Example: balanced parentheses checker
def is_balanced(s):
    """Check if brackets in string are properly nested."""
    stack = Stack()
    # Map each closer to its opener — lets us handle all three
    # bracket types in one pass without separate if/elif chains
    pairs = {')': '(', ']': '[', '}': '{'}

    for char in s:
        if char in '([{':
            stack.push(char)
        elif char in ')]}':
            # Two failure modes: nothing to match, or wrong match
            if stack.is_empty() or stack.pop() != pairs[char]:
                return False
    # If anything's left, we have unclosed openers
    return stack.is_empty()


# Usage
print(is_balanced("({[]})"))    # True
print(is_balanced("([)]"))      # False — interleaved
print(is_balanced("(("))        # False — unclosed

class Stack {
  constructor() {
    this._data = [];
  }

  push(val) {
    this._data.push(val);
  }

  pop() {
    if (this.isEmpty()) throw new Error("Stack underflow");
    return this._data.pop();
  }

  peek() {
    if (this.isEmpty()) throw new Error("Stack is empty");
    return this._data[this._data.length - 1];
  }

  isEmpty() {
    return this._data.length === 0;
  }

  get size() {
    return this._data.length;
  }
}

// Example: evaluate postfix expression (Reverse Polish Notation)
// "3 4 + 2 *" means (3 + 4) * 2 = 14
function evalPostfix(expr) {
  const stack = new Stack();
  const tokens = expr.split(" ");

  for (const token of tokens) {
    if ("+-*/".includes(token)) {
      // Pop two operands — note the order matters for - and /
      const b = stack.pop();  // second operand was pushed last
      const a = stack.pop();  // first operand was pushed first
      switch (token) {
        case "+": stack.push(a + b); break;
        case "-": stack.push(a - b); break;
        case "*": stack.push(a * b); break;
        case "/": stack.push(Math.trunc(a / b)); break;
      }
    } else {
      stack.push(Number(token));
    }
  }
  return stack.pop();
}

console.log(evalPostfix("3 4 + 2 *")); // 14
console.log(evalPostfix("5 1 2 + 4 * + 3 -")); // 14

class MinStack:
    """Stack that supports getMin() in O(1) time.
    
    The trick: maintain a parallel stack that tracks the minimum
    value at each "level" of the main stack. When we push a value
    that's <= the current minimum, we push it onto the min stack too.
    When we pop a value equal to the current minimum, we pop from
    the min stack as well.
    """

    def __init__(self):
        self._data = []
        self._mins = []  # Parallel stack tracking the minimum at each level

    def push(self, val):
        self._data.append(val)
        # If this value is <= current min, push it onto mins too
        # Using <= (not <) handles duplicate minimums correctly
        if not self._mins or val <= self._mins[-1]:
            self._mins.append(val)

    def pop(self):
        val = self._data.pop()
        # If we're popping the current minimum, pop from mins too
        if val == self._mins[-1]:
            self._mins.pop()
        return val

    def top(self):
        return self._data[-1]

    def get_min(self):
        return self._mins[-1]  # O(1) — always the current minimum

def next_greater_element(nums):
    """For each element, find the next element that is larger.
    
    Uses a monotonic decreasing stack (from bottom to top).
    When we encounter a number larger than the stack's top,
    that number is the "next greater" for everything smaller
    on the stack.
    
    Example: [4, 2, 1, 5, 3] → [5, 5, 5, -1, -1]
    
    Time: O(n) — each element is pushed and popped at most once
    Space: O(n) — for the stack and result array
    """
    n = len(nums)
    result = [-1] * n
    stack = []  # stores indices, not values

    for i in range(n):
        # Pop all elements smaller than current — current is their answer
        while stack and nums[stack[-1]] < nums[i]:
            idx = stack.pop()
            result[idx] = nums[i]
        stack.append(i)

    return result

# Example: Daily Temperatures (LC #739)
# Given temperatures, find how many days until a warmer day
def daily_temperatures(temps):
    """Same monotonic stack idea, but return days-to-wait."""
    n = len(temps)
    answer = [0] * n
    stack = []

    for i in range(n):
        while stack and temps[stack[-1]] < temps[i]:
            idx = stack.pop()
            answer[idx] = i - idx  # days between
        stack.append(i)

    return answer

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

class UndoRedoEditor:
    """Simple text editor with undo/redo support.
    
    Two stacks:
    - undo_stack: holds previous states (push on every edit)
    - redo_stack: holds states you've undone (push on undo)
    
    Key rule: any new edit clears the redo stack.
    Why? Once you edit after undoing, the "future" you undid
    is no longer valid.
    """
    def __init__(self):
        self.content = ""
        self.undo_stack = []
        self.redo_stack = []

    def type_text(self, text):
        """Add text at the end."""
        self.undo_stack.append(self.content)  # Save current state
        self.redo_stack.clear()                # New edit kills redo
        self.content += text

    def delete_last(self, n):
        """Delete last n characters."""
        self.undo_stack.append(self.content)
        self.redo_stack.clear()
        self.content = self.content[:-n] if n < len(self.content) else ""

    def undo(self):
        """Revert to previous state."""
        if not self.undo_stack:
            return  # Nothing to undo
        self.redo_stack.append(self.content)  # Save current for redo
        self.content = self.undo_stack.pop()   # Restore previous

    def redo(self):
        """Re-apply the last undone action."""
        if not self.redo_stack:
            return  # Nothing to redo
        self.undo_stack.append(self.content)
        self.content = self.redo_stack.pop()


# Demo
editor = UndoRedoEditor()
editor.type_text("Hello")
editor.type_text(" World")
print(editor.content)   # "Hello World"

editor.undo()
print(editor.content)   # "Hello"

editor.undo()
print(editor.content)   # ""

editor.redo()
print(editor.content)   # "Hello"

editor.type_text("!")
print(editor.content)   # "Hello!"
# redo_stack is now empty — the " World" future is gone