S026 · Stacks & Queues — LIFO/FIFO in Practice

"""stacks_queues.py — the interview canon for stacks + queues.
 
Run:  python stacks_queues.py
"""
from __future__ import annotations
from collections import deque
 
 
# ------------------------------------------------------------------
# 1) Valid Parentheses — the canonical stack problem
# ------------------------------------------------------------------
def valid_parentheses(s: str) -> bool:
    pairs = {")": "(", "]": "[", "}": "{"}
    stack: list[str] = []
    for ch in s:
        if ch in "([{":
            stack.append(ch)
        elif ch in ")]}":
            if not stack or stack.pop() != pairs[ch]:
                return False
    return not stack
 
 
# ------------------------------------------------------------------
# 2) MinStack — get_min in O(1) with an auxiliary stack
# ------------------------------------------------------------------
class MinStack:
    """Standard stack + get_min in O(1). Trick: keep a parallel stack of running minima."""
    def __init__(self) -> None:
        self._data: list[int] = []
        self._mins: list[int] = []
 
    def push(self, x: int) -> None:
        self._data.append(x)
        self._mins.append(x if not self._mins else min(x, self._mins[-1]))
 
    def pop(self) -> int:
        self._mins.pop()
        return self._data.pop()
 
    def top(self) -> int:
        return self._data[-1]
 
    def get_min(self) -> int:
        return self._mins[-1]
 
 
# ------------------------------------------------------------------
# 3) Next Greater Element — the monotonic-stack pattern
# ------------------------------------------------------------------
def next_greater(nums: list[int]) -> list[int]:
    """For each element, the next-to-the-right greater value, or -1 if none. O(n)."""
    n = len(nums)
    ans = [-1] * n
    stack: list[int] = []                # stack of INDICES with strictly decreasing values
    for i, x in enumerate(nums):
        while stack and nums[stack[-1]] < x:
            ans[stack.pop()] = x
        stack.append(i)
    return ans
 
 
# ------------------------------------------------------------------
# 4) Daily Temperatures — same monotonic-stack idea, different question
# ------------------------------------------------------------------
def daily_temperatures(temps: list[int]) -> list[int]:
    """For each day, days until a warmer temperature (0 if never). O(n)."""
    n = len(temps)
    ans = [0] * n
    stack: list[int] = []
    for i, t in enumerate(temps):
        while stack and temps[stack[-1]] < t:
            j = stack.pop()
            ans[j] = i - j
        stack.append(i)
    return ans
 
 
# ------------------------------------------------------------------
# 5) Implement a Queue with deque
# ------------------------------------------------------------------
class Queue:
    def __init__(self) -> None:
        self._d: deque = deque()
 
    def enqueue(self, x) -> None:
        self._d.append(x)
 
    def dequeue(self):
        return self._d.popleft()          # O(1) — the whole point of deque
 
    def peek(self):
        return self._d[0]
 
    def __len__(self) -> int:
        return len(self._d)
 
 
# ------------------------------------------------------------------
# 6) BFS on a graph — a queue in its natural habitat
# ------------------------------------------------------------------
def bfs_shortest_path(graph: dict[int, list[int]], start: int, goal: int) -> list[int] | None:
    """Return the shortest path (as a list of nodes) from start to goal, else None. O(V + E)."""
    if start == goal:
        return [start]
    seen = {start}
    parent: dict[int, int] = {start: -1}
    q: deque = deque([start])
    while q:
        node = q.popleft()
        for nbr in graph.get(node, []):
            if nbr in seen:
                continue
            seen.add(nbr)
            parent[nbr] = node
            if nbr == goal:
                # Reconstruct path by walking parents backwards
                path: list[int] = [nbr]
                while parent[path[-1]] != -1:
                    path.append(parent[path[-1]])
                path.reverse()
                return path
            q.append(nbr)
    return None
 
 
# ------------------------------------------------------------------
# 7) Perf demo — list.pop(0) vs deque.popleft
# ------------------------------------------------------------------
def perf_demo(n: int = 200_000) -> None:
    import time
 
    lst = list(range(n))
    t = time.perf_counter()
    while lst:
        lst.pop(0)
    print(f"list.pop(0)  n={n:>7} : {time.perf_counter()-t:.3f}s  (O(n^2))")
 
    dq = deque(range(n))
    t = time.perf_counter()
    while dq:
        dq.popleft()
    print(f"deque.popleft n={n:>7} : {time.perf_counter()-t:.3f}s  (O(n))")
 
 
if __name__ == "__main__":
    print("valid '(()[]{})':", valid_parentheses("(()[]{})"))
    print("valid '(]':      ", valid_parentheses("(]"))
 
    ms = MinStack()
    for v in [3, 5, 2, 6, 1, 4]:
        ms.push(v)
    print("MinStack get_min after pushes:", ms.get_min())    # 1
    ms.pop(); ms.pop()                                        # pop 4, 1
    print("MinStack get_min after pops:", ms.get_min())       # 2
 
    print("next_greater [2,1,2,4,3]:", next_greater([2, 1, 2, 4, 3]))
    print("daily_temperatures [73,74,75,71,69,72,76,73]:", daily_temperatures([73, 74, 75, 71, 69, 72, 76, 73]))
 
    graph = {1: [2, 3], 2: [4], 3: [4, 5], 4: [6], 5: [6], 6: []}
    print("BFS 1 -> 6:", bfs_shortest_path(graph, 1, 6))
 
    perf_demo()