What is a Queue

A queue is a data structure that follows the FIFO principle: first in, first out. Elements are added at the back (enqueue) and removed from the front (dequeue). Think of a line at a checkout counter — the first person in line is the first person served.

How it works

A queue supports two primary operations, both O(1):

• Enqueue — add an element to the back.
• Dequeue — remove and return the element from the front.

enqueue(A)  enqueue(B)  enqueue(C)  dequeue()    dequeue()

front → [A]    [A, B]    [A, B, C]   → returns A   → returns B
                                       [B, C]        [C]

A naive array-based queue has a problem: dequeuing from the front requires shifting every remaining element left, which is O(n). The solution is a circular buffer (ring buffer) — the array wraps around so that front and back pointers chase each other. No shifting needed; both enqueue and dequeue stay O(1).

A linked list-based queue maintains pointers to both head and tail. Dequeue removes the head; enqueue appends at the tail. Both are O(1) with no resizing, but the cache performance is worse than a circular buffer.

A priority queue is a variant where elements are dequeued not in FIFO order but by priority — the highest-priority element comes out first, regardless of when it was inserted. Priority queues are typically implemented with a heap, not a simple array or linked list.

Double-ended queues (deques) allow insertion and removal at both ends, combining the capabilities of stacks and queues.

Why it matters

Queues appear everywhere in systems:

• BFS traversal — breadth-first search in a graph uses a queue to explore nodes level by level. See How Graph Algorithms Work.
• Task scheduling — operating systems use queues to manage which process runs next.
• Message passing — distributed systems use message queues (Kafka, RabbitMQ) to decouple producers and consumers.
• Buffering — network packets, print jobs, and I/O requests all wait in queues.

The FIFO property guarantees fairness: whatever arrives first gets processed first. This makes queues the natural structure for any system that must handle requests in order.

See How Arrays and Linked Lists Work for the underlying implementations.