Queue

A queue is a linear data structure that stores elements in a sequence and supports two principal operations: enqueue (insert at the rear) and dequeue (remove from the front). It preserves the first-in, first-out order, meaning the oldest element added is the first to be removed. The term is derived from the notion of waiting in line.

Queues can be implemented in several ways, including arrays, linked lists, or circular buffers. An array-based queue may require shifting elements or use a circular arrangement to reuse space. A linked-list queue uses nodes linked in a chain, with pointers to the front and rear. Performance is typically O(1) time for both enqueue and dequeue in well-implemented queues, with O(n) for resizing if using a plain dynamic array.

Variants include priority queues, where elements are dequeued according to priority rather than arrival order, and double-ended queues (deques), which allow insertion and removal at both ends. Some queues also support bounded capacity, in which case enqueueing when full is either blocked, or causes an overflow exception.

Common applications include job scheduling, printer spooling, data buffering in I/O streams, messaging, and traversal algorithms such as breadth-first search. In real-world terms, a queue models waiting lines where the discipline is to serve customers in order of arrival.