Queues follow the First-In First-Out (FIFO) principle, which determines how elements are inserted and removed. Each operation — like enqueue, dequeue, or checking the front — typically has a constant-time complexity, making queues efficient for ordered data processing. In this guide, we explore the time complexities of five core queue operations.
Summary Table
| Operation | Best Case | Average Case | Worst Case |
|---|---|---|---|
| Enqueue | O(1) | O(1) | O(1) |
| Dequeue | O(1) | O(1) | O(1) |
| Peek | O(1) | O(1) | O(1) |
| isEmpty | O(1) | O(1) | O(1) |
| Size | O(1) | O(1) | O(1) |
1. Enqueue
The enqueue operation adds an element to the rear of the queue.
- Best Case – O(1): The element is added directly at the rear with no shifting or restructuring.
- Average Case – O(1): Most implementations (arrays with rear pointers or linked lists) support enqueue in constant time.
- Worst Case – O(1): Even with dynamic resizing (amortized), the enqueue operation is still O(1) in typical use cases.
2. Dequeue
The dequeue operation removes an element from the front of the queue.
- Best Case – O(1): The front element is removed instantly, often by moving a front pointer forward.
- Average Case – O(1): Linked-list-based or circular queue implementations maintain O(1) for all cases.
- Worst Case – O(1): Even in array-based queues, shifting can be avoided using circular logic or a moving front index.
3. Peek
The peek operation retrieves the front element without removing it.
- Best Case – O(1): Direct access to the front pointer gives immediate value.
- Average Case – O(1): Constant-time lookup regardless of queue size.
- Worst Case – O(1): Always O(1) in well-implemented queues.
4. isEmpty
The isEmpty operation checks whether the queue is empty.
- Best Case – O(1): A single pointer or size check determines emptiness.
- Average Case – O(1): Same across all queue sizes and states.
- Worst Case – O(1): Always constant-time as it doesn’t depend on elements.
5. Size
The size operation returns the number of elements in the queue.
- Best Case – O(1): Most implementations maintain a
countvariable. - Average Case – O(1): Size doesn't require scanning the entire queue.
- Worst Case – O(1): Always constant time unless specifically implemented otherwise.