List-Based Queue in Python — O(n) pop(0) Performance Trap

# A Stack implemented with a Python list.
# Real-world scenario: browser back-button history.

class BrowserHistoryStack:
    def __init__(self):
        # The list acts as our stack storage.
        # The RIGHT end of the list is the TOP of the stack.
        self._history = []

    def push(self, url: str) -> None:
        """Visit a new page — push the URL onto the top of the stack."""
        self._history.append(url)  # append() is O(1) — always adds to the right end
        print(f"  Visited: {url}")

    def pop(self) -> str:
        """Go back — remove and return the most recently visited page."""
        if self.is_empty():
            raise IndexError("No history to go back to — stack is empty")
        previous_page = self._history.pop()  # pop() with no argument removes from the RIGHT end — O(1)
        print(f"  Going back to: {self._history[-1] if self._history else 'Start page'}")
        return previous_page

    def peek(self) -> str:
        """See the current page without removing it."""
        if self.is_empty():
            raise IndexError("Stack is empty — no current page")
        return self._history[-1]  # -1 index always gives us the top of the stack

    def is_empty(self) -> bool:
        return len(self._history) == 0

    def size(self) -> int:
        return len(self._history)

    def __repr__(self) -> str:
        # Display the stack so the top is on the RIGHT (most intuitive for lists)
        return f"BrowserHistoryStack({self._history}) <- TOP"


# --- Let's simulate a browsing session ---
history = BrowserHistoryStack()

history.push("https://google.com")
history.push("https://thecodeforge.io")
history.push("https://thecodeforge.io/python-stacks")

print(f"\nCurrent stack: {history}")
print(f"Currently on: {history.peek()}")
print(f"Stack size: {history.size()}")

print("\n-- Pressing back twice --")
history.pop()
history.pop()

print(f"\nCurrent stack: {history}")
print(f"Currently on: {history.peek()}")

# A Queue implemented with a Python list.
# Real-world scenario: customer support ticket processing.
# We'll also benchmark the naive approach to show WHY deque exists.

import time

class SupportTicketQueue:
    def __init__(self):
        # The list acts as our queue storage.
        # RIGHT end = back of queue (where new tickets are added).
        # LEFT end  = front of queue (where tickets are processed next).
        self._tickets = []

    def enqueue(self, ticket_id: str) -> None:
        """Add a new support ticket to the back of the queue."""
        self._tickets.append(ticket_id)  # append() is O(1) — fast
        print(f"  Ticket {ticket_id} added to queue")

    def dequeue(self) -> str:
        """Process the next ticket — remove from the front of the queue."""
        if self.is_empty():
            raise IndexError("No tickets in queue — nothing to process")
        # pop(0) removes the FIRST element — but this is O(n) on a plain list!
        # Every element shifts left by one position in memory.
        # This is fine for small queues; use collections.deque for large ones.
        next_ticket = self._tickets.pop(0)
        print(f"  Processing ticket: {next_ticket}")
        return next_ticket

    def peek(self) -> str:
        """See which ticket is next without processing it."""
        if self.is_empty():
            raise IndexError("Queue is empty")
        return self._tickets[0]  # Front of the queue is always index 0

    def is_empty(self) -> bool:
        return len(self._tickets) == 0

    def size(self) -> int:
        return len(self._tickets)

    def __repr__(self) -> str:
        return f"FRONT -> {self._tickets} <- BACK"


# --- Simulate a support queue ---
ticket_queue = SupportTicketQueue()

ticket_queue.enqueue("TKT-001")  # First customer — should be helped first
ticket_queue.enqueue("TKT-002")
ticket_queue.enqueue("TKT-003")

print(f"\nQueue state: {ticket_queue}")
print(f"Next up: {ticket_queue.peek()}")
print(f"Tickets waiting: {ticket_queue.size()}")

print("\n-- Processing tickets in order --")
ticket_queue.dequeue()  # TKT-001 goes first — FIFO in action
ticket_queue.dequeue()  # TKT-002 goes second

print(f"\nQueue state: {ticket_queue}")

# --- Now let's see the O(n) cost of pop(0) on a large list ---
print("\n-- Performance comparison: pop(0) vs pop() --")

large_list_front = list(range(500_000))  # 500,000 items
large_list_back  = list(range(500_000))

start = time.perf_counter()
for _ in range(10_000):
    large_list_front.pop(0)  # Removing from the FRONT — O(n) each time
elapsed_front = time.perf_counter() - start

start = time.perf_counter()
for _ in range(10_000):
    large_list_back.pop()    # Removing from the BACK — O(1) each time
elapsed_back = time.perf_counter() - start

print(f"  pop(0) — removing from front: {elapsed_front:.4f}s")
print(f"  pop()  — removing from back:  {elapsed_back:.4f}s")
print(f"  pop(0) is roughly {elapsed_front / elapsed_back:.1f}x slower")

# Real-world Stack use case: validating balanced brackets.
# This exact logic is used in code editors, compilers, and JSON parsers.

def is_balanced(expression: str) -> bool:
    """
    Returns True if all brackets in the expression are correctly matched.
    Uses a Stack to track open brackets as we scan left to right.
    """
    # Map each closing bracket to its expected opening bracket
    matching_open = {')': '(', ']': '[', '}': '{'}
    closing_brackets = set(matching_open.keys())
    opening_brackets = set(matching_open.values())

    bracket_stack = []  # Our stack — stores unmatched opening brackets

    for character in expression:
        if character in opening_brackets:
            # We found an opener — push it onto the stack and move on
            bracket_stack.append(character)

        elif character in closing_brackets:
            # We found a closer — the stack top MUST be its matching opener
            if not bracket_stack:
                # Closer with nothing on the stack — unmatched closer
                return False

            top_of_stack = bracket_stack.pop()  # Pop the most recent opener

            if top_of_stack != matching_open[character]:
                # Top of stack doesn't match this closer — mismatched pair
                return False

    # If the stack is empty, every opener was matched and closed
    # If not empty, some openers were never closed
    return len(bracket_stack) == 0


# --- Test the validator ---
test_cases = [
    ("({[]})",          True),   # Perfectly nested — all matched
    ("([)]",            False),  # Wrong order — square closed before round
    ("{[()()]}",        True),   # Multiple levels of nesting — all matched
    ("(((",             False),  # All openers, no closers
    (")))",             False),  # All closers, no openers
    ("def func(a[0]):", True),   # Real code-like expression
    ("{name: [1,2,3]}", True),   # JSON-like structure
]

print("Bracket Validation Results:")
print("-" * 45)
for expression, expected in test_cases:
    result = is_balanced(expression)
    status = "PASS" if result == expected else "FAIL"
    print(f"  [{status}] '{expression}' -> {result}")

# Production-grade Queue using collections.deque
from collections import deque
import time

class DequeQueue:
    def __init__(self):
        self._items = deque()

    def enqueue(self, item):
        self._items.append(item)       # O(1)

    def dequeue(self):
        if not self._items:
            raise IndexError("Queue empty")
        return self._items.popleft()   # O(1) — no element shifting

    def peek(self):
        if not self._items:
            raise IndexError("Queue empty")
        return self._items[0]

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

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

# --- Benchmark: deque popleft() vs list pop(0) ---
import time

deque_bench = deque(list(range(500_000)))
list_bench = list(range(500_000))

start = time.perf_counter()
for _ in range(10_000):
    deque_bench.popleft()
elapsed_deque = time.perf_counter() - start

start = time.perf_counter()
for _ in range(10_000):
    list_bench.pop(0)
elapsed_list = time.perf_counter() - start

print(f"deque.popleft(): {elapsed_deque:.6f}s")
print(f"list.pop(0):     {elapsed_list:.6f}s")
print(f"deque is about {elapsed_list / elapsed_deque:.0f}x faster")

# Thread-safe worker queue using queue.Queue
from queue import Queue
from threading import Thread
import time

def worker(work_queue: Queue, worker_id: int):
    while True:
        item = work_queue.get()
        if item is None:  # poison pill to stop the worker
            work_queue.task_done()
            break
        print(f"Worker {worker_id} processing: {item}")
        time.sleep(0.1)  # simulate work
        work_queue.task_done()

# Create a queue with maximum 10 pending items
q = Queue(maxsize=10)

# Start 3 worker threads
threads = []
for i in range(3):
    t = Thread(target=worker, args=(q, i))
    t.start()
    threads.append(t)

# Enqueue 20 tasks
for i in range(20):
    q.put(f"Task-{i}")
    print(f"Enqueued Task-{i}, queue size: {q.qsize()}")

# Wait for all tasks to be processed
q.join()

# Stop workers with poison pills
for _ in range(3):
    q.put(None)
for t in threads:
    t.join()

print("All tasks completed.")