Stacks & Queues

#Topic: Stack Basics -- push, pop, peek, underflow, DFS Simulation
# Time  : push O(1), pop O(1), peek O(1)
#Space: O(n) -- Number of elements stored in the stack

from __future__ import annotations


class Stack:
    """Implementation of a list-based stack."""

    def __init__(self) -> None:
        self._data: list[int] = []

    def push(self, val: int) -> None:
        """Add an element to the top of the stack -- O(1) constant time."""
        self._data.append(val)

    def pop(self) -> int:
        """Remove and return the top element of the stack -- O(1).

        Raises:
            IndexError: When the stack is empty."""
        if self.is_empty():
            raise IndexError("Stack Underflow: Attempt to pop from an empty stack")
        return self._data.pop()

    def peek(self) -> int:
        """Returns the top element without removal -- O(1)."""
        if self.is_empty():
            raise IndexError("The stack is empty")
        return self._data[-1]

    def is_empty(self) -> bool:
        """Returns True if the stack is empty -- O(1)."""
        return len(self._data) == 0

    def size(self) -> int:
        """Returns the number of elements in the stack -- O(1)."""
        return len(self._data)

    def __repr__(self) -> str:
        return f"Stack(bottom->top): {self._data}"


def demo_basic_operations() -> None:
    """Stack basic operation demo."""
    print("=" * 50)
    print("Basic stack operations")
    print("=" * 50)

    s = Stack()
    for val in [1, 3, 5, 7, 9]:
        s.push(val)
        print(f"push({val:2}) -> {s}")

    print()
    while not s.is_empty():
        val = s.pop()
        print(f"pop() -> {val:2}  {s}")

    #Underflow Handling
    print()
    try:
        s.pop()
    except IndexError as e:
        print(f"Underflow Handling: {e}")


def dfs_iterative(graph: dict[int, list[int]], start: int) -> list[int]:
    """Iterative DFS using an explicit stack -- Time O(V+E), Space O(V).

    Implement DFS using a stack directly instead of recursion."""
    visited: list[int] = []
    seen: set[int] = set()
    stack: list[int] = [start]

    while stack:
        node = stack.pop()      #Stack LIFO -> DFS
        if node in seen:
            continue
        seen.add(node)
        visited.append(node)
        #Push neighbor nodes in reverse order (to maintain visit order consistency)
        for neighbor in reversed(graph.get(node, [])):
            if neighbor not in seen:
                stack.append(neighbor)

    return visited


def demo_dfs() -> None:
    """Graph DFS simulation."""
    print()
    print("=" * 50)
    print("Stack-based DFS Simulation")
    print("=" * 50)

    #   1
    #  / \\
    # 2   3
    # |   |
    # 4   5
    graph = {
        1: [2, 3],
        2: [4],
        3: [5],
        4: [],
        5: [],
    }
    print("Graph:", graph)
    order = dfs_iterative(graph, start=1)
    print("DFS Visit Order (Start=1):", order)   # [1, 2, 4, 3, 5]


if __name__ == "__main__":
    demo_basic_operations()
    demo_dfs()

#Topic: Queue Basics -- Performance Comparison: deque vs list, BFS Simulation
#Time: enqueue O(1), dequeue O(1) (based on deque)
#Space: O(n) -- number of elements stored in the queue

import time
from collections import deque


def demo_deque_operations() -> None:
    """Deque basic operations demo."""
    print("=" * 50)
    print("basic deque operations")
    print("=" * 50)

    q: deque[int] = deque()

    #enqueue (add to the right)
    for val in [10, 20, 30, 40, 50]:
        q.append(val)
        print(f"enqueue({val:2}) -> front{list(q)}back")

    print()
    #dequeue (remove from the left)
    while q:
        val = q.popleft()
        print(f"dequeue() -> {val:2}  front{list(q)}back")

    #Deque: O(1) on both ends
    print()
    print("deque bidirectional operations:")
    d: deque[int] = deque([1, 2, 3])
    d.appendleft(0)   #add to the left
    d.append(4)       #add to the right
    print("appendleft(0), append(4):", list(d))   # [0,1,2,3,4]
    d.popleft()       #remove from the left
    d.pop()           #remove from the right
    print("popleft(), pop():         ", list(d))  # [1,2,3]

    #maxlen feature (useful for sliding window)
    window: deque[int] = deque(maxlen=3)
    for v in range(6):
        window.append(v)
        print(f"  append({v}) -> {list(window)}")


def benchmark_list_vs_deque(n: int = 100_000) -> None:
    """Performance comparison of list.pop(0) vs deque.popleft()."""
    print()
    print("=" * 50)
    print(f"Performance comparison: list.pop(0) vs deque.popleft() (n={n:,})")
    print("=" * 50)

    #list method -- O(n) per pop(0)
    lst = list(range(n))
    t0 = time.perf_counter()
    while lst:
        lst.pop(0)
    t1 = time.perf_counter()
    list_time = t1 - t0

    #deque method -- O(1) per popleft()
    dq = deque(range(n))
    t0 = time.perf_counter()
    while dq:
        dq.popleft()
    t1 = time.perf_counter()
    deque_time = t1 - t0

    print(f"list.pop(0)       : {list_time:.4f}s")
    print(f"deque.popleft()   : {deque_time:.4f}s")
    if deque_time > 0:
        print(f"deque is about {list_time / deque_time:.1f} times faster!")


def bfs_iterative(
    graph: dict[int, list[int]], start: int
) -> list[int]:
    """BFS using a queue -- Time O(V+E), Space O(V)."""
    visited: list[int] = []
    seen: set[int] = {start}
    queue: deque[int] = deque([start])

    while queue:
        node = queue.popleft()    # FIFO -> BFS
        visited.append(node)
        for neighbor in graph.get(node, []):
            if neighbor not in seen:
                seen.add(neighbor)
                queue.append(neighbor)

    return visited


def demo_bfs() -> None:
    """Graph BFS simulation."""
    print()
    print("=" * 50)
    print("Queue-based BFS simulation")
    print("=" * 50)

    #   1
    #  / \\
    # 2   3
    # |   |
    # 4   5
    graph = {1: [2, 3], 2: [4], 3: [5], 4: [], 5: []}
    print("Graph:", graph)
    order = bfs_iterative(graph, start=1)
    print("BFS visit order (start=1):", order)   # [1, 2, 3, 4, 5]


if __name__ == "__main__":
    demo_deque_operations()
    benchmark_list_vs_deque()
    demo_bfs()

#Topic : Bracket Matching -- (), [], {}
#Time  : O(n) -- string length n
#Space : O(n) -- in the worst case, n/2 stored in stack


def is_valid_brackets(s: str) -> bool:
    """Checks whether a bracket string is valid.

    Algorithm:
      - Push opening brackets ( [ { onto the stack
      - When a closing bracket ) ] } appears:
          1. If the stack is empty -> False (no matching pair)
          2. If it does not match the stack top -> False
          3. If it matches, stack.pop()
      - After all processing, if the stack is empty -> True"""
    match = {")": "(", "]": "[", "}": "{"}
    stack: list[str] = []

    for ch in s:
        if ch in "([{":
            stack.append(ch)
        elif ch in ")]}":
            if not stack or stack[-1] != match[ch]:
                return False
            stack.pop()

    return len(stack) == 0


def bracket_balance_detail(s: str) -> str:
    """Returns an explanation of what issue it is if it is invalid."""
    match = {")": "(", "]": "[", "}": "{"}
    stack: list[tuple[str, int]] = []   #(Bracket, Index)

    for i, ch in enumerate(s):
        if ch in "([{":
            stack.append((ch, i))
        elif ch in ")]}":
            if not stack:
                return f"Position {i}: No opening bracket corresponding to '{ch}'"
            top_ch, top_idx = stack[-1]
            if top_ch != match[ch]:
                return (
                    f"Position {i}: '{ch}' does not match '{top_ch}' at position {top_idx}"
                )
            stack.pop()

    if stack:
        ch, idx = stack[-1]
        return f"Position {idx}: No closing bracket corresponding to '{ch}'"
    return "Valid"


def count_min_removals(s: str) -> int:
    """Making valid parentheses with the minimum number of removals -- O(n)."""
    open_count = 0   #Number of '(' not matched
    close_count = 0  #Number of ')' not matched

    for ch in s:
        if ch == "(":
            open_count += 1
        elif ch == ")":
            if open_count > 0:
                open_count -= 1   #Match Success
            else:
                close_count += 1  #Match Failed ')'

    return open_count + close_count


if __name__ == "__main__":
    print("=" * 55)
    print("Bracket Matching Check")
    print("=" * 55)

    test_cases = [
        ("()",         True),
        ("()[]{}",     True),
        ("(]",         False),
        ("([)]",       False),
        ("{[]}",       True),
        ("",           True),
        ("(((", False),
        (")))", False),
        ("{[()]}",     True),
        ("([{}])",     True),
    ]

    print(f"{'Input':15} {'Expected':6} {'Result':6} {'Status'}")
    print("-" * 40)
    for s, expected in test_cases:
        result = is_valid_brackets(s)
        status = "OK" if result == expected else "NG"
        print(f"{s!r:15} {str(expected):6} {str(result):6} {status}")

    print()
    print("=" * 55)
    print("Detailed Error Analysis")
    print("=" * 55)
    detail_cases = ["(]", "([)]", "(((", "{[]}", ")))"]
    for s in detail_cases:
        print(f"{s!r:10} -> {bracket_balance_detail(s)}")

    print()
    print("=" * 55)
    print("Minimum Removal Count")
    print("=" * 55)
    removal_cases = ["()))(" , "((("]
    for s in removal_cases:
        print(f"{s!r:10} -> Minimum removals {count_min_removals(s)} times")

#Topic: Evaluation of Postfix Expression (Postfix / RPN) and Infix -> Postfix Conversion
#Time: O(n) -- proportional to the number of tokens
#Space: O(n) -- stack size

OPERATORS = set("+-*/^")
PRECEDENCE = {"+": 1, "-": 1, "*": 2, "/": 2, "^": 3}


def evaluate_postfix(expression: str) -> float:
    """Calculates a postfix expression -- Time O(n), Space O(n).

    Example: '3 4 2 * +' -> 3 + (4*2) = 11.0"""
    stack: list[float] = []
    tokens = expression.split()

    for token in tokens:
        if token in OPERATORS:
            if len(stack) < 2:
                raise ValueError(f"Not enough operands: stack={stack}, operator={token}")
            b = stack.pop()   #Right operand
            a = stack.pop()   #Left operand
            if token == "+":
                stack.append(a + b)
            elif token == "-":
                stack.append(a - b)
            elif token == "*":
                stack.append(a * b)
            elif token == "/":
                if b == 0:
                    raise ZeroDivisionError("Division by zero")
                stack.append(a / b)
            elif token == "^":
                stack.append(a ** b)
        else:
            stack.append(float(token))

    if len(stack) != 1:
        raise ValueError(f"Invalid expression: stack={stack}")
    return stack[0]


def infix_to_postfix(expression: str) -> str:
    """Convert infix expressions to postfix expressions -- Shunting-Yard algorithm.

    Time O(n), Space O(n)."""
    output: list[str] = []
    op_stack: list[str] = []
    tokens = expression.split()

    for token in tokens:
        if token not in OPERATORS and token not in "()":
            #Operand: output immediately
            output.append(token)
        elif token == "(":
            op_stack.append(token)
        elif token == ")":
            #Pop until matching '('
            while op_stack and op_stack[-1] != "(":
                output.append(op_stack.pop())
            if op_stack:
                op_stack.pop()  #Remove '('
        else:
            #Operator: compare precedence
            while (
                op_stack
                and op_stack[-1] != "("
                and op_stack[-1] in PRECEDENCE
                and PRECEDENCE[op_stack[-1]] >= PRECEDENCE[token]
            ):
                output.append(op_stack.pop())
            op_stack.append(token)

    #Output all remaining operators
    while op_stack:
        output.append(op_stack.pop())

    return " ".join(output)


if __name__ == "__main__":
    print("=" * 55)
    print("Postfix expression evaluation")
    print("=" * 55)

    postfix_cases = [
        ("3 4 +",                7.0),    # 3+4
        ("3 4 2 * +",           11.0),   # 3 + 4*2
        ("5 1 2 + 4 * + 3 -",  14.0),   # 5+((1+2)*4)-3
        ("2 3 ^",                8.0),   # 2^3
        ("10 2 /",               5.0),   # 10/2
    ]

    print(f"{'Postfix Expression':30} {'Expected':8} {'Result':8}")
    print("-" * 50)
    for expr, expected in postfix_cases:
        result = evaluate_postfix(expr)
        ok = "OK" if abs(result - expected) < 1e-9 else "NG"
        print(f"{expr:30} {expected:8.1f} {result:8.1f} {ok}")

    print()
    print("=" * 55)
    print("Infix -> Postfix Conversion (Shunting-Yard)")
    print("=" * 55)

    infix_cases = [
        "3 + 4",
        "3 + 4 * 2",
        "( 3 + 4 ) * 2",
        "5 + ( 1 + 2 ) * 4 - 3",
    ]

    for expr in infix_cases:
        postfix = infix_to_postfix(expr)
        value = evaluate_postfix(postfix)
        print(f"Infix: {expr:30} -> Postfix: {postfix:25} = {value}")