Queue
A queue is a linear data structure that follows the First-In, First-Out (FIFO) principle, where the first element added is the first one to be removed.
Fundamental Concepts
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 Comparison
Queue Types
| Operation | Linear Queue | Circular Queue | Priority Queue (Heap) | Deque | Explanation |
|---|---|---|---|---|---|
| Enqueue | O(1) | O(1) | O(log n) | O(1) | Insert element |
| Dequeue | O(1) | O(1) | O(log n) | O(1) | Remove element |
| Peek / Front | O(1) | O(1) | O(1) | O(1) | View front |
| Rear access | O(1) | O(1) | — | O(1) | View last |
| Search | O(n) | O(n) | O(n) | O(n) | Scan elements |
| Traversal | O(n) | O(n) | O(n) | O(n) | Visit all |