Time complexity of queue operations
Queue ADT operations are usually O(1) per step for standard implementations. Costs change when you use a dynamic array (occasional O(n) resize) or a heap priority queue (O(log n) insert/remove).
On this page
- Typical operations — enqueue, dequeue, peek
- By implementation — array, circular, linked list, heap
- Amortized analysis — dynamic array growth
- Quick reference table
1) Operations we measure
| Operation | Meaning | Notes |
|---|---|---|
enqueue | Add at rear | May fail if capacity fixed and full |
dequeue | Remove from front | Underflow if empty |
peek / front | Read front without removing | O(1) when front index/pointer known |
2) Complexity by implementation
| Implementation | Enqueue | Dequeue | Peek |
|---|---|---|---|
Linked list (front/rear) | O(1) | O(1) | O(1) |
Circular array (fixed N) | O(1) | O(1) | O(1) |
| Linear array (shift elements) | O(1)* | O(n) | O(1) |
| Dynamic circular array | O(1) amortized | O(1) amortized | O(1) |
| Min-/max-heap priority queue | O(log n) | O(log n) | O(1) |
*Enqueue at end O(1) if unused slot; naive linear-array dequeue without circular indexing shifts O(n).
3) Amortized cost (dynamic array)
When the array doubles in size, copying takes O(n), but that happens rarely enough that the average cost per enqueue stays O(1) (aggregate over many pushes). Same idea applies to shrink-if-mostly-empty policies.
4) Quick reference
| Question | Answer |
|---|---|
| Best queue for strict FIFO O(1)? | Linked list or circular array. |
| Priority by value? | Binary heap: push/pop in O(log n). |
| BFS on graph? | Queue holds frontier; each vertex/edge handled once → O(V + E) total, not per queue op. |
Related lessons
- Circular queue — O(1) without shifting.
- Linked-list queue — O(1) enqueue/dequeue.
- Priority queue (heap) — O(log n) insert/extract.
Key takeaway
State the implementation when you give Big-O: “queue” alone is ambiguous. Circular/linked queues are O(1); heaps add a log factor for priority.
Next up: Space complexity · BFS using queue · All queue topics