Queues & Deques: guided lesson

the story

Queue (FIFO)

Every tool here exists because something was too slow or broke without it. Here is what.

1909–1917 · Agner Krarup Erlang, Copenhagen Telephone Company

Nobody invented "first come, first served" — waiting lines are older than computers, and the FIFO queue in code has no single inventor. What has a clear start is the maths of queues. In 1909 Erlang, an engineer at the Copenhagen Telephone Company, showed that calls made at random follow a Poisson distribution. His 1917 paper gave formulas for lost calls and waiting time, and telephone companies in many countries adopted them. That field, queueing theory, is still how engineers size server pools, call centres and network buffers.

the problem it solved

How many lines a telephone exchange needs so that calls rarely wait or get lost — sizing any system that serves requests in arrival order.

why it matters: without it

Bursts of work would be dropped or served in random order — no fairness for print jobs or bookings — and BFS would stop finding shortest paths.

sources: MacTutor History of Mathematics — Agner Krarup Erlang (University of St Andrews) ↗

also in this chapter: Circular buffer (ring buffer) · Deque and Java's ArrayDeque · Monotonic deque · Queue from two stacks (amortized O(1))

the idea

The idea in 30 seconds

A queue lets you add at the rear and remove from the front: whoever arrived first leaves first (FIFO).

Both ends must be O(1). An array does that by letting head and tail walk forward and wrap around; a linked list does it with head and tail pointers.

A deque ("deck") opens both ends. Keep it sorted as you go and it becomes a monotonic deque — the trick behind sliding-window maximum.

picture this

Your printer's queue: jobs wait in the order you pressed Ctrl+P. The printer always takes the oldest job; a new job joins at the back. No job jumps the line — that is FIFO.

watch it

Linked queue: enqueue & dequeue

Predict mode is on. Before each step, guess what happens, then watch. Wrong guesses are fine; that is how it sinks in.

sim

Linked queue: enqueue & dequeue

Top: the queue as the user sees it. Bottom: the linked nodes in memory, with head and tail markers.

loading simulation…

javajava.util.*

1class LinkedQueue {2    private static class Node {3        final int val;4        Node next;5 6        Node(int val) {7            this.val = val;8        }9    }10 11    private Node head; // front: we remove here12    private Node tail; // rear: we add here13    private int size;14 15    void enqueue(int x) {16        Node node = new Node(x);17        if (tail == null) head = node; // empty queue: the new node is also the front18        else tail.next = node; // link it after the old rear19        tail = node;20        size++;21    }22 23    int dequeue() {24        if (head == null) throw new NoSuchElementException("queue is empty");25        int x = head.val;26        head = head.next;27        if (head == null) tail = null; // queue became empty: forget the rear too28        size--;29        return x;30    }31 32    int peek() {33        if (head == null) throw new NoSuchElementException("queue is empty");34        return head.val;35    }36 37    boolean isEmpty() {38        return size == 0;39    }40}

On this screen ← / → step the simulation. Use the buttons below to move through the lesson.

watch it

Circular buffer: watch head and tail wrap around

Predict mode is on. Before each step, guess what happens, then watch. Wrong guesses are fine; that is how it sinks in.

sim

Circular buffer: watch head and tail wrap around

The array never shifts. Grey slots are free (or stale); the live part can wrap past the end back to index 0.

loading simulation…

javajava.util.*

1class CircularQueue {2    private final int[] data;3    private int head = 0; // index of the front element4    private int tail = 0; // index where the next element will go5    private int size = 0; // how many elements are stored right now6 7    CircularQueue(int capacity) {8        data = new int[capacity];9    }10 11    /** Adds x at the rear. Returns false when the queue is full (like Queue.offer). */12    boolean enqueue(int x) {13        if (size == data.length) return false;14        data[tail] = x;15        tail = (tail + 1) % data.length; // step right, wrap to 0 at the end16        size++;17        return true;18    }19 20    /** Removes and returns the front. Throws when empty (like Queue.remove). */21    int dequeue() {22        if (size == 0) throw new NoSuchElementException("queue is empty");23        int x = data[head];24        head = (head + 1) % data.length; // step right, wrap to 0 at the end25        size--;26        return x;27    }28 29    int peek() {30        if (size == 0) throw new NoSuchElementException("queue is empty");31        return data[head];32    }33 34    boolean isEmpty() {35        return size == 0;36    }37 38    int size() {39        return size;40    }41}

On this screen ← / → step the simulation. Use the buttons below to move through the lesson.

key idea 1 of 8