Types of Queues
There are four kinds of Queues:
1. Simple Queue (Linear Queue)
Follows the First-In, First-Out (FIFO) principle. The element enqueued (added) first is the one dequeued (removed) first.
Operations
- Enqueue: Adds an element to the rear (end) of the queue.
- Dequeue: Removes an element from the front (beginning) of the queue.
- Peek (or Front): Allows you to view the element at the front of the queue without removing it.
Implementation: Can be implemented using arrays or linked lists.
Limitations: In array-based implementations, once the rear reaches the end of the array, even if there are empty slots at the beginning (due to dequeues), you cannot insert new elements. This leads to inefficient memory utilization.
Real-world Examples
- Managing print jobs.
- Handling requests on a single shared resource (like CPU scheduling in a basic manner).
- Call center queues.
2. Circular Queue (Ring Buffer)
A modification of the simple queue where the last position is connected back to the first position, forming a circle. This overcomes the space wastage issue in linear queues.
Operations: Similar to a simple queue (Enqueue, Dequeue, Peek), but the rear pointer wraps around to the beginning of the array if there's space available.
Implementation: Typically implemented using arrays with the help of the modulo operator (%) to handle the circular nature of the indices.
Real-world Examples
- CPU scheduling (round-robin approach).
- Traffic signal systems.
- Buffer management in streaming media.
3. Priority Queue
Elements in a priority queue are associated with a priority. The element with the highest priority is dequeued before elements with lower priority, regardless of the order of insertion.
If elements have the same priority, they are typically dequeued based on their order of arrival (FIFO).
Types of Priority Queue
- Ascending Priority Queue (Min-Priority Queue): Elements with the smallest value have the highest priority.
- Descending Priority Queue (Max-Priority Queue): Elements with the largest value have the highest priority.
Operations
- Enqueue (Insert): Adds an element with an associated priority.
- Dequeue (Remove): Removes and returns the element with the highest priority.
- Peek (or Get Highest Priority): Views the element with the highest priority without removing it.
Implementation: Commonly implemented using heaps (binary heaps are efficient for this), but can also be implemented using arrays, linked lists, or balanced binary search trees.
Real-world Examples
- Operating system task scheduling (prioritizing critical tasks).
- Emergency room triage (patients are treated based on the severity of their condition).
- Dijkstra's shortest path algorithm.
- Huffman coding for data compression.
4. Double-Ended Queue (Deque)
A deque allows insertion and deletion of elements from both the front (head) and the rear (tail). It's a generalization of a queue and a stack.
Operations
- EnqueueFront (or AddFront): Adds an element to the front.
- EnqueueRear (or AddRear): Adds an element to the rear.
- DequeueFront (or RemoveFront): Removes an element from the front.
- DequeueRear (or RemoveRear): Removes an element from the rear.
- PeekFront (or GetFront): Views the element at the front without removing it.
- PeekRear (or GetRear): Views the element at the rear without removing it.
Types (based on restrictions)
- Input-Restricted Deque: Insertion is allowed only at one end, but deletion is allowed from both ends.
- Output-Restricted Deque: Deletion is allowed only at one end, but insertion is allowed from both ends.
- Implementation: Can be implemented using doubly linked lists or arrays (with careful management of indices, potentially using a circular approach for efficiency).
Real-world Examples
- Undo/redo functionality in software.
- Web browser history (can add to front or rear, remove from front or rear).
- Implementing both stacks and queues with a single data structure.