Queue (line, data structure, and queueing theory)

Characteristics and basic operations

Abstract queues follow a simple discipline: first in, first out (FIFO). Core operations include enqueue (add an item to the rear), dequeue (remove from the front), and peek (inspect the front element without removing it). Queues may be bounded (fixed capacity) or unbounded, and behavior on overflow can include blocking, dropping new arrivals, or signaling errors. FIFO contrasts with a stack's last-in, first-out (LIFO) behavior and with priority-based structures where order is determined by keys.

Types and implementations

• Simple queues implemented with arrays or singly linked lists for straightforward enqueue/dequeue operations.
• Circular buffers (ring buffers) for fixed-size storage that efficiently reuse space without moving elements.
• Double-ended queues (deques) that allow insertion and removal at both ends, and priority queues that order items by priority rather than arrival time.
• Concurrent queues and lock-free implementations designed for multi-threaded programs and high-performance systems.

Queueing theory and performance

Queueing theory is the mathematical study of waiting lines. Models describe arrival processes, service processes, the number of servers, and capacity constraints to estimate metrics such as average wait time, queue length, throughput, and server utilization. Standard notations and simple models (often denoted by common shorthand) help analyze bottlenecks and inform resource allocation in telephony, transportation, manufacturing, and computer networks. Behavioral phenomena studied include balking (refusing to join), reneging (leaving before service), and priority disciplines.

Uses and examples

Queues are ubiquitous: ticket lines, customer service desks, restaurant waiting lists and airport checkpoints. In computing they appear as job schedulers, print queues, message queues, event loops and in algorithms such as breadth-first search. Queues coordinate producers and consumers, smooth mismatches between arrival and processing rates, and form fundamental building blocks in operating systems and distributed systems.

Social and cultural notes

Queuing implies social rules about fairness and order; cutting in line is widely stigmatized. The word also has other meanings in history and culture, for example the braided ponytail sometimes called a "queue" that has been worn or required in particular societies. Awareness of both technical and human aspects highlights how a simple ordering principle shapes technology, organizations and everyday life.