Queues, Priority Queues, and Real-World Scheduling

Core Concepts

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

A queue is a linear data structure that follows the FIFO (First-In-First-Out) principle. Elements are added at the rear (enqueue) and removed from the front (dequeue). It is analogous to a real-world queue (line), where the first person to join is the first to be served.

Key Operations:

• Enqueue: Add an element to the rear.
• Dequeue: Remove an element from the front.
• Peek/Front: View the front element without removal.
• isEmpty: Check if the queue is empty.
• isFull: Check if the queue is full (for fixed-size implementations).

Time Complexity:

Types of Queues:

1. Simple Queue: Basic FIFO implementation.
2. Circular Queue: Efficiently reuses space by wrapping around.
3. Double-Ended Queue (Deque): Allows insertion and deletion from both ends.

---

Example: Circular Queue

A circular queue avoids wasting space by using a fixed-size array and reusing slots after the rear reaches the end.

Code (Circular Queue in C):

#include <stdio.h>
#define MAX 5

int queue[MAX];
int front = -1, rear = -1;

void enqueue(int x) {
    if ((front == 0 && rear == MAX - 1) || (rear == front - 1)) {
        printf("Queue is full\n");
    } else if (front == -1) {
        front = rear = 0;
        queue[rear] = x;
    } else if (rear == MAX - 1) {
        rear = 0;
        queue[rear] = x;
    } else {
        rear++;
        queue[rear] = x;
    }
}

int dequeue() {
    int item;
    if (front == -1) {
        printf("Queue is empty\n");
        return -1;
    }
    item = queue[front];
    if (front == rear) {
        front = rear = -1;
    } else if (front == MAX - 1) {
        front = 0;
    } else {
        front++;
    }
    return item;
}

Trace: Enqueue and Dequeue Operations

---

---

Priority Queues: Order Matters

A priority queue is a specialized queue where elements are dequeued based on their priority, not arrival order. It is implemented using:

• Min-Heap: Smallest element has highest priority.
• Max-Heap: Largest element has highest priority.

Key Operations:

• Insert: Add an element with a priority.
• Extract-Min/Max: Remove the highest-priority element.
• Peek: View the highest-priority element.

Time Complexity:

Example: Min-Heap Priority Queue

A min-heap ensures the smallest element is always at the root.

Code (Min-Heap in Python):

import heapq

class PriorityQueue:
    def __init__(self):
        self.heap = []

    def enqueue(self, item, priority):
        heapq.heappush(self.heap, (priority, item))

    def dequeue(self):
        return heapq.heappop(self.heap)[1]

    def peek(self):
        return self.heap[0][1] if self.heap else None

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

Trace: Insert and Extract Operations

---

---

In the Real World

1. eSewa and Khalti Transactions:

   • Queue Idea: When multiple users request bill payments simultaneously, eSewa processes them in FIFO order to ensure fairness. If two users pay their electricity bill at the same time, the one who initiated the request first gets processed first.
   • Priority Queue Idea: For premium users (e.g., those with higher transaction limits), Khalti may use a priority queue to process their transactions before others, ensuring faster service.

2. Daraz Order Fulfillment:

   • Queue Idea: When a customer places an order on Daraz, the system assigns it to a warehouse worker in FIFO order. The first order received is the first to be packed and shipped.
   • Priority Queue Idea: If a customer selects "Express Delivery," their order is placed in a high-priority queue, ensuring it is processed before standard orders.

3. Ncell Call Center:

   • Priority Queue Idea: Incoming customer calls are routed based on priority. Complaints about network issues are given higher priority (min-heap) and resolved before routine inquiries, reducing customer dissatisfaction.

4. Bank Loan Processing:

   • Priority Queue Idea: Banks use priority queues to process loan applications. Applications from high-net-worth individuals or those with lower risk scores (min-heap for risk) are processed first, optimizing resource allocation.

5. NEPSE Stock Trading:

   • Queue Idea: Buy/sell orders for stocks are executed in FIFO order for the same price. If two traders place a buy order for 100 shares of Nabil Bank at Rs. 500, the first order is fulfilled before the second.
   • Priority Queue Idea: Market makers or institutional investors may get priority execution (higher priority in the queue) for large trades to ensure liquidity.

6. Pathao Driver Assignment:

   • Priority Queue Idea: When multiple drivers are available for a ride request, Pathao assigns the driver closest to the pickup location (highest priority) first. This is implemented using a max-heap where the driver with the smallest distance (highest priority) is dequeued first.

---

Applications of Queues and Priority Queues

---

Comparison: Queue vs. Priority Queue

---

Worked Example: Bank Loan Processing with Priority Queue

Scenario: A bank receives loan applications with different risk levels (1 = lowest risk, 5 = highest risk). The bank wants to process low-risk applications first.

Priority Queue Operations:

1. Enqueue applications with their risk levels:

   • (Risk 3, Customer A)
   • (Risk 1, Customer B)
   • (Risk 5, Customer C)
   • (Risk 2, Customer D)

2. Process applications in order of increasing risk (min-heap).

Trace:

Visualization:

---

Exam Tip

1. Understand FIFO vs. Priority:

   • Queues are strictly FIFO; priority queues ignore order for priority.
   • Common Mistake: Confusing a queue with a stack (LIFO). Always emphasize FIFO.

2. Circular Queue Implementation:

   • Key Insight: Use modulo arithmetic ((rear + 1) % MAX) to wrap around.
   • Exam Question: Given a circular queue, trace the front and rear pointers after a series of enqueue/dequeue operations.

3. Heap Operations:

   • Heapify Up/Down: After insertion or deletion, the heap property must be restored.
   • Code Snippet: Be ready to write a function to insert into a min-heap or extract the min element.

4. Real-World Scenarios:

   • Application Questions: Expect questions like:
     • "How would you implement a call center system using queues?"
     • "Why might a bank use a priority queue for loan processing?"
   • Answer Tip: Relate to fairness (FIFO) or urgency (priority).

5. Time Complexity:

   • Queue: All operations are O(1).
   • Priority Queue (Heap): Insert and extract are O(log n).
   • Common Pitfall: Assuming a priority queue is O(1) like a queue.

6. Edge Cases:

   • Empty Queue: Handle front == -1 in circular queues.
   • Full Queue: Check (rear + 1) % MAX == front for circular queues.
   • Priority Queue: What if two elements have the same priority? (Use secondary keys like arrival time.)

7. Pseudocode is Key:

   • Exam Format: Often, you’ll be asked to write pseudocode for enqueue/dequeue in a circular queue or heap operations. Practice tracing step-by-step.

---