Queue
First in, first out — a checkout line. Enqueue at the rear, dequeue at the front, both O(1). Fairness by construction.
A queue adds at one end and removes at the other, guaranteeing elements leave in arrival order. Implementations use a linked list with head and tail pointers, or a circular buffer over an array — both give O(1) at each end.
Queues are the natural shape for producer/consumer handoffs: one side enqueues work, the other dequeues it, and bursts get absorbed instead of dropped. BFS uses a queue to guarantee level-by-level exploration, which is exactly why it finds shortest paths in unweighted graphs.
Variants: the deque (double-ended queue) allows O(1) at both ends; the priority queue (usually a heap underneath) dequeues by priority instead of arrival — different contract, same "hand me the next item" role.
Operations
| Operation | Complexity |
|---|---|
| enqueue | O(1) |
| dequeue | O(1) |
| front | O(1) |
| search | O(n) |
Where it's used
Task schedulers, message queues, BFS frontiers, rate limiters, print spoolers — any pipeline where order of arrival matters.