Queue
A Queue is an ordered list; that follows the First-In-First-Out (FIFO) principle, meaning the first element added to the queue will be the first one to be removed.
Queue Operations
| Operation | Description |
|---|---|
| Enqueue | Add an element to the rear |
| Dequeue | Remove an element from the front |
| Peek/Front | Get the front element without removing |
| isEmpty | Check if the queue is empty |
| Size | Get the number of elements |
It can be implemented using arrays, linked lists, or other data structures
Types of Queues
- Simple Queue: Standard FIFO queue.
- Circular Queue: Last position is connected back to the first to make a circle, optimizing space.
- Priority Queue: Each element has a priority; elements are served based on priority, not just order.
- Deque (Double-Ended Queue): Insertion and deletion can be done from both ends.
Time and Space Complexity
| Operation | Array/Linked List Implementation |
|---|---|
| Enqueue | O(1) |
| Dequeue | O(1) |
| Peek | O(1) |
| isEmpty | O(1) |
Space complexity is O(n), where n is the number of elements in the queue.