Queues
A print line, a support queue — first come, first served — is a data structure with its own rules.
The problem
You send three documents to a shared office printer. So does everyone else on your floor. Nobody expects their third page to come out first — the printer serves jobs in the order they arrived. The person who clicked "print" at 9:01 gets their pages before the person who clicked at 9:02.
That fairness is the whole point. A support desk, a ticket line at the bank, packets arriving on a network card — they all share one rule: whoever got here first, gets served first. You need a structure that remembers arrival order and hands things back in that exact order.
A first attempt
Reach for a plain array. New jobs go on the end with append. To serve the oldest, you take index 0:
jobs = []
jobs.append("doc-A") # arrives first
jobs.append("doc-B")
first = jobs.pop(0) # serve "doc-A"It works, and append is cheap. But pop(0) is the trap. Removing the front element forces every remaining item to shift down one slot to fill the gap. Serve one job out of n and you pay O(n). Drain the whole line and you have paid O(n²) for what should be simple bookkeeping. On a busy printer that is the difference between instant and sluggish.
The insight
The slowness comes from insisting the front lives at index 0. But nothing says it has to. Keep two pointers — one marking the front, one marking the back. To remove, read the front and move the front pointer forward. To add, write at the back and move the back pointer forward. Nothing shifts. Both operations touch a single slot, so both are O(1).
That two-ended discipline — add at one end, remove at the other — is a queue, and the rule it enforces is FIFO: first in, first out. A stack is LIFO; a queue is its mirror image.
How it works
Start empty
Picture a strip of slots. Two markers, front and back, both point at the start. Size is zero.
front,back
v
[ _ ][ _ ][ _ ][ _ ]Enqueue adds at the back
Write the value where back points, then advance back. This is "getting in line."
front back
v v
[ A ][ B ][ C ][ _ ]Dequeue removes from the front
Read the value front points at, then advance front. A leaves; B is now the oldest waiting.
front back
v v
[ _ ][ B ][ C ][ _ ]Peek and empty check
peek returns the front value without moving anything. The queue is empty when front == back (front caught up to back).
The code
A ready-made structure keeps the pointers for you: Python's collections.deque, a doubly linked list, or the language's built-in queue. Both ends stay O(1).
from collections import deque
class Queue:
def __init__(self):
self._data = deque()
def enqueue(self, x):
self._data.append(x)
def dequeue(self):
if not self._data:
raise IndexError("dequeue from empty queue")
return self._data.popleft() # O(1)
def peek(self):
return self._data[0]
def is_empty(self):
return len(self._data) == 0
q = Queue()
q.enqueue("doc-A")
q.enqueue("doc-B")
print(q.dequeue()) # doc-A
print(q.peek()) # doc-Bclass Queue<T> {
private data: T[] = [];
private head = 0; // index of the front
enqueue(x: T): void {
this.data.push(x);
}
dequeue(): T {
if (this.isEmpty()) throw new Error("dequeue from empty queue");
const x = this.data[this.head];
this.head++;
// occasionally compact so memory does not grow forever
if (this.head > 32 && this.head * 2 >= this.data.length) {
this.data = this.data.slice(this.head);
this.head = 0;
}
return x;
}
peek(): T {
return this.data[this.head];
}
isEmpty(): boolean {
return this.head === this.data.length;
}
}
const q = new Queue<string>();
q.enqueue("doc-A");
q.enqueue("doc-B");
console.log(q.dequeue()); // doc-A
console.log(q.peek()); // doc-Bimport java.util.ArrayDeque;
import java.util.Deque;
class Queue<T> {
private final Deque<T> data = new ArrayDeque<>();
void enqueue(T x) {
data.addLast(x);
}
T dequeue() {
if (data.isEmpty()) throw new IllegalStateException("empty");
return data.pollFirst(); // O(1)
}
T peek() {
return data.peekFirst();
}
boolean isEmpty() {
return data.isEmpty();
}
public static void main(String[] args) {
Queue<String> q = new Queue<>();
q.enqueue("doc-A");
q.enqueue("doc-B");
System.out.println(q.dequeue()); // doc-A
System.out.println(q.peek()); // doc-B
}
}#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int value;
struct Node *next;
} Node;
typedef struct {
Node *front;
Node *back;
} Queue;
void init(Queue *q) { q->front = q->back = NULL; }
void enqueue(Queue *q, int x) {
Node *n = malloc(sizeof(Node));
n->value = x;
n->next = NULL;
if (q->back) q->back->next = n;
else q->front = n;
q->back = n;
}
int dequeue(Queue *q) {
Node *n = q->front; /* assumes non-empty */
int x = n->value;
q->front = n->next;
if (!q->front) q->back = NULL;
free(n);
return x;
}
int main(void) {
Queue q;
init(&q);
enqueue(&q, 10);
enqueue(&q, 20);
printf("%d\n", dequeue(&q)); /* 10 */
printf("%d\n", q.front->value); /* 20 (peek) */
return 0;
}#include <iostream>
#include <queue>
int main() {
std::queue<std::string> q;
q.push("doc-A"); // enqueue
q.push("doc-B");
std::cout << q.front() << "\n"; // peek -> doc-A
q.pop(); // dequeue doc-A
std::cout << q.front() << "\n"; // doc-B
std::cout << "empty? " << q.empty() << "\n";
return 0;
}Complexity
| Operation | Time | Space |
|---|---|---|
| Enqueue | O(1) | O(1) |
| Dequeue | O(1) | O(1) |
| Peek | O(1) | O(1) |
| Whole queue | — | O(n) |
The pop(0) array approach was O(n) per dequeue and O(n²) to drain. Two pointers (or a linked list) fixes both.
When to use it
Reach for a queue when order matters
Use a queue whenever items must be processed in arrival order: task and job schedulers, print spoolers, request buffers, and — most famously — breadth-first search, where the queue holds the frontier of nodes to visit. If you need fast access at both ends, look at a deque instead. And never dequeue with array.pop(0) in a hot loop — that quietly turns O(1) into O(n).
Practice
Recap
- A queue enforces FIFO — first in, first out — the mirror of a stack's LIFO.
- Enqueue at the back, dequeue at the front; both are O(1) with a linked list or two pointers.
- Never dequeue with
pop(0)on a plain array — it shifts everything and costs O(n).
How is this guide?
Last updated on