Time Complexity of Queue Operations

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 count variable.
• Average Case – O(1): Size doesn't require scanning the entire queue.
• Worst Case – O(1): Always constant time unless specifically implemented otherwise.