7. Queue

Queue Fundamentals

A queue is a linear data structure that follows the First‑In‑First‑Out (FIFO) principle. Elements are added at the rear and removed from the front. The primary operations are:

• enqueue(x) – inserts element x at the rear.
• dequeue() – removes and returns the element at the front.
• front() – returns the front element without removing it.
• rear() – returns the rear element without removing it.
• isEmpty() – checks whether the queue contains any elements.

In an efficient implementation each of these runs in O(1) time.

Circular Queue

A circular queue improves space utilisation by treating the underlying array as a ring. When the rear index reaches the end of the array it wraps around to the beginning using modulo arithmetic.

Key Formulas

• Advance rear: rear = (rear + 1) % capacity
• Advance front: front = (front + 1) % capacity
• Number of elements (using a count variable): size = (rear - front + capacity) % capacity when a count is not stored.

To differentiate between empty and full states we either keep an explicit count variable or sacrifice one array slot (i.e., the queue is considered full when (rear + 1) % capacity == front).

Operations (O(1))

1. Enqueue: if not full, place x at array[rear], then update rear with the formula above.
2. Dequeue: if not empty, retrieve array[front], then update front similarly.
3. Front / Rear: return array[front] or array[rear] without modification.
4. isEmpty: true when count == 0 (or front == rear when using the sacrificed‑slot method).

Example

Consider a circular queue of capacity 5.

Initial: front = 0, rear = 0, count = 0 (empty)
enqueue(10) → array[0]=10, rear=1, count=1
enqueue(20) → array[1]=20, rear=2, count=2
dequeue()   → returns 10, front=1, count=1
enqueue(30) → array[2]=30, rear=3, count=2
enqueue(40) → array[3]=40, rear=4, count=3
enqueue(50) → array[4]=50, rear=0 (wrap), count=4
enqueue full → array[0]=60, rear=1, count=5 (now full)

Attempting another enqueue would fail because (rear + 1) % capacity == front (both equal 1).

Priority Queue

A priority queue removes elements based on priority rather than insertion order. The highest (or lowest) priority element is always at the front.

Underlying Structures

• Binary Heap – complete binary tree stored in an array; provides O(log n) insert and extract‑min/max.
• Balanced BST (e.g., AVL, Red‑Black) – also O(log n) for both operations, with the added ability to find arbitrary elements.
• Fibonacci Heap – amortized O(1) insert and O(log n) extract‑min; useful in algorithms like Dijkstra’s.

Core Operations

1. insert(x, p) – inserts element x with priority p.
2. extractMin() (or extractMax()) – removes and returns the element with smallest (largest) priority.
3. peek() – returns the top priority element without removal.
4. isEmpty() – checks if the queue is empty.

All operations are O(log n) for binary heap and balanced BST; Fibonacci heap improves insert to amortized O(1).

Example (Min‑Heap)

Insert elements with priorities: (5, A), (2, B), (9, C).

1. Insert (5, A) → heap: [A(5)]
2. Insert (2, B) → heap: [B(2), A(5)] (B becomes root)
3. Insert (9, C) → heap: [B(2), A(5), C(9)]
4. extractMin() → returns B(2); heap becomes [A(5), C(9)] after heapify.

Applications

• CPU scheduling (shortest‑job‑first, priority scheduling).
• Graph algorithms (Dijkstra, Prim).
• Event simulation systems.

Deque (Double‑Ended Queue)

A deque allows insertion and removal at both ends, combining the features of stacks and queues.

Operations (O(1) with a dynamic array or linked list)

• insertFront(x) – adds x at the front.
• insertRear(x) – adds x at the rear.
• deleteFront() – removes and returns the front element.
• deleteRear() – removes and returns the rear element.
• peekFront() / peekRear() – view elements without removal.
• isEmpty() – emptiness test.

Implementation Variants

1. Dynamic Array (circular buffer) – similar to circular queue but maintains two pointers; resizing when needed.
2. Doubly Linked List – each node has prev and next pointers; all operations are constant time.

Example (Array‑based deque)

Capacity 4, initially empty.

insertRear(1) → [1]
insertFront(2) → [2, 1]
insertRear(3) → [2, 1, 3]
deleteFront() → returns 2, deque → [1, 3]
insertRear(4) → [1, 3, 4]
deleteRear() → returns 4, deque → [1, 3]

Applications

• Undo‑redo functionality in editors.
• Palindrome checking.
• Job‑stealing schedulers in parallel computing.
• Browser history (back/forward).

Real‑Life Uses of Queues

Queues model many everyday systems where fairness and order of arrival matter.

Summary

This chapter covered the essential queue operations (enqueue, dequeue, front, rear, isEmpty) and their O(1) guarantees. We examined three important variations:

• Circular Queue – array‑based, constant‑time operations with modulo indexing.
• Priority Queue – ordered by priority, logarithmic insert/extract via heaps or BSTs.
• Deque – double‑ended, allowing O(1) inserts/deletes at both ends.

Understanding these structures enables efficient solutions for scheduling, resource allocation, and many real‑world scenarios.