Types of Queues
A queue is a linear data structure that follows the FIFO (First-In, First-Out) principle.
However, depending on how elements are inserted, removed, or prioritized, queues are classified into different types.
The main types of queues are:
- Linear Queue (Simple Queue)
- Circular Queue
- Priority Queue
- Double-Ended Queue (Deque)
Each type is designed to solve specific limitations or suit particular applications.
1. Linear Queue (Simple Queue)
A linear queue is the basic form of queue where elements are inserted at the rear and removed from the front following FIFO order.
Characteristics:
- Follows strict FIFO principle
- Insertion only at rear
- Deletion only from front
- Easy to implement
Operations:
- Enqueue → Insert at rear
- Dequeue → Remove from front
- Peek → View front element
Limitation:
- Memory wastage problem
- After several deletions, empty spaces at the beginning cannot be reused
- Leads to inefficient utilization in array implementation
Example:
- Queue: [10, 20, 30]
- After removing 10 → [_, 20, 30] (empty space wasted)
Real-World Applications:
- Printer job scheduling
- Call center queues
- Basic CPU scheduling
2. Circular Queue
A circular queue is an improved version of a linear queue where the last position is connected back to the first position, forming a circle.
Characteristics:
- Eliminates memory wastage
- Rear wraps around using modulo operation
- Efficient use of space
Working Concept:
- When rear reaches the end, it moves to the beginning if space is available
Operations:
- Same as linear queue (Enqueue, Dequeue, Peek)
- Uses modulo (%) for circular movement
Example:
- Queue size = 5
- [10, 20, 30, _, _]
- After deletions and insertions → space is reused
Real-World Applications:
- CPU scheduling (Round Robin)
- Traffic signal control systems
- Streaming buffers
3. Priority Queue
In a priority queue, elements are not processed strictly by arrival time.
Instead, each element has a priority, and higher-priority elements are served first.
Characteristics:
- Order depends on priority, not FIFO
- If priorities are equal → FIFO is followed
- Useful in decision-based systems
Types:
- Min Priority Queue → smallest value has highest priority
- Max Priority Queue → largest value has highest priority
Operations:
- Insert → add element with priority
- Delete → remove highest priority element
- Peek → view highest priority element
Example:
- Insert: (A, priority 2), (B, priority 1)
- Dequeue: B comes first (higher priority)
Real-World Applications:
- Operating system scheduling
- Emergency services (hospital triage)
- Dijkstra’s shortest path algorithm
- Data compression (Huffman coding)
4. Double-Ended Queue (Deque)
A deque (double-ended queue) allows insertion and deletion from both ends.
Characteristics:
- More flexible than simple queue
- Can behave like both stack and queue
- Operations allowed at both front and rear
Operations:
- Insert at front (enqueueFront)
- Insert at rear (enqueueRear)
- Delete from front (dequeueFront)
- Delete from rear (dequeueRear)
- Peek front and rear
Types of Deque:
- Input-Restricted Deque
- Insertion allowed only at one end
- Deletion allowed at both ends
- Output-Restricted Deque
- Deletion allowed only at one end
- Insertion allowed at both ends
Example:
- Insert 10 at rear → [10]
- Insert 5 at front → [5, 10]
- Remove from rear → [5]
Real-World Applications:
- Undo/Redo operations
- Browser history navigation
- Task scheduling systems
- Implementing both stack and queue
Summary Table
| Queue Type | Key Idea | Advantage | Limitation |
|---|---|---|---|
| Linear Queue | FIFO, simple structure | Easy to implement | Memory wastage |
| Circular Queue | Circular structure | Efficient space utilization | Slightly complex logic |
| Priority Queue | Based on priority | Handles important tasks first | Not purely FIFO |
| Deque | Insert/delete from both ends | Highly flexible | More complex implementation |
Conclusion
Different types of queues are designed to solve different real-world problems:
- Linear Queue → simple and basic
- Circular Queue → fixes memory issues
- Priority Queue → handles importance-based processing
- Deque → provides maximum flexibility
Was this article helpful?