Queue

A First-In-First-Out line: enqueue at the back, dequeue from the front — both ends O(1).

A queue is a waiting line. You join at the back (enqueue) and are served from the front (dequeue), so whoever arrived first leaves first. That's FIFO — *First In, First Out* — and it's the natural shape for anything that must be handled fairly, in arrival order: print jobs, tasks waiting for a worker, requests hitting a server.

The operations

1enqueue(x) — add x to the back of the line.
2dequeue() — remove and return the value at the front.
3front() — peek at the front value without removing it.

Don't naively dequeue from an array's front

Implementing dequeue as array.shift() is O(n) — every remaining element shuffles down one slot. A real queue keeps O(1) at both ends using a circular buffer (head/tail indices that wrap around) or a linked list, so neither end pays a shifting cost.

// O(1) at both ends via two pointers into a growing array
class Queue {
  constructor() { this.items = {}; this.head = 0; this.tail = 0; }
  enqueue(x) { this.items[this.tail++] = x; }      // add at back
  dequeue() {
    if (this.head === this.tail) return undefined;  // empty
    const x = this.items[this.head];
    delete this.items[this.head++];                 // remove at front
    return x;
  }
  front() { return this.items[this.head]; }
  get isEmpty() { return this.head === this.tail; }
}

Why the circular buffer wins

A fixed-size array used as a ring lets the front and back indices chase each other around, wrapping from the last slot back to the first. No element ever moves — only the two indices advance — so both enqueue and dequeue stay O(1) with no wasted space.

Where queues show up

Beyond fairness, the queue is the engine of breadth-first search: visiting a node and adding its neighbours to the back means everything one step away is processed before anything two steps away — which is exactly why BFS finds shortest paths in unweighted graphs. Queues also buffer work between a fast producer and a slow consumer, smoothing out bursts.

OperationTimeSpace

enqueue / dequeue / front · each touches one fixed endO(1)O(1)

Storage · n items in line—O(n)

Check yourself

A stack is LIFO. What is a queue?