Lesson notes
These notes explain the problem and current implementation. They are a reading companion, not a verbatim transcript of the recording.
A queue processes items in first-in, first-out order. The item that has waited longest leaves next. The recording introduces that ordering through examples and operations. It helps to separate the queue's behavior from its storage representation: a linked list, circular buffer, or another suitable structure can implement the same ordering.
Trace the front and the back
Enqueue A, then B, then C. The front is A and the back is C. A dequeue returns A and moves the front to B. Enqueuing D afterward should leave the remaining order B, C, D. A structure that returns D next has implemented stack ordering instead.
Peeking reads the next item without removing it. Empty behavior needs a defined contract, especially when the queue permits values such as null or undefined. A size or explicit emptiness check can distinguish an absent item from an allowed stored value. Do not assume every language's queue API chooses the same return or error behavior.
Choose a representation with efficient endpoints
A linked queue that retains both endpoints can append at the back and remove at the front with constant link changes. A dynamic array that shifts every remaining value after each front removal can turn a long processing sequence into quadratic work. A moving head index avoids that repeated shift but may retain consumed storage until compaction or reuse.
A circular buffer reuses capacity by wrapping indexes. Its implementation must distinguish a full buffer from an empty one and decide whether it grows, rejects, or overwrites when full. Those policies belong to the implementation contract; FIFO ordering alone does not choose them.
Connect FIFO order to graph distance
Breadth-first search uses a queue so vertices are expanded by increasing distance from the start in an unweighted graph. Newly discovered neighbors wait behind previously discovered vertices at the same or earlier depth. Replacing the queue with a stack changes that guarantee. A visited set remains necessary when the graph can cycle or offer several routes to the same vertex.
Continue with Implement a Queue to follow endpoint changes. Then study Breadth-First Search and Pilot a Rocket, where FIFO processing supports a shortest route measured in number of edges. Weighted shortest paths require additional reasoning and a different ordering policy.