Queue (data structure)

A queue is a first-in-first-out (FIFO) abstract data structure in which elements are added at the rear and removed from the front. It is the computational embodiment of waiting: the first request submitted is the first request served, a discipline that prevents starvation and enforces temporal fairness. In graph search, queues drive breadth-first search, ensuring that nodes are explored in order of discovery rather than depth. But the queue is not merely a programming convenience; it is a fundamental model of how systems process sequential demand.

In queueing theory, the queue becomes a stochastic system: arrivals and departures are random variables, and the discipline of the queue determines whether the system stabilizes or collapses under load. The M/M/1 queue — the simplest model — reveals that even a single server with Poisson arrivals will develop an infinite backlog if the arrival rate exceeds the service rate. This is a systems insight: fairness (FIFO) is not free. It costs memory, and when demand exceeds capacity, the queue grows without bound. The queue is therefore a diagnostic: if your queue is growing, your system is undersized, not poorly scheduled.