Overview

In computer science, a queue is an abstract data type that represents a collection of elements maintained in first-in, first-out (FIFO) order. Elements are added at one end (the rear or tail) and removed from the other (the front or head). The FIFO discipline makes queues suitable for modeling sequential waiting lines and many streaming or scheduling scenarios.

Core operations and characteristics

Typical operations provided by a queue interface include:

  • enqueue: insert an element at the rear.
  • dequeue: remove and return the element at the front.
  • peek (or front): observe the front element without removing it.
  • auxiliary checks such as isEmpty and size.

Elements between the front and rear are not directly accessed; the only permitted removals are from the front. Enqueue and dequeue are commonly implemented to run in constant time (O(1)) on average.

Implementations and common forms

Queues can be realized in several ways depending on performance and memory needs. Common implementations include arrays (often as circular buffers to reuse space), singly linked lists with head and tail pointers, and wrappers around double-ended queues. Some programming environments provide blocking or bounded queue implementations for thread coordination.

Applications and examples

Queues are ubiquitous in software and systems: they form the basis of breadth-first graph search, job and task scheduling, print spooling and network packet buffering, producer–consumer message passing, and event loops in user interfaces. In each case the FIFO order preserves processing fairness or arrival order.

Variants and notable distinctions

Several variants modify the basic FIFO behavior. A priority queue associates keys or priorities with elements; removal returns the element with highest (or lowest) priority rather than the oldest. Priority queues are often implemented with heaps. A deque (double-ended queue) permits insertion and removal at both ends. Bounded and blocking queues enforce capacity limits and can suspend producers or consumers until space or items become available.

Concurrency and performance considerations

When used between threads or processes, queues require synchronization. Many libraries offer thread-safe or lock-free queue implementations to reduce contention. Choice of implementation affects memory usage, worst-case performance and suitability for real-time or high-throughput systems.

Further reading

For general theory and practical APIs, consult resources on data structures and concurrent programming; these discuss trade-offs among array-backed rings, linked representations, and priority-based variants in greater detail.