Stack and Queue in Python — list.pop(0) Performance Bug

# 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}")

// io.thecodeforge — java tutorial

import java.util.*;

public class CacheMissDemonstration {
    public static void main(String[] args) {
        int elements = 10_000_000;
        
        // LinkedList — pointer chasing nightmare
        Queue<Integer> linked = new LinkedList<>();
        long start = System.nanoTime();
        for (int i = 0; i < elements; i++) linked.add(i);
        while (!linked.isEmpty()) linked.poll();
        long linkedTime = System.nanoTime() - start;
        
        // ArrayDeque — contiguous memory bliss
        Queue<Integer> arrayDeque = new ArrayDeque<>(elements);
        start = System.nanoTime();
        for (int i = 0; i < elements; i++) arrayDeque.add(i);
        while (!arrayDeque.isEmpty()) arrayDeque.poll();
        long dequeTime = System.nanoTime() - start;
        
        System.out.println("LinkedList: " + linkedTime / 1_000_000 + " ms");
        System.out.println("ArrayDeque: " + dequeTime / 1_000_000 + " ms");
        System.out.println("ArrayDeque is " + ((double) linkedTime / dequeTime) + "x faster");
    }
}

// io.thecodeforge — java tutorial

import java.util.*;
import java.util.concurrent.*;

public class StackComparison {
    public static void main(String[] args) {
        int operations = 10_000_000;
        
        // Legacy Stack - synchronized overhead
        Stack<Integer> legacy = new Stack<>();
        long start = System.nanoTime();
        for (int i = 0; i < operations; i++) legacy.push(i);
        for (int i = 0; i < operations; i++) legacy.pop();
        long legacyTime = System.nanoTime() - start;
        
        // ArrayDeque as LIFO - no sync, contiguous memory
        Deque<Integer> fast = new ArrayDeque<>(operations);
        start = System.nanoTime();
        for (int i = 0; i < operations; i++) fast.push(i);
        for (int i = 0; i < operations; i++) fast.pop();
        long fastTime = System.nanoTime() - start;
        
        System.out.println("Stack (legacy): " + legacyTime / 1_000_000 + " ms");
        System.out.println("ArrayDeque:      " + fastTime / 1_000_000 + " ms");
        System.out.println("ArrayDeque is " + String.format("%.1f", (double) legacyTime / fastTime) + "x faster");
    }
}

// io.thecodeforge — java tutorial

import java.util.*;

record Task(int priority, String name, long createdAt) {}

public class StablePriorityQueue {
    public static void main(String[] args) {
        // Comparator that uses creation order as tiebreaker
        Queue<Task> queue = new PriorityQueue<>(
            (a, b) -> {
                if (a.priority() != b.priority()) 
                    return Integer.compare(a.priority(), b.priority());
                return Long.compare(a.createdAt(), b.createdAt());
            }
        );
        
        // Insert with same priority, different creation times
        queue.add(new Task(1, "payroll", 100));
        queue.add(new Task(1, "invoice", 200));
        queue.add(new Task(2, "report", 300));
        queue.add(new Task(1, "email", 150));
        
        while (!queue.isEmpty()) {
            Task t = queue.poll();
            System.out.println(t.name() + " (priority=" + t.priority() + ")");
        }
    }
}

// io.thecodeforge — java tutorial

import java.util.Stack;

public class StackCapacityDemo {
    public static void main(String[] args) {
        // Default capacity 10 — painful resize at 11
        Stack<Integer> lazy = new Stack<>();
        
        // Pre-allocated — zero resizes
        Stack<Integer> smart = new Stack<>() {
            { ensureCapacity(1000); }
        };
        
        long start = System.nanoTime();
        for (int i = 0; i < 1000; i++) lazy.push(i);
        long lazyTime = System.nanoTime() - start;
        
        start = System.nanoTime();
        for (int i = 0; i < 1000; i++) smart.push(i);
        long smartTime = System.nanoTime() - start;
        
        System.out.println("Lazy: " + lazyTime + " ns");
        System.out.println("Smart: " + smartTime + " ns");
    }
}

// io.thecodeforge — java tutorial

import java.util.Stack;

public class StackEnsureCapacity {
    public static void main(String[] args) {
        // No constructor exists, but we can still pre-size
        Stack<String> s = new Stack<>();
        s.ensureCapacity(10_000);  // allocates array of length 10,000
        
        for (int i = 0; i < 10_000; i++) {
            s.push("item-" + i);
        }
        
        System.out.println("Capacity: " + s.capacity());
        System.out.println("Size: " + s.size());
    }
}

// io.thecodeforge — java tutorial
// Article categories: choose stack, queue, or priority

import java.util.*;

public class StackQueueCategories {
    public static void main(String[] args) {
        // Category: Sequence Reversal -> ArrayDeque as stack
        Deque<String> stack = new ArrayDeque<>();
        stack.push("undo1"); stack.push("undo2");
        System.out.println(stack.pop()); // undo2 (LIFO)

        // Category: Buffering -> LinkedList as queue
        Queue<String> queue = new LinkedList<>();
        queue.offer("task1"); queue.offer("task2");
        System.out.println(queue.poll()); // task1 (FIFO)

        // Category: Prioritized -> PriorityQueue (min-heap)
        Queue<Integer> pq = new PriorityQueue<>();
        pq.offer(30); pq.offer(10); pq.offer(20);
        System.out.println(pq.poll()); // 10 (smallest first)
    }
}

// io.thecodeforge — java tutorial
// Test output: stack vs queue vs priority

import java.util.*;

public class OutputTest {
    public static void main(String[] args) {
        Deque<Integer> stack = new ArrayDeque<>();
        stack.push(1); stack.push(2);
        System.out.println("Stack pop: " + stack.pop()); // 2

        Queue<Integer> queue = new LinkedList<>();
        queue.offer(1); queue.offer(2);
        System.out.println("Queue poll: " + queue.poll()); // 1

        Queue<Integer> pq = new PriorityQueue<>();
        pq.offer(30); pq.offer(10); pq.offer(20);
        System.out.println("Priority poll: " + pq.poll()); // 10
    }
}