Queues — FIFO Fundamentals

A queue is a first-in-first-out (FIFO) collection. Items enter at the back and leave from the front. Both operations are $O(1)$ — usually implemented as a doubly linked list or as a circular buffer in an array.

Implementation notes

Using a Python list with pop(0) gives $O(n)$ dequeue — every remaining element shifts left. Use collections.deque (a doubly linked list) for true $O(1)$. In Java, ArrayDeque is the typical choice; LinkedList technically works but with worse cache behavior.

Breadth-first search

BFS explores a graph or tree level by level using a queue. Enqueue the start node; loop: dequeue, visit, enqueue all unvisited neighbors. Because nodes enter the queue in distance order, BFS finds shortest paths (in unweighted graphs) and level-by-level structure.

Producer-consumer

Threads share a bounded queue. Producers enqueue work, consumers dequeue. The queue's blocking semantics handle synchronization. This is the basis for thread pools and message-passing systems.

Rate limiters and buffers

A queue of recent request timestamps lets you implement a sliding-window rate limiter. A circular buffer of fixed size is the backing store for log ring buffers, audio buffers, and many embedded systems primitives.

Two stacks make a queue

A neat trick: maintain an "in" stack and an "out" stack. Enqueue pushes to in. Dequeue pops from out; when out is empty, transfer all of in into out (which reverses the order). Amortized $O(1)$ per operation despite the occasional $O(n)$ transfer.