Queues, Priority Queues, and Real-World Scheduling

1. Queues: First-In-First-Out (FIFO) Order

A queue is a linear data structure that follows the FIFO (First-In-First-Out) principle. The first element added is the first one removed. It has two primary operations:

• Enqueue: Add an element to the rear (back) of the queue.
• Dequeue: Remove an element from the front (head) of the queue.

Key Operations

Implementation: Array vs. Linked List

• Array-based queue:

  • Fixed size (may overflow).
  • Requires shifting elements if implemented naively (inefficient).
  • Circular array is used to optimize space.

• Linked-list-based queue:

  • Dynamic size (no overflow).
  • No shifting needed (pointers adjust dynamically).

Example: eSewa Transaction Queue

When you pay a bill via eSewa, your transaction is added to a queue of pending payments. The system processes payments in the order they were received (FIFO), ensuring fairness.

Worked Example: Bank Customer Queue

Suppose a bank has a single queue for all customers. Customers arrive in this order: A, B, C, D, E.

• Enqueue(A), Enqueue(B), Enqueue(C) → Queue: [A, B, C]
• Dequeue(A) → Queue: [B, C]
• Enqueue(D), Enqueue(E) → Queue: [B, C, D, E]
• Dequeue(B) → Queue: [C, D, E]

2. Priority Queues: Order Based on Priority

A priority queue is a queue where elements are dequeued based on their priority (not FIFO). Higher-priority elements are served first.

Types of Priority Queues

Operations

Example: Pathao Ride Dispatch

When you request a ride on Pathao, your request is assigned to the nearest available driver based on priority (distance, driver availability, surge pricing). Drivers with higher priority (closer distance) are matched first.

flowchart TD
    A["Priority Queue: [(P3: Low), (P1: High), (P2: Medium)]"] -->|"Enqueue(P4: Urgent)"| B["Priority Queue: [(P4: Urgent), (P1: High), (P2: Medium), (P3: Low)]"]
    B -->|"Dequeue(P4)"| C["Priority Queue: [(P1: High), (P2: Medium), (P3: Low)]"]

Worked Example: Hospital Emergency Triage

Patients arrive with different priorities:

• P1 (Critical): Heart attack (Priority 1)
• P2 (Urgent): Fracture (Priority 2)
• P3 (Non-urgent): Cold (Priority 3)

Queue after arrivals: [P1, P2, P3] After dequeue (P1): [P2, P3] After enqueue (P4: Stroke, Priority 1): [P4, P2, P3] After dequeue (P4): [P2, P3]

3. Implementations: Arrays vs. Linked Lists vs. Heaps

Visual: Array-Based Queue (Circular)

Visual: Heap-Based Priority Queue (Max-Heap)

graph TD
    A["Root (Max)"] --> B["Left Child"]
    A --> C["Right Child"]
    B --> D["Grandchild"]
    C --> E["Grandchild"]

4. Applications in Real World

1. Operating System Task Scheduling

• Example: Windows Task Manager uses a priority queue to schedule processes. High-priority tasks (e.g., system updates) run before low-priority ones (e.g., background apps).

2. Network Routing (NTC, Ncell)

• Example: When you make a call via Ncell, the network uses a priority queue to route calls based on signal strength and congestion. Emergency calls (911) get the highest priority.

3. Online Order Processing (Daraz, Amazon)

• Example: When you place an order on Daraz, items are packed and shipped in FIFO order (first ordered, first shipped) to ensure fairness. High-value orders may get priority during sales.

4. Call Center Systems (Nepal Telecom)

• Example: Customer calls are handled in priority order (e.g., VIP customers first, then regular calls). A queue ensures calls are answered in the order they arrive.

5. Algorithms Using Queues & Priority Queues

A. Breadth-First Search (BFS) – Uses Queue

BFS explores all neighbors at the present depth before moving deeper. Used in shortest path finding (unweighted graphs).

B. Dijkstra’s Algorithm – Uses Priority Queue

Finds the shortest path in a weighted graph (e.g., GPS navigation).

import heapq

def dijkstra(graph, start):
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    priority_queue = [(0, start)]

    while priority_queue:
        current_dist, current_node = heapq.heappop(priority_queue)
        if current_dist > distances[current_node]:
            continue
        for neighbor, weight in graph[current_node].items():
            distance = current_dist + weight
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(priority_queue, (distance, neighbor))
    return distances

Trace: Dijkstra’s Algorithm (Graph: A→B(1), A→C(4), B→C(2), B→D(5), C→D(1))

6. Comparison: Queue vs. Priority Queue

7. Common Pitfalls & Exam Tips

❌ Mistakes to Avoid

• Assuming queues are LIFO: Queues are FIFO, not stacks (LIFO).
• Ignoring priority in priority queues: Always check if the highest-priority element is dequeued.
• Overflow in array-based queues: Use circular arrays to avoid wasting space.

✅ Exam Tips

1. Draw diagrams for queue operations (enqueue/dequeue) and priority queue updates.
2. Memorize time complexities for heap operations (O(log n) for insert/delete).
3. Relate to real-world examples:
   • Queue: eSewa transactions, bank tellers.
   • Priority Queue: Pathao ride dispatch, hospital triage.
4. Practice coding:
   • Implement a queue using a linked list.
   • Write a priority queue using a min-heap.
5. Understand BFS/Dijkstra: Know when to use a queue vs. a priority queue.