Queues
A queue is a First-In-First-Out (FIFO) data structure. It perfectly models real-world lines, ensuring fairness in task processing. However, a naive array implementation can lead to severe performance issues.
FIFO and the Two Ends
A queue is a linear data structure with a strict access rule: elements are added at one end, the rear, and removed from the other, the front. The element that has waited longest is the next to leave — First In, First Out.
That restriction is the point. Like a stack, a queue is defined by what it refuses to let you do: there is no reaching into the middle, no indexing, no search. The narrow interface is what makes the structure a promise about ordering rather than just a container.
The core operations are four. enqueue adds an element at the rear. dequeue removes and returns the element at the front. peek or front reads the front without removing it. isEmpty reports whether anything remains — and calling dequeue on an empty queue is an underflow, which must either throw or return a sentinel, never silently return garbage.
All four are expected to be O(1). A queue whose dequeue is O(n) is not merely slow, it defeats the reason for choosing the structure — and, as the next section shows, that is exactly what the obvious implementation produces.
- Enqueue at the rear, dequeue from the front
- FIFO — longest-waiting element leaves first
enqueue,dequeue,peek,isEmpty- Dequeue on an empty queue is underflow — handle it explicitly
Why the Obvious Array Implementation Fails
Take a plain array with a rear index. Enqueue writes at rear and increments it — O(1), fine. Dequeue returns element 0 and then must shift every remaining element one slot left so the front is at index 0 again. That shift is O(n), and it happens on every single removal.
So a queue of n elements costs O(n²) to drain. This is not a theoretical concern: list.pop(0) in Python does exactly this, which is why collections.deque exists and why using a plain list as a queue is a standard performance bug.
The obvious repair is to stop shifting: keep a front index as well as rear, and dequeue by incrementing front. Now both operations are O(1) — but the space in front of front is abandoned. After enough operations, rear reaches the end of the array while the front of it sits empty, and the queue reports itself full while holding almost nothing.
The real fix is to let the indices wrap around with modulo arithmetic: rear = (rear + 1) % capacity. The array is treated as a ring, so the freed space at the front is reused instead of leaked. That is a circular queue, and it is how essentially every fixed-capacity queue is actually built.
The alternative is a linked list, which sidesteps the problem entirely. Keep head at the front and tail at the rear: enqueue attaches to tail.next and advances tail, dequeue advances head. Both O(1), no shifting, no wrapping, and no fixed capacity — at the cost of a pointer per element and scattered memory.
| Backing | Enqueue | Dequeue | Problem |
|---|---|---|---|
| Array, shift on dequeue | O(1) | O(n) | Shifting dominates everything |
| Array, moving front index | O(1) | O(1) | Leaks the space it passes over |
| Circular array | O(1) | O(1) | Fixed capacity; full and empty look alike |
| Linked list with head and tail | O(1) | O(1) | Pointer overhead, poor locality |
- Shifting on dequeue makes draining a queue O(n²)
- Python's
list.pop(0)is this bug — usecollections.deque - A moving front index is fast but wastes the space behind it
- Wrap with modulo, or use a linked list with head and tail
The Types of Queue
Four variants appear in syllabuses, and questions usually name one specifically. Each keeps some part of the FIFO promise and relaxes another.
A simple queue is the base case: enqueue at the rear, dequeue at the front, strict arrival order.
A circular queue is the same interface with wrapped indices, so a fixed-size array is fully reused. Its one genuine subtlety is that front == rear describes both an empty queue and a full one, resolved either by keeping an explicit count or by deliberately leaving one slot unused.
A priority queue breaks FIFO on purpose: elements carry a priority and the highest-priority one is served next regardless of when it arrived. Because that requires finding the extreme element quickly, it is normally backed by a heap rather than a list, giving O(log n) insertion and removal instead of O(1). It is a queue by interface, not by ordering.
A deque (double-ended queue) relaxes the other way, permitting insertion and removal at both ends. That makes it a superset of both the queue and the stack — restrict it to rear-in/front-out and it is a queue; restrict it to rear-in/rear-out and it is a stack.
- Simple — strict arrival order, one end each way
- Circular — wrapped indices; full and empty need disambiguating
- Priority — served by priority, heap-backed, O(log n)
- Deque — both ends open; a superset of queue and stack
Terms, operations, and practical uses
Core operations
- EnqueueAdding an element to the rear (tail) of the queue. O(1) time complexity.
- DequeueRemoving and returning the element from the front (head) of the queue. O(1) time complexity.
- FIFOFirst-In-First-Out. The fundamental ordering rule of a queue.
Implementation problems
- Array ShiftingThe fatal flaw of naive array-backed queues where dequeuing requires shifting all remaining elements left in O(N) time.
- Two-Stack QueueA clever workaround where one stack is used for enqueuing and another is used for dequeuing, reversing elements when needed.
- Linked List QueueThe standard implementation using head and tail pointers to achieve strict O(1) enqueue and dequeue operations.
Practical applications
- Breadth-First Search (BFS)Using a queue to explore trees or graphs layer by layer, guaranteeing the shortest path in unweighted graphs.
- Task SchedulingBuffering incoming requests so worker threads can process them fairly in the order they were received.
- Message BrokersEnterprise software (like Kafka or RabbitMQ) designed specifically to handle massive distributed queues reliably.
Linked List Queue Operations
class Node:
def __init__(self, val):
self.val = val
self.next = None
class Queue:
def __init__(self):
self.head = self.tail = None
def enqueue(self, val):
new_node = Node(val)
if not self.tail:
self.head = self.tail = new_node
return
self.tail.next = new_node
self.tail = new_node
def dequeue(self):
if not self.head:
return None
val = self.head.val
self.head = self.head.next
if not self.head:
self.tail = None
return val
q = Queue()
q.enqueue(10)
q.enqueue(20)
q.dequeue()
q.enqueue(30)
print('Front is ' + str(q.head.val) + ', Rear is ' + str(q.tail.val))#include <iostream>
using namespace std;
struct Node {
int val;
Node* next;
Node(int x): val(x), next(NULL) {
};
};
class Queue {
public:
Node *head = NULL, *tail = NULL;
void enqueue(int val) {
Node* newNode = new Node(val);
if(!tail) {
head = tail = newNode;
return;
}
tail->next = newNode;
tail = newNode;
}
int dequeue() {
if (!head) return -1;
int v = head->val;
Node* temp = head;
head = head->next;
if (!head) tail = NULL;
delete temp;
return v;
}
};
int main() {
Queue q;
q.enqueue(10);
q.enqueue(20);
q.dequeue();
q.enqueue(30);
cout << "Front is " << q.head->val << ", Rear is " << q.tail->val << '\n';
}class Main {
static class Node {
int val;
Node next;
Node(int x) {
val = x;
}
}
static class Queue {
Node head, tail;
void enqueue(int val) {
Node newNode = new Node(val);
if(tail == null) {
head = tail = newNode;
return;
}
tail.next = newNode;
tail = newNode;
}
int dequeue() {
if (head == null) return -1;
int v = head.val;
head = head.next;
if (head == null) tail = null;
return v;
}
}
public static void main(String[] args) {
Queue q = new Queue();
q.enqueue(10);
q.enqueue(20);
q.dequeue();
q.enqueue(30);
System.out.println("Front is " + q.head.val + ", Rear is " + q.tail.val);
}
}Step through it
Running on Enqueue 10, Enqueue 20, Dequeue, Enqueue 30
Read all 12 Steps
- An empty queue A queue keeps two references: head, where elements leave, and tail, where they arrive. Both are null while the queue is empty.
- Enqueue 10 into an empty queue The first element is the special case: it is simultaneously the head and the tail. Both pointers are set to the same node.
- Enqueue 20 — link before moving tail.next = newNode attaches 20 to the end of the chain. Doing this before moving tail is what keeps the list connected; move tail first and the old node's next is never set.
- Advance the tail tail = newNode. Enqueue is now complete: two pointer writes, no traversal, O(1) regardless of how long the queue is.
- Enqueue 30 The same two steps again. The queue holds 10, 20, 30, with 10 at the front because it arrived first.
- Dequeue reads the head FIFO means the element that has waited longest leaves first — that is 10, at the head. A stack would have taken 30 here; this single difference is the whole distinction between the two structures.
- Advance the head head = head.next, so head now refers to 20. The old node is unlinked and can be freed. Again O(1) — nothing shifts, unlike an array-backed queue.
- Dequeue again 20 leaves, in the order it arrived. head moves to 30, which is now both the head and the tail.
- Dequeue the last element 30 leaves and the queue is empty. head becomes null — but tail is still pointing at the freed node.
- The bug everyone writes once When the queue becomes empty, tail must be set to null as well. Forget it and the next enqueue writes tail.next on a node that is no longer in the queue, and the element silently vanishes.
- Enqueue 40 into the emptied queue With both pointers correctly nulled, this is the first-element case again: head and tail both point at 40. The queue is reusable.
- Why a linked list and not an array Every operation here touched one or two pointers. An array-backed queue must either shift all remaining elements on dequeue, which is O(n), or wrap its indices with modulo — which is exactly what a circular queue does.
Breadth-First Search Depends on the Ordering
The most important application is breadth-first search, and the relationship is tighter than 'BFS happens to use a queue'. Enqueue the start node, then repeatedly dequeue a node, mark it visited, and enqueue its unvisited neighbours.
Because the queue is FIFO, every node at distance d is dequeued before any node at distance d+1 is reached. The queue therefore always holds nodes from at most two adjacent levels, and the traversal sweeps outward in complete rings.
That is what makes BFS a shortest-path algorithm on unweighted graphs: the first time a node is dequeued, no shorter route to it can exist, because a shorter one would have placed it in an earlier ring. The proof rests entirely on the FIFO property — swap the queue for a stack and the same code becomes depth-first search and loses the guarantee completely.
The same structure appears in level-order tree traversal, which is BFS on a tree. Recording the queue's size at the start of each round tells you exactly how many nodes are on the current level, which is how per-level output is produced without storing depths.
- BFS explores in complete rings of increasing distance
- First dequeue of a node is its shortest unweighted distance
- Replace the queue with a stack and BFS becomes DFS
- Queue size at the start of a round = the size of that level