Queue
A linear data structure that follows the First-In, First-Out (FIFO) principle, where insertion happens at the rear and deletion happens from the front.
Types of Queues
1️⃣ Linear Queue
A queue where elements are added at the rear and removed from the front, following FIFO.
Example: Waiting line.
2️⃣ Circular Queue
A queue where the last position connects back to the first, reusing empty space.
Use Case: Used to avoid wasted memory.
3️⃣ Priority Queue
A queue where elements are served based on priority, not arrival order.
Example: Emergency patients in a hospital.
4️⃣ Double-Ended Queue
A queue where insertion and deletion can happen at both front and rear.
Key Feature: Flexible structure.
FIFO Principle (First-In, First-Out)
FIFO means the first element added to a collection is the first one to be removed.
Enqueue
Enqueue adds an element to the back (or end) of the queue, with O(1) time complexity.
Dequeue
Dequeue removes the front element from the queue, with O(1) time complexity.
Peek
Peek returns the front element without removing it, with O(1) time complexity.
Search
Search must check each element from the front, resulting in O(n) time complexity.
Time Complexity
| Operation | Time Complexity | Notes |
|---|---|---|
| Enqueue | O(1) | Add element to the rear |
| Dequeue | O(1) | Remove element from the front |
| Peek | O(1) | View front element without removal |
| Search | O(n) | Requires scanning from the front |
| Traversal | O(n) | Requires visiting all elements |
When to Use Queues
- Processing tasks in the order they were received, like a printer queue.
- Implementing Breadth-First Search (BFS) in graph and tree traversal algorithms.
- Managing requests in a web server or tasks in an operating system scheduler.
- Buffering data in streams (e.g., video streaming) where data is processed in the order it arrives.