Queues and Their Variants: FIFO, Circular, Priority, Double-Ended

TAKEAWAYS

• A queue enforces FIFO order, where the first inserted element is the first to be removed (unlike stacks, which use LIFO).
• Circular queues optimize memory by reusing the last slot after the end, avoiding fixed-size limits.
• Priority queues serve elements based on priority (e.g., emergency calls before routine calls), implemented via heaps or linked lists.
• Dequeues (double-ended queues) allow insertion/deletion at both ends, useful for palindrome checks or undo/redo operations.
• Time complexity for basic operations (enqueue/dequeue) is O(1) for arrays/linked lists, but O(log n) for priority queues (heap-based).
• Real-world examples include bank queues (FIFO), operating system process scheduling (priority queues), and Daraz order processing (FIFO for delivery).

---

1. Introduction to Queues

A queue is a linear data structure that follows the First-In-First-Out (FIFO) principle. The last element inserted is the first to be removed, unlike stacks (LIFO). Queues are used in scenarios where order matters, such as:

• Bank teller lines (customers wait in order).
• Print queues (documents print in submission order).
• CPU task scheduling (processes run in arrival order).

Key Operations

---

Array Implementation

Example Trace (Array Queue):

Code Example (Array Queue in C):

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

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

int dequeue() {
    if (front == -1) { printf("Empty\n"); return -1; }
    int x = queue[front];
    if (front == rear) front = rear = -1;
    else front++;
    return x;
}

Problem: Fixed size limits queue capacity. Solution: Circular Queue.

---

2. Circular Queue

A circular queue reuses the empty slots after the rear, eliminating the need for a fixed-size array. It wraps around using modulo arithmetic.

Operations

• Enqueue: If rear is at the last index, move to front - 1.
• Dequeue: If front is at the last index, move to 0.
• Full Condition: (rear + 1) % MAX == front
• Empty Condition: front == -1 (or front == rear for non-empty check).

Visualization

Example Trace (Circular Queue):

Code Example (Circular Queue in C):

void enqueue(int x) {
    if ((rear + 1) % MAX == front) printf("Full\n");
    else {
        if (front == -1) front = 0;
        rear = (rear + 1) % MAX;
        queue[rear] = x;
    }
}

int dequeue() {
    if (front == -1) { printf("Empty\n"); return -1; }
    int x = queue[front];
    if (front == rear) front = rear = -1;
    else front = (front + 1) % MAX;
    return x;
}

Advantages:

• No wasted space (unlike linear queues).
• Efficient memory usage.

Disadvantages:

• Slightly complex implementation (modulo arithmetic).

---

3. Priority Queue

A priority queue serves elements based on priority (e.g., emergency calls before routine calls). Priorities can be:

• Numerical (higher number = higher priority).
• Alphabetical (e.g., 'A' > 'B').

Operations

Implementation Methods

1. Array-Based (Unsorted):
   • Insertion: O(1).
   • Deletion: O(n) (linear search).
2. Linked List-Based (Sorted):
   • Insertion: O(n) (find position).
   • Deletion: O(1) (head removal).
3. Heap-Based (Binary Heap):
   • Insertion: O(log n).
   • Deletion: O(log n).

Example: Heap-Based Priority Queue

Trace (Heap Insertions):

1. Insert 3 (priority 2):

       3
   

2. Insert 1 (priority 1):

       3
      /
     1
   

3. Insert 2 (priority 3):

       2
      / \
     3   1
   

4. deleteMax(): Returns 2 (priority 3), heap becomes:

       3
      /
     1
   

Code Example (Heap-Based Priority Queue in C):

typedef struct {
    int data;
    int priority;
} Element;

void heapifyUp(Element arr[], int i) {
    while (i > 0 && arr[(i - 1) / 2].priority < arr[i].priority) {
        swap(arr[i], arr[(i - 1) / 2]);
        i = (i - 1) / 2;
    }
}

void insert(Element arr[], int *size, Element x) {
    arr[*size] = x;
    heapifyUp(arr, *size);
    (*size)++;
}

Real-World Example:

• NTC/Ncell Call Center: Emergency calls (priority 1) are handled before routine calls (priority 2).
• Operating Systems: Processes with higher priority (e.g., real-time tasks) run before lower-priority tasks.

---

4. Double-Ended Queue (Deque)

A deque (double-ended queue) allows insertion/deletion at both ends. Use cases:

• Palindrome checks (e.g., "madam").
• Undo/redo operations (e.g., text editors).
• Browser history (add/remove from both ends).

Operations

Visualization

Example Trace (Deque):

Code Example (Deque in C):

#define MAX 3
int deque[MAX], front = -1, rear = -1;

void addFront(int x) {
    if ((front == 0 && rear == MAX - 1) || (front == rear + 1)) printf("Full\n");
    else {
        if (front == -1) front = rear = 0;
        else if (front == 0) front = MAX - 1;
        else front--;
        deque[front] = x;
    }
}

int removeFront() {
    if (front == -1) { printf("Empty\n"); return -1; }
    int x = deque[front];
    if (front == rear) front = rear = -1;
    else front = (front + 1) % MAX;
    return x;
}

Advantages:

• Flexible insertion/deletion at both ends.
• Efficient for palindrome checks (O(n) time).

Disadvantages:

• More complex than a regular queue.

---

5. Comparison of Queue Variants

---

6. Applications of Queues

In the Real World

1. Daraz Order Processing:

   • Idea: FIFO queue for delivery orders.
   • How: Orders are processed in the sequence they are received. The first order placed gets the first delivery slot.
   • Worked Example:
     • Order 101 (placed at 10:00 AM) → Delivered at 12:00 PM.
     • Order 102 (placed at 10:05 AM) → Delivered at 12:15 PM.
     • Queue state after 2 orders:

       Front: 101 (rear: 102)
       

2. Pathao Ride Allocation:

   • Idea: Priority queue for ride requests.
   • How: Emergency rides (priority 1) are allocated before regular rides (priority 2).
   • Worked Example:
     • Ride 501 (priority 2) → Waits.
     • Ride 502 (priority 1) → Allocated immediately.

3. NEPSE Stock Trading:

   • Idea: FIFO queue for buy/sell orders.
   • How: Orders are executed in the order they are received to ensure fairness.
   • Worked Example:
     • Buy order for 100 shares at ₹500 → Executed before a later buy order at the same price.

---

7. Exam Tip

• Focus Areas:
  • Definitions: Clearly explain FIFO vs. LIFO (stacks).
  • Operations: Practice enqueue, dequeue, peek on arrays/linked lists.
  • Circular Queue: Master modulo arithmetic for wrap-around logic.
  • Priority Queue: Know heap-based vs. array-based implementations.
  • Deque: Understand bidirectional operations (e.g., palindrome check).
• Common Mistakes:
  • Forgetting to update front/rear pointers in circular queues.
  • Confusing isEmpty() and isFull() conditions.
  • Misapplying priority logic (e.g., max-heap vs. min-heap).
• Problem-Solving Tips:
  • Draw the queue state after each operation (examiners love visual traces).
  • For priority queues, always clarify whether it’s a max-heap or min-heap.
  • For deques, think of real-world examples (e.g., "How would you implement an undo button?").

---

Visual Summary: