A queue is a linear data structure that stores elements in the order they arrive and removes them in the same order, a discipline known as first in, first out (FIFO). Elements are added at the back, or tail, and taken from the front, or head, so the element that has waited longest is always served next.
Among data structures, the queue is the natural model for waiting lines of work: print jobs, network packets, keyboard events, background tasks and requests waiting for a server. It is the counterpart of the stack, which serves the most recent element first, and it underlies algorithms such as breadth-first search on a graph or tree.
How a queue works
A queue works through two primary operations that act on opposite ends. Enqueue places an element at the tail, and dequeue removes the element at the head. Because insertion and removal never touch the same end, the relative order of elements never changes while they wait.
A well-implemented queue performs every core operation in constant time, O(1), regardless of how many elements it holds. Accessing an element in the middle is not part of the abstraction; if that is needed often, a different structure is usually the better choice.
| Operation | Effect | Time complexity |
|---|---|---|
| Enqueue | Add an element at the tail | O(1) |
| Dequeue | Remove and return the head element | O(1) |
| Peek | Read the head element without removing it | O(1) |
| Is empty | Report whether any element is waiting | O(1) |
| Size | Return the number of elements | O(1) when tracked |
Two edge cases need explicit handling: dequeuing from an empty queue, which must return a signal or raise an error, and enqueuing into a full bounded queue, which must block, reject or overwrite depending on the design.
Implementing a queue
A queue is an abstract data type, so the same interface can sit on different storage. The two classic implementations use a linked list or an array treated as a ring, and each has distinct memory and performance characteristics.
| Implementation | How it stores elements | Strength | Weakness |
|---|---|---|---|
| Linked list | Nodes with head and tail pointers | Unbounded growth, no copying | Extra memory per node, poor cache locality |
| Circular buffer | Fixed array with wrapping indices | Compact and cache-friendly | Fixed capacity unless resized |
| Dynamic ring buffer | Circular array that doubles when full | Amortized O(1), good locality | Occasional resize pause |
| Two stacks | Input and output stacks | Simple in functional languages | Amortized rather than strict O(1) |
A naive array queue that shifts every element forward on dequeue costs O(n) per removal and is a common performance mistake. In a circular buffer, head and tail indices advance modulo the capacity, so no element ever moves.
Queue variants
Several specialized variants keep the idea of ordered waiting but change the rule for who is served next or add capabilities. Choosing the right variant often matters more than the implementation details.
| Variant | Ordering rule | Typical use |
|---|---|---|
| Simple queue | Strict FIFO | Task lists, buffering input |
| Double-ended queue | Insert and remove at both ends | Sliding-window algorithms, undo history |
| Priority queue | Highest priority first, usually a heap | Scheduling, shortest-path algorithms |
| Bounded blocking queue | FIFO with fixed capacity, waits when full | Producer-consumer threads |
| Concurrent lock-free queue | FIFO with atomic operations | High-throughput multithreaded systems |
A priority queue is a queue only in name: it abandons arrival order and typically uses a binary heap, giving O(log n) insertion and removal. A double-ended queue, often called a deque, generalizes both the queue and the stack.
The same principle scales beyond a single program. A message queue in a distributed system stores messages durably between services, so a producer can continue working while a consumer is slow or temporarily offline. Such systems add guarantees that an in-memory queue lacks, such as persistence, acknowledgment and redelivery, but they usually offer only at-least-once delivery, which means consumers must handle duplicate messages safely.
Queue compared with stack, array and linked list
The queue is easiest to understand by contrast with its closest relatives in data structures. Each answers a different question about which element should be handled next.
| Structure | Access rule | Natural fit |
|---|---|---|
| Queue | First in, first out | Fair processing in arrival order |
| Stack | Last in, first out | Nested calls, backtracking, parsing |
| Array | Random access by index | Fixed collections, direct lookup |
| Linked list | Sequential traversal | Frequent insertion in the middle |
The distinction has visible consequences in algorithms. Exploring a graph with a queue yields breadth-first search, which finds the shortest path in an unweighted graph; replacing the queue with a stack yields depth-first search, which explores one branch completely before the next.
Pitfalls when using queues
Queues fail most often through unbounded growth and concurrency mistakes rather than incorrect order. These problems tend to appear only under load, which makes them expensive to discover late.
- Unbounded queues hide overload. If producers outpace consumers, memory grows until the process fails; a bounded queue with backpressure fails earlier and more clearly.
- Shared queues need synchronization. Using a non-thread-safe queue from several threads corrupts its internal pointers.
- Polling an empty queue in a tight loop wastes processor time; blocking or signaling queues avoid it.
- Long wait times can violate deadlines even when throughput looks fine, so queue length and age of the oldest element should be monitored.
In everyday language
A queue in programming works exactly like a line at a ticket counter. People join at the end of the line, and the person at the front is served first. Nobody skips ahead, so everyone is handled in the order they arrived.
Computers use queues whenever more work arrives than can be handled at once. Documents sent to a printer, messages waiting to be delivered and videos waiting to be processed all wait their turn in a queue, which keeps the work fair and orderly.
Seen in the real world
A photo-sharing application lets users upload images, each of which must be resized into five formats. Resizing takes about two seconds per image, so doing it during the upload request would keep users waiting. The developers place each upload into a bounded job queue with a capacity of 10,000 entries.
Eight worker threads dequeue jobs and resize images in arrival order. During an evening peak, uploads briefly exceed processing capacity, and the queue grows to about 3,000 jobs before draining within minutes. Because the queue is bounded and monitored, the team receives an alert when the oldest job waits longer than one minute and adds workers before users notice delays. Uploads remain fast, and every image is processed in order.