0% completed
Queues come in different variations based on how elements are inserted, removed, and prioritized. While all queues follow the First-In, First-Out (FIFO) principle, some variations modify the insertion and removal rules to suit different use cases.
Let’s explore the main types of queues and understand their applications.
1. Simple Queue (Linear Queue)
A simple queue is the most basic form of a queue. It follows the FIFO (First-In, First-Out) rule, meaning:
- New elements are added at the rear.
- Elements are removed from the front.
Representation:
Front → [ 10, 20, 30, 40 ] → Rear Enqueue(50) → [ 10, 20, 30, 40, 50 ] Dequeue() → [ 20, 30, 40, 50 ] (10 is removed)
Key Properties:
✔ Follows FIFO order.
✔ Simple to implement using arrays or linked lists.
✔ Used in task scheduling and request processing.
2. Circular Queue
A circular queue is a variation where the last position is connected back to the first. This eliminates the need for shifting elements and efficiently utilizes available memory.
Why Use a Circular Queue?
A simple queue can result in wasted space when elements are dequeued. A circular queue reuses positions efficiently.
Representation:
[ _, _, 30, 40, 50 ] (Front = 2, Rear = 4) Enqueue(60) → [ 60, _, 30, 40, 50 ] (Front = 2, Rear = 0)
Key Properties:
✔ Prevents wastage of space in array-based queues.
✔ More efficient for buffer management.
✔ Used in CPU scheduling, memory allocation, and buffering in networking.
3. Deque (Double-Ended Queue)
A deque (Double-Ended Queue) allows insertion and deletion from both ends:
- Front Insertion & Rear Insertion (Enqueue).
- Front Removal & Rear Removal (Dequeue).
Representation:
Deque: [ 10, 20, 30, 40 ] EnqueueFront(5) → [ 5, 10, 20, 30, 40 ] EnqueueRear(50) → [ 5, 10, 20, 30, 40, 50 ] DequeueFront() → [ 10, 20, 30, 40, 50 ] (5 is removed) DequeueRear() → [ 10, 20, 30, 40 ] (50 is removed)
Types of Deques:
- Input-Restricted Deque → Insertion allowed only at one end, but deletion at both ends.
- Output-Restricted Deque → Deletion allowed only at one end, but insertion at both ends.
Key Properties:
✔ Provides more flexibility than a simple queue.
✔ Used in sliding window problems, undo operations, and task scheduling.
4. Priority Queue
A priority queue assigns a priority to each element, and elements are dequeued based on their priority rather than their arrival order.
How It Works:
- Higher priority elements are dequeued first, regardless of when they were enqueued.
- Can be implemented using heaps for efficient insertion and deletion.
Representation:
Priority Queue: [(3, "Task A"), (1, "Task B"), (2, "Task C")] Dequeue() → "Task B" (Lowest number = highest priority) Queue after removal: [(3, "Task A"), (2, "Task C")]
Key Properties:
✔ Not strictly FIFO (processed based on priority).
✔ Used in operating systems (process scheduling), networking (packet scheduling), and Dijkstra’s algorithm.
5. Affinity Queue
An Affinity Queue groups elements based on a shared property (affinity). It ensures that:
- Elements with the same affinity are grouped together.
- If no matching affinity is found, the element is placed at the rear.
Example Use Case:
In multi-threading, tasks from the same thread/process are scheduled closely together for better efficiency.
Representation:
Affinity Queue: [ (A, 10), (A, 20), (B, 30), (B, 40) ] Enqueue(A, 25) → [ (A, 10), (A, 20), (A, 25), (B, 30), (B, 40) ]
Key Properties:
✔ Improves cache locality and system efficiency.
✔ Used in thread scheduling, data processing, and database transactions.
Comparison of Queue Types
| Queue Type | FIFO? | Special Feature | Common Use Case |
|---|---|---|---|
| Simple Queue | ✅ Yes | Basic FIFO queue | Task scheduling, request processing |
| Circular Queue | ✅ Yes | Last position connects to first | Memory-efficient queueing |
| Deque | ❌ No | Insert/remove from both ends | Undo operations, sliding window problems |
| Priority Queue | ❌ No | Elements dequeued based on priority | CPU scheduling, Dijkstra’s algorithm |
| Affinity Queue | ✅ Yes | Groups elements by shared properties | Thread scheduling, multi-threaded task processing |
.....
.....
.....
Table of Contents
Contents are not accessible
Contents are not accessible
Contents are not accessible
Contents are not accessible
Contents are not accessible