What is a Queue?
Data Structures·6 min read·code in python
A queue is a linear data structure that stores items in first-in, first-out (FIFO) order: you add elements at the back (enqueue) and remove them from the front (dequeue). Like a line at a checkout, the earliest arrival is served first. Queues power breadth-first search, task scheduling, and buffering.
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.
The code
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) == 0Run it in the browser IDE, free on the platform. Open the IDE
Complexity
| Time | Enqueue, dequeue, peek, and isEmpty are all O(1). |
|---|---|
| Space | O(n) to hold n stored elements. |
With 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'.
Queue: questions we get
What is the time complexity of a queue?
Enqueue, dequeue, and peek are all O(1) when the queue is backed by a linked list, a deque, or a circular array. Space is O(n) for n elements. The only way to accidentally make it O(n) is by removing from the front of a plain dynamic array, which shifts every remaining element.
What is the difference between a stack and a queue?
A queue is FIFO: the first item added is the first removed, like people in a line. A stack is LIFO: the last item added comes out first, like a stack of plates. Queues drive breadth-first search; stacks drive depth-first search and recursion.
Why shouldn't I use a Python list as a queue?
list.append is O(1), but list.pop(0) is O(n) because Python shifts every remaining element one position left. Over many dequeues this turns your queue quadratic. Use collections.deque instead, whose popleft is genuine O(1).
Is a queue hard to learn?
No: FIFO is one of the most intuitive structures because it mirrors an everyday line. The subtle parts are picking an implementation that keeps dequeue at O(1) and getting circular-queue wrap-around right. It tends to click fast once you watch enqueue and dequeue animate step by step.
Related concepts
Reading is the easy part. In a batch you build it, say it out loud in a scored mock round and hear what an interviewer would think.
Talk to mentor