Queue

First in, first out.

A queue is like a line at a checkout: people join at the back (enqueue) and are served from the front (dequeue). The first to arrive is the first to leave.

• enqueue — add to the back.
• dequeue — remove from the front.
• front/peek — view the next item to be served.

Variants.

• Circular queue (ring buffer) — a fixed-size array reused in a circle; O(1) ops with no shifting.
• Deque — double-ended queue; add/remove at both ends.
• Priority queue — items served by priority, not arrival order (usually a heap).

Backed by a linked list (with head + tail pointers) or a circular array, enqueue/dequeue are O(1). A naive array queue that shifts on dequeue is O(n) — avoid it.

Concurrency and systems.

• BFS — a queue drives breadth-first search, processing nodes level by level.
• Producer–consumer — blocking/concurrent queues decouple producers from consumers (thread pools, task scheduling).
• Lock-free queues — CAS-based designs (Michael–Scott) for high-throughput concurrency.
• Message queues — the same FIFO idea at system scale (Kafka, RabbitMQ, SQS) for buffering and async decoupling.