Queues: Operations, Implementations & Applications

Core Concepts

1. Definition & FIFO Principle

A queue is a linear data structure that follows FIFO (First-In-First-Out):

• The first element added is the first to be removed.
• Analogous to a ticket counter (e.g., NTC or Ncell customer service) or a print queue in computers.

graph LR
    A["Enqueue (Insert)"] --> B["Queue: [10, 20, 30]"]
    B --> C["Dequeue (Remove)"] --> D["Queue: [20, 30]"]

Key Terms:

• Front/Head: First element (removed via dequeue).
• Rear/Tail: Last element (added via enqueue).
• Empty Queue: front == -1 (or null in linked lists).

2. Queue Operations

Example: Bank Customer Queue

• Customers arrive (enqueue) and are served (dequeue) in order.
• Visualization:

  flowchart TD
      A["Arrival: Customer A"] --> B["Queue: [A]"]
      B --> C["Arrival: Customer B"] --> D["Queue: [A, B]"]
      D --> E["Serve A"] --> F["Queue: [B]"]
      F --> G["Serve B"] --> H["Queue: []"]

Implementations

1. Array-Based Queue

• Problem: Fixed size; inefficient if resizing is needed.
• Solution: Use circular queue to reuse space.

  flowchart TD
      A["Initial: front=0, rear=-1"] --> B["Enqueue 10: [10|_|_|_]"]
      B --> C["Enqueue 20: [10|20|_|_]"] --> D["Enqueue 30: [10|20|30|_]"]
      D --> E["Dequeue: [20|30|_|_], front=1"] --> F["Enqueue 40: [20|30|40|_]"]

Code Example (C):

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

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

void dequeue() {
    if (front == -1) printf("Queue Empty\n");
    else if (front == rear) front = rear = -1;
    else front++;
}

Trace Table:

2. Linked List-Based Queue

• Advantage: Dynamic size; no wasted space.
• Nodes: Store data + next pointer.

  classDiagram
      class QueueNode {
          +data
          +next
      }
      class Queue {
          +front
          +rear
          +enqueue(x)
          +dequeue()
      }
      QueueNode --> Queue : "linked to"

Code Example (Python):

class QueueNode:
    def __init__(self, data):
        self.data = data
        self.next = None

class Queue:
    def __init__(self):
        self.front = self.rear = None

    def enqueue(self, x):
        new_node = QueueNode(x)
        if self.rear is None:
            self.front = self.rear = new_node
        else:
            self.rear.next = new_node
            self.rear = new_node

Trace Table:

Applications in Real World

1. Pathao/Daraz Order Processing

• How Queues Work:
  • Orders arrive (enqueue) and are processed (dequeue) in sequence.
  • Example: A Daraz delivery queue ensures orders are fulfilled in arrival order, preventing chaos.

2. Printer Spooling (Windows/Linux)

• How Queues Work:
  • Print jobs are added to a queue (enqueue) and printed one by one (dequeue).
  • Visualization:

    flowchart TD
        A["User sends print job"] --> B["Queue: [Job1]"]
        B --> C["User sends Job2"] --> D["Queue: [Job1, Job2]"]
        D --> E["Printer processes Job1"] --> F["Queue: [Job2]"]

3. Call Center (Ncell/NTC)

• How Queues Work:
  • Customer calls are queued (enqueue) and handled in order (dequeue).
  • Example: Ncell’s IVR system uses queues to manage call priority.

Specialized Queues

1. Circular Queue

• Use Case: Efficient space reuse (e.g., traffic light timers).
• Example: A roundabout where vehicles enter and exit in a loop.

2. Priority Queue

• Use Case: Operating systems (process scheduling).
• Example: NEPSE stock trading prioritizes high-value orders.

3. Double-Ended Queue (Deque)

• Use Case: Undo/redo operations (e.g., text editors).
• Example: WhatsApp’s message deletion queue allows reinsertion.

Exam Tip

1. Understand FIFO: Always relate queues to real-world examples (e.g., ticket counters, printer queues).
2. Circular Queue: Know how to handle front and rear pointers to avoid overflow.
3. Time Complexity: Memorize O(1) for enqueue/dequeue in both array and linked list implementations.
4. Code Traces: Practice writing trace tables for operations (e.g., enqueue/dequeue steps).
5. Applications: Link queues to scheduling (OS), buffering (networks), and BFS (graphs).

Key Formula: For a circular queue of size n:

• isFull: (rear + 1) % n == front
• isEmpty: front == -1 (or front == rear + 1 in some implementations).