Queue
easyTwo indices, neither ever moving backwards. It looks trivial until you implement it on an array and discover that shifting on every dequeue makes a full drain O(n²).
O(1) enqueue/dequeueSpace O(n)Saved in this browser - no sign-up, nothing sent anywhere.
How queue works
A queue is two indices over storage: front marks the oldest element, rear marks where the next arrival lands. enqueue writes at rear and advances it; dequeue reads at front and advances that. Neither index ever moves backwards, nothing ever shifts, and that is the entire reason both operations are O(1).
It looks too simple to get wrong, and then you implement it on a Python list. list.pop(0) shifts every remaining element down one slot - O(n) per call - so draining a full queue that way costs O(n²). collections.deque, a ring buffer, or two stacks are the real implementations.
First in, first out is fairness: elements leave in exactly the order they arrived. That is why queues sit wherever work must wait its turn - BFS frontiers, task schedulers, and buffering between a producer and a consumer that run at different speeds.
Step by step
- Start holding 14, 27, 8. front points at 14, the oldest element; rear sits just past 8.
- enqueue(52): write 52 at rear and advance rear. front does not move; size is now four.
- dequeue: return 14 - first in, first out - and advance front to 27. Not one element shifted.
- dequeue again: 27 leaves. The slots behind front now sit dead - the waste a circular queue exists to reclaim.
- Drain the rest: 8, then 52. Arrival order in, identical order out, every operation O(1).
Complexity
| Worst case time | O(1) enqueue/dequeue |
|---|---|
| Space | O(n) |
Reference implementation
Python
from collections import deque
q = deque()
q.append(x) # enqueue at the back - O(1)
x = q.popleft() # dequeue from the front - O(1)
# Never use a list for a queue: list.pop(0) is O(n),
# because every remaining element shifts down one slot.JavaScript
const stack = [];
stack.push(x); // O(1)
const top = stack.at(-1);
stack.pop(); // O(1)
// Array.shift() is O(n) - for a real queue use two stacks,
// a ring buffer, or a linked list.Worth noticing
Two indices, and neither ever goes backwards
front only rises, rear only rises. Nothing shifts, which is what keeps both ends O(1) - and also what wastes the space behind front, the problem a circular queue exists to fix.
`list.pop(0)` is the classic performance bug
It looks like a dequeue but it shifts every remaining element - O(n) per call, O(n²) for a full drain. Use a deque, a ring buffer, or two stacks.
Common pitfalls
- list.pop(0) in Python or Array.shift() in JavaScript: each call shifts every remaining element, turning a full drain into O(n²).
- Dequeueing from empty: a sentinel, an exception, or garbage - pick the behaviour deliberately and guard for it.
- On a plain array the region behind front is never reused, so a long-lived queue leaks capacity until wrapped into a ring.
- Mixing up the ends: enqueue at the front and FIFO silently becomes LIFO - tests that only check contents will miss it.
Where it is used
- BFS - the frontier is a queue, which is exactly what makes the traversal level-by-level.
- Task and job schedulers, where fairness means first submitted, first run.
- Producer and consumer pipelines, buffering between components that run at different speeds.
- Print spoolers and request queues - anywhere arrival order is the contract.
Frequently asked questions
What is the time complexity of queue operations?
enqueue and dequeue are both O(1) worst case: one writes at rear, the other reads at front, and each just advances its own index. Space is O(n) for n queued elements. The O(1) holds only for proper implementations - array shifting breaks it.
Why is list.pop(0) bad for queues in Python?
It looks like a dequeue but it shifts every remaining element down one slot - O(n) per call, O(n²) to drain a full queue. Use collections.deque, whose popleft is O(1), or a ring buffer, or the two-stack construction.
What is the difference between a queue and a stack?
Which end removal touches. A stack pops the newest element - last in, first out. A queue dequeues the oldest - first in, first out. Both offer O(1) operations; the orderings are opposite, and swapping one for the other turns BFS into DFS.
How do you implement a queue with two stacks?
Push arrivals onto an in-stack. To dequeue, pop everything from the in-stack onto an out-stack when the out-stack is empty, then pop it - the double reversal restores arrival order. Each element moves at most twice, so operations are amortised O(1).