View source for 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|graph search]], queues drive [[Breadth-First Search|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|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.

[[Category:Computer Science]] [[Category:Data Structures]] [[Category:Systems]]