The Intuition: A Fair Line
Picture a checkout line. Whoever arrives first is served first, and new people join at the back. A queue captures exactly this rule in code: it preserves arrival order. That property — first in, first out — is the entire personality of the structure, and it is the opposite of a stack, which serves the most recent arrival first (last in, first out).
Because order is preserved, queues are the natural choice whenever fairness or arrival-order processing matters: handling requests in the order they came in, replaying events, or visiting things layer by layer. Two ends do the work — you always add at the back and always remove from the front.
The Mechanics: Enqueue, Dequeue, and Peek
A queue exposes four core operations: enqueue (add to the back), dequeue (remove and return the front), peek or front (look at the front without removing it), and isEmpty. Done right, every one of these is O(1) — constant time regardless of how many items are queued.
The implementation you pick decides whether that O(1) holds. A linked list with head and tail pointers works, and so does a deque or a circular buffer. The common mistake is a dynamic array where dequeue removes index 0: that forces every remaining element to shift down, quietly turning an O(1) operation into O(n).
This is why breadth-first search leans on a queue. BFS keeps a queue of the 'frontier' of nodes to visit; dequeuing in FIFO order guarantees you reach nodes in increasing order of distance from the source, which is what makes BFS find shortest paths in unweighted graphs.
Circular Queues and Deques
A circular queue is a fixed-size array whose front and rear indices wrap around with the modulo operator. Instead of shifting elements or growing without bound, it reuses slots that earlier dequeues freed. That makes it perfect for bounded buffers — ring buffers for streaming audio, keyboard input, or producer-consumer pipelines where memory is capped.
A deque (double-ended queue) generalizes the idea by allowing O(1) insertion and removal at both ends. It can act as a stack or a queue, and it powers classic patterns like sliding-window maximum, where you push and pop from both sides. Most languages ship one — Python's collections.deque, Java's ArrayDeque — and it is usually the most practical way to build a queue.
from collections import deque
class Queue:
def __init__(self):
self._items = deque()
def enqueue(self, item): # add to the back
self._items.append(item)
def dequeue(self): # remove from the front
if not self._items:
raise IndexError("dequeue from empty queue")
return self._items.popleft()
def peek(self): # front without removing
if not self._items:
raise IndexError("peek from empty queue")
return self._items[0]
def is_empty(self):
return len(self._items) == 0With a deque, linked list, or circular array, all operations are O(1) in the best, average, and worst case. The classic trap is a dynamic array where you remove from the front (Python's list.pop(0)): that is O(n) because every remaining element shifts down one slot, making a sequence of dequeues quadratic.
When to use it
- Breadth-first search and level-order traversal of trees or graphs, where nodes must be visited in order of distance from the start.
- Scheduling and task processing in arrival order — job queues, print spoolers, message queues, and CPU-style round-robin work.
- Buffering data between a fast producer and a slower consumer, typically with a fixed-size circular (ring) buffer.
- Any 'shortest number of steps' problem on an unweighted grid or graph, where FIFO ordering yields the minimum-step answer.
Watch out for
- Using list.pop(0) in Python (or otherwise shifting an array) to dequeue, which is O(n) per removal and makes a loop of dequeues quadratic — reach for collections.deque or a linked list instead.
- Dequeuing or peeking without first checking whether the queue is empty, which raises an error or returns undefined and crashes the surrounding logic.
- In a fixed-size circular queue, mishandling the full-versus-empty case: when front and rear point to the same slot, you need a count or a spare slot to tell 'empty' from 'full'.
Queues show up constantly in interviews, usually indirectly. The strongest signal is any breadth-first-search problem — level-order tree traversal, shortest path in an unweighted graph, or "minimum number of steps" grid problems — all of which need a queue to process nodes in order of distance from the start. Interviewers also quietly check whether you know that dequeuing from the front of a plain array is O(n), and expect you to reach for a deque or linked list instead. Tougher rounds lean on the double-ended deque variant for sliding-window questions. What they are really testing is whether you choose FIFO deliberately and keep every operation O(1).