Queues: The FIFO Structure
Definition: A Queue is a linear data structure that permits insertion at one end (Rear) and deletion at the other end (Front). Principle: FIFO (First In, First Out). Think of a line at a ticket counter; the first person in line is the first served.
Queue Operations & Complexity
| Operation | Description | Pointer Action | Time |
|---|---|---|---|
| Enqueue | Add element at Rear | Rear = Rear + 1 | O(1) |
| Dequeue | Remove element at Front | Front = Front + 1 | O(1) |
| Front/Peek | View front element | — | O(1) |
| isEmpty | Check if queue is empty | Front > Rear | O(1) |
| isFull | Check if queue is full | Rear == MAX - 1 | O(1) |
Limitations of Linear Queue — The "False Full" Problem
After multiple Enqueue/Dequeue operations, Rear reaches the end of the array, but empty spaces exist at the beginning. The queue appears full when it's not!
Example:
Initial: [10, 20, 30, _, _] Front=0, Rear=2
Dequeue 2: [_, _, 30, _, _] Front=2, Rear=2
Enqueue: [_, _, 30, 40, 50] Front=2, Rear=4 (FULL!)Positions 0 and 1 are wasted! Solution: Circular Queue.
Circular Queue — The Fix
Key Formula: Next Position = (Current + 1) % MAX_SIZE
This wraps the Rear pointer back to position 0 after reaching the end.
Worked Example (Size = 5):
| Operation | Front | Rear | Queue State |
|---|---|---|---|
| Enqueue(10) | 0 | 0 | [10, _, _, _, _] |
| Enqueue(20) | 0 | 1 | [10, 20, _, _, _] |
| Enqueue(30) | 0 | 2 | [10, 20, 30, _, _] |
| Dequeue() → 10 | 1 | 2 | [_, 20, 30, _, _] |
| Dequeue() → 20 | 2 | 2 | [_, _, 30, _, _] |
| Enqueue(40) | 2 | 3 | [_, _, 30, 40, _] |
| Enqueue(50) | 2 | 4 | [_, _, 30, 40, 50] |
| Enqueue(60) | 2 | 0 | [60, _, 30, 40, 50] ← Wraps! |
Full Condition: (Rear + 1) % SIZE == Front Empty Condition: Front == -1 (or Front == Rear + 1 after dequeue)
Queue Variations — Comparison
| Variation | Insert | Delete | Ordering | Use Case |
|---|---|---|---|---|
| Linear Queue | Rear only | Front only | FIFO | Basic task scheduling |
| Circular Queue | Rear (wraps) | Front (wraps) | FIFO | Memory-efficient buffering |
| Deque (Double-Ended) | Both ends | Both ends | Flexible | Sliding window, undo/redo |
| Priority Queue | By priority | Highest priority first | Priority | Dijkstra's, CPU scheduling |
Deque (Double-Ended Queue)
Definition: Insertion and deletion can be performed at both ends.
| Type | Insert | Delete |
|---|---|---|
| Input Restricted | ONE end only | Both ends |
| Output Restricted | Both ends | ONE end only |
Priority Queue
Definition: Every element has an associated priority value. Elements are dequeued based on priority, not arrival time.
| Type | Rule | Example |
|---|---|---|
| Ascending (Min-Priority) | Smallest value = Highest priority | Emergency room triage (severity 1 first) |
| Descending (Max-Priority) | Largest value = Highest priority | VIP queue (highest rank first) |
Tie-Breaking: If two items have the same priority, FIFO order is used.
Real-World Applications of Queues
| Application | Queue Type Used |
|---|---|
| CPU Scheduling | Priority Queue (OS processes) |
| Print Spooler | Linear Queue (first document prints first) |
| BFS Graph Traversal | Linear Queue |
| Keyboard Buffer | Circular Queue (fixed-size input buffer) |
| Dijkstra's Algorithm | Min-Priority Queue |
| Streaming Buffer | Circular Queue (audio/video buffering) |
| Call Center | Priority Queue (VIP customers first) |