Queues

Picture the lunch queue at school. You join at the back; the person served next is always the one at the front — the person who has been waiting longest. Nobody (fairly!) barges in and gets served first. That single rule of fairness is exactly what a queue data structure captures: first in, first out, or FIFO.

A queue is a collection where you add at one end and remove from the other. Whatever went in first comes out first, so the order things arrive is the order they leave. It is one of the most useful structures in all of computing — and, like the queue you stand in, it is defined not by how it is stored but by the discipline it enforces on the order of arrivals and departures.

The four operations

A queue exposes a small, fixed set of operations — and crucially it lets you touch only the two ends, never the middle:

enqueue(x) — add item x to the rear (the back of the queue), where new arrivals join.
dequeue() — remove and return the item at the front, the one that has waited longest.
peek() — look at the front item without removing it (who's next to be served?).
isEmpty() — is there anyone in the queue at all?

Because you may only add at the rear and take from the front, the FIFO order is guaranteed by the structure itself — there is simply no operation that would let you jump the queue.

Watch it move

Below, items join at the rear on the right and leave from the front on the left. Step through it and notice the order in which values depart — it is exactly the order they arrived.

This is the whole idea in one picture: arrivals pile up at the back, departures peel off the front, and the queue quietly preserves arrival order from end to end.

A queue in TypeScript

The simplest way to build one is to wrap an array and only ever add to the back and remove from the front. Here is a reusable Queue class. Watch the Output: the values come out in the same order they went in — 10, 20, 30 — which is what makes it FIFO.

class Queue<T> { private items: T[] = []; enqueue(x: T): void { // add to the REAR this.items.push(x); } dequeue(): T | undefined { // remove from the FRONT return this.items.shift(); } peek(): T | undefined { // front item, without removing return this.items[0]; } isEmpty(): boolean { return this.items.length === 0; } get size(): number { return this.items.length; } } const jobs = new Queue<number>(); jobs.enqueue(10); // 10 joins the rear jobs.enqueue(20); jobs.enqueue(30); console.log("Next up (peek):", jobs.peek()); // 10 is at the front console.log("Size:", jobs.size); while (!jobs.isEmpty()) { console.log("Serving:", jobs.dequeue()); // FIFO: 10, then 20, then 30 } console.log("Empty now?", jobs.isEmpty());

Notice how dequeue always hands back the oldest waiting item. Swap the queue for a stack and the last item in would come out first — the opposite order. That contrast is worth pinning down.

A stack is a queue's mirror image. A stack is LIFO — last in, first out — like a pile of plates: you add and remove at the same end (the top), so the most recent arrival is served first. A queue is FIFO — first in, first out — and adds and removes at opposite ends, so the oldest arrival is served first.

Enqueue 1, 2, 3 then drain the collection: a queue gives 1, 2, 3 (arrival order preserved); a stack gives 3, 2, 1 (arrival order reversed). Same inputs, opposite output — the two structures differ only in which end you take from.

Where queues show up

Any time work must be handled fairly, in the order it arrived, there's a queue hiding underneath:

Print job queues — documents print in the order they were sent, not whoever shouts loudest.
Task / process scheduling — an operating system queues jobs waiting for the CPU so each gets its turn.
Breadth-first search (BFS) — exploring a graph or maze level by level uses a queue to remember which places to visit next, always in discovery order.
Buffering — a video stream, a keyboard's key-presses, or data arriving over a network is held in a queue so a fast producer and a slower consumer can work at their own pace.

The circular queue: reusing the space

The array version above is easy to read, but shift() hides a cost: removing the front element means every remaining item slides down one slot. Repeatedly enqueueing and dequeueing also leaves a growing patch of "used up" space at the start of the array going to waste.

A circular queue fixes both. It keeps a fixed-size array and two indices — front and rear — that wrap around to the start using the remainder operator (% capacity) when they run off the end. Nothing ever slides; the array is treated as a ring, so freed slots at the front are reused by later arrivals. Run it:

class CircularQueue { private items: (number | null)[]; private front = 0; private count = 0; constructor(private capacity: number) { this.items = new Array(capacity).fill(null); } enqueue(x: number): boolean { if (this.count === this.capacity) return false; // full: no room const rear = (this.front + this.count) % this.capacity; this.items[rear] = x; // rear wraps around this.count++; return true; } dequeue(): number | null { if (this.count === 0) return null; // empty const x = this.items[this.front]; this.items[this.front] = null; this.front = (this.front + 1) % this.capacity; // front wraps around this.count--; return x; } } const q = new CircularQueue(3); q.enqueue(1); q.enqueue(2); q.enqueue(3); console.log("Full, so enqueue(4) rejected?", q.enqueue(4) === false); console.log("Dequeue:", q.dequeue()); // 1 leaves, freeing slot 0 console.log("Now enqueue(4) fits and REUSES the freed slot:", q.enqueue(4)); console.log("Dequeue:", q.dequeue()); // 2 console.log("Dequeue:", q.dequeue()); // 3 console.log("Dequeue:", q.dequeue()); // 4 — arrival order still FIFO

The visible order is still perfectly FIFO — 1, 2, 3, 4 — but the storage is reused in place, so a circular queue runs in constant time per operation and never wastes room.

A queue has two different ends and it matters which is which — this is the classic trip-up. You enqueue at the rear (the back) and dequeue at the front (where items have waited longest). Mix them up and you have accidentally built a stack: adding and removing at the same end turns FIFO into LIFO and reverses your output order.

The second trap is queue underflow — calling dequeue() or peek() on an empty queue. There is nothing to hand back, so a careful implementation either returns a "nothing here" value (like undefined) or raises an error — it must not crash or return junk. Always check isEmpty() first. (Its cousin is overflow: enqueueing onto a full fixed-size queue, which the circular queue above guards against by returning false.)

A neat memory aid: this is the exact opposite of a stack, end for end. A stack adds and removes at one end and reverses order; a queue uses opposite ends and preserves it.