Queues

A queue is FIFO — first in, first out — with O(1) enqueue at one end and O(1) dequeue from the other. Use it anywhere order of arrival matters and you want fairness: job schedulers, print queues, rate-limited request processing, BFS (graph traversal level by level). Distributed message queues (Kafka, RabbitMQ, SQS) are the same primitive scaled to multi-process / multi-machine, with persistence and delivery guarantees bolted on — the core FIFO invariant is the same. Variants worth knowing: priority queue (dequeue always returns min/max, backed by a heap), deque (double-ended, push/pop from both sides), circular buffer (fixed size, oldest overwrites newest — useful for logs and streaming). Naive implementations using an array's shift() are O(n); real queues use a linked list or a circular buffer.