Queues (FIFO)
Add at the rear, remove from the front — fairness, and breadth-first search. · 5 min read
A queue adds at one end (the rear) and removes from the other (the front), so the first item in is the first out — FIFO. Think of a line at a counter.
Interactive visualization: Enqueue / dequeue — step through it frame by frame on this page.
The queue invariant
front points to the next item out— Dequeue updates the front.rear points to the next insertion spot— Enqueue updates the rear.neither operation shifts all elements— A linked list or circular buffer avoids O(n) movement.
Result: O(1) enqueue/dequeue