5. Stacks & Queues

Stack — Last In, First Out (LIFO)

Analogy: A stack of plates. You always add and remove from the top.

Real-world uses:

• Undo/redo in text editors (each action pushed onto a stack)
• Browser back button (visited pages pushed; pop on back)
• Function call stack (Python's own execution model)
• Syntax validation (matching parentheses, HTML tags)

# Python list as a stack — use only append() and pop()
stack = []
stack.append("page1")    # push
stack.append("page2")
stack.append("page3")
print(stack[-1])          # peek — O(1)
stack.pop()               # pop → "page3"
print(stack)              # ["page1", "page2"]

# --- Validate balanced brackets ---
def is_balanced(s: str) -> bool:
    """
    Check if brackets are properly nested and closed.
    e.g. "({[]})" → True
         "([)]"   → False
    """
    stack = []
    matching = {')': '(', '}': '{', ']': '['}
    for ch in s:
        if ch in '({[':
            stack.append(ch)
        elif ch in ')}]':
            if not stack or stack[-1] != matching[ch]:
                return False
            stack.pop()
    return len(stack) == 0

print(is_balanced("({[]})"))  # True
print(is_balanced("({[)]}"))  # False

# --- Simple undo system ---
class TextEditor:
    def __init__(self):
        self.text  = ""
        self._history: list[str] = []

    def type(self, text: str) -> None:
        self._history.append(self.text)   # save current state
        self.text += text

    def undo(self) -> None:
        if self._history:
            self.text = self._history.pop()   # restore previous state

editor = TextEditor()
editor.type("Hello")
editor.type(", World")
print(editor.text)    # "Hello, World"
editor.undo()
print(editor.text)    # "Hello"

---

Queue — First In, First Out (FIFO)

Analogy: A line at a checkout counter. First person in line is first to be served.

Real-world uses:

• Job/task queues (background workers process tasks in order)
• Print queues (documents printed in submission order)
• BFS graph traversal (explore nodes level by level)
• Rate limiting (process N requests per second)

from collections import deque

# Always use deque for queues — list.pop(0) is O(n), deque.popleft() is O(1)
queue: deque = deque()
queue.append("task_1")      # enqueue — O(1)
queue.append("task_2")
queue.append("task_3")
task = queue.popleft()       # dequeue → "task_1"   O(1)
print(task, queue)

# --- Simple task processor ---
class TaskQueue:
    def __init__(self):
        self._queue: deque[str] = deque()

    def add_task(self, task: str) -> None:
        self._queue.append(task)
        print(f"Queued: {task}")

    def process_next(self) -> str | None:
        if not self._queue:
            print("No tasks.")
            return None
        task = self._queue.popleft()
        print(f"Processing: {task}")
        return task

q = TaskQueue()
q.add_task("send_email")
q.add_task("resize_image")
q.add_task("send_report")
q.process_next()   # send_email
q.process_next()   # resize_image

---

Monotonic Stack (Intermediate Pattern)

A stack that maintains elements in either strictly increasing or strictly decreasing order. Used to find the nearest greater/smaller element in $O(n)$.

# --- Next warmer day (Daily Temperatures) ---
# For each day, how many days until a warmer temperature?
def daily_temperatures(temps: list[int]) -> list[int]:
    result = [0] * len(temps)
    stack  = []   # stores indices of days waiting for a warmer day

    for today, temp in enumerate(temps):
        # Pop all days that are colder than today — today is their answer
        while stack and temps[stack[-1]] < temp:
            cold_day = stack.pop()
            result[cold_day] = today - cold_day
        stack.append(today)

    return result   # days where stack still has items → no warmer day found (remain 0)

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

---