Waiting in line
A queue is an abstract data type that serves items in arrival order: first in, first out. Items enter at the back through an enqueue operation and leave from the front through a dequeue operation. It captures fairness, since whoever waited longest is served next.
Where queues appear
Queues model any process where order of arrival should be respected.
- A printer serves documents in the order they were submitted.
- A breadth first search visits nodes in the order they were discovered.
- Task schedulers hand out work to keep producers and consumers decoupled.
Building one efficiently
A naive array queue that shifts everything forward on each dequeue is slow. The common fix is a circular buffer: keep a fixed array with a front index and a back index that wrap around modulo the length. Enqueue writes at the back index and advances it; dequeue reads at the front index and advances it. No shifting occurs, so both operations are constant time. A linked list with head and tail pointers achieves the same.
Key idea
A queue serves items first in, first out using enqueue at the back and dequeue at the front, and a circular buffer or a linked list makes both operations constant time without shifting.