Queues

from collections import deque

class Queue:
    def __init__(self):
        # deque gives us O(1) popleft — a plain list would be O(n)
        self._data = deque()

    def enqueue(self, val):
        self._data.append(val)

    def dequeue(self):
        if not self._data:
            raise IndexError("dequeue from empty queue")
        return self._data.popleft()

    def peek(self):
        if not self._data:
            raise IndexError("peek from empty queue")
        return self._data[0]

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

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


# Usage
q = Queue()
q.enqueue(10)
q.enqueue(20)
q.enqueue(30)
print(q.dequeue())  # 10 — first in, first out
print(q.peek())     # 20 — next in line, but stays

class Queue {
  constructor() {
    // Use a map with numeric keys instead of an array
    // so dequeue doesn't shift every element (O(n) with arrays)
    this._data = {};
    this._head = 0;
    this._tail = 0;
  }

  enqueue(val) {
    this._data[this._tail] = val;
    this._tail++;
  }

  dequeue() {
    if (this.isEmpty()) throw new Error("Queue is empty");
    const val = this._data[this._head];
    delete this._data[this._head];
    this._head++;
    return val;
  }

  peek() {
    if (this.isEmpty()) throw new Error("Queue is empty");
    return this._data[this._head];
  }

  isEmpty() {
    return this._tail === this._head;
  }

  get size() {
    return this._tail - this._head;
  }
}

// Usage
const q = new Queue();
q.enqueue(10);
q.enqueue(20);
q.enqueue(30);
console.log(q.dequeue()); // 10
console.log(q.peek());    // 20

class CircularQueue:
    """Fixed-size circular queue (ring buffer).
    
    Used in: network packet buffers, audio processing,
    producer-consumer patterns, kernel I/O buffers.
    
    Wraps around using modulo arithmetic — when the pointer
    reaches the end of the array, it jumps back to index 0.
    """
    def __init__(self, capacity):
        self._data = [None] * capacity
        self._capacity = capacity
        self._front = 0
        self._rear = 0
        self._size = 0

    def enqueue(self, val):
        if self._size == self._capacity:
            raise OverflowError("queue is full")
        self._data[self._rear] = val
        self._rear = (self._rear + 1) % self._capacity  # wrap around
        self._size += 1

    def dequeue(self):
        if self._size == 0:
            raise IndexError("queue is empty")
        val = self._data[self._front]
        self._data[self._front] = None  # help GC
        self._front = (self._front + 1) % self._capacity  # wrap around
        self._size -= 1
        return val

    def peek(self):
        if self._size == 0:
            raise IndexError("queue is empty")
        return self._data[self._front]

    def is_full(self):
        return self._size == self._capacity

    def is_empty(self):
        return self._size == 0

import heapq

# Python's heapq is a min-heap — smallest value comes out first
pq = []
heapq.heappush(pq, (3, "low priority"))
heapq.heappush(pq, (1, "high priority"))
heapq.heappush(pq, (2, "medium priority"))

# Items come out in priority order, not insertion order
while pq:
    priority, task = heapq.heappop(pq)
    print(f"Priority {priority}: {task}")
# Output:
#   Priority 1: high priority
#   Priority 2: medium priority
#   Priority 3: low priority


# For a max-heap, negate the priority
heapq.heappush(pq, (-5, "important"))
heapq.heappush(pq, (-1, "trivial"))
priority, task = heapq.heappop(pq)
print(-priority, task)  # 5, "important"

class MinHeap {
  constructor() {
    this._heap = [];
  }

  push(val) {
    this._heap.push(val);
    this._bubbleUp(this._heap.length - 1);
  }

  pop() {
    if (!this._heap.length) throw new Error("Heap is empty");
    const min = this._heap[0];
    const last = this._heap.pop();
    if (this._heap.length) {
      this._heap[0] = last;
      this._bubbleDown(0);
    }
    return min;
  }

  peek() {
    return this._heap[0];
  }

  _bubbleUp(i) {
    // Keep swapping with parent until heap property holds
    while (i > 0) {
      const parent = Math.floor((i - 1) / 2);
      if (this._heap[i] >= this._heap[parent]) break;
      [this._heap[i], this._heap[parent]] = [this._heap[parent], this._heap[i]];
      i = parent;
    }
  }

  _bubbleDown(i) {
    const n = this._heap.length;
    while (true) {
      let smallest = i;
      const left = 2 * i + 1;
      const right = 2 * i + 2;
      // Find the smallest among node and its children
      if (left < n && this._heap[left] < this._heap[smallest]) smallest = left;
      if (right < n && this._heap[right] < this._heap[smallest]) smallest = right;
      if (smallest === i) break;
      [this._heap[i], this._heap[smallest]] = [this._heap[smallest], this._heap[i]];
      i = smallest;
    }
  }

  get size() { return this._heap.length; }
}

import heapq
import time

class TaskScheduler:
    """Priority-based task scheduler.
    
    Tasks with lower priority numbers run first.
    Ties are broken by arrival order (FIFO within same priority).
    
    This is the basic pattern behind: OS process schedulers,
    Celery/RQ job queues, hospital triage systems, Dijkstra's algorithm.
    """
    def __init__(self):
        self._queue = []
        self._counter = 0  # Tiebreaker for same-priority tasks

    def add_task(self, name, priority=5):
        # Tuple comparison: first by priority, then by arrival order
        # The counter ensures FIFO ordering within the same priority
        heapq.heappush(self._queue, (priority, self._counter, name))
        self._counter += 1
        print(f"  + Queued: '{name}' (priority {priority})")

    def run_next(self):
        if not self._queue:
            print("  No tasks in queue")
            return None
        priority, _, name = heapq.heappop(self._queue)
        print(f"  ▶ Running: '{name}' (priority {priority})")
        return name

    def run_all(self):
        print("Running all tasks in priority order:")
        while self._queue:
            self.run_next()


# Simulate a server processing requests
scheduler = TaskScheduler()
scheduler.add_task("Send weekly report email", priority=3)
scheduler.add_task("Process payment", priority=1)        # urgent!
scheduler.add_task("Generate thumbnails", priority=5)
scheduler.add_task("Send password reset", priority=2)
scheduler.add_task("Clean temp files", priority=5)

print()
scheduler.run_all()
# Output:
#   ▶ Running: 'Process payment' (priority 1)
#   ▶ Running: 'Send password reset' (priority 2)
#   ▶ Running: 'Send weekly report email' (priority 3)
#   ▶ Running: 'Generate thumbnails' (priority 5)
#   ▶ Running: 'Clean temp files' (priority 5)