Algorithms / Queue Fifo Bfs Simulation
Least You Need to Know: Queues, FIFO Order, and Level-by-Level Simulation
Queues model situations where the earliest discovered or earliest arrived item should be processed first. That makes queues the natural frontier structure for breadth-first search and many step-by-step simulations.
The least you need to know
- A queue is first in, first out.
- Breadth-first search uses a queue to process a frontier level by level.
- Discovered states are often marked visited when enqueued to avoid duplicates.
- The current queue length can separate one BFS layer from the next.
- Queues also model arrival/service systems where order matters.
Key notation
enqueue
add an item at the back of the queue
dequeue
remove the oldest item from the front
frontier
currently discovered but not yet processed states
Tiny worked example
- In BFS from a source node, enqueue the source first.
- Repeatedly dequeue one node, then enqueue its unseen neighbors.
- Because earlier layers were enqueued first, they are processed before deeper layers.
- That yields shortest-path distances in unweighted graphs.
Common mistakes
- Students sometimes mark visited only when dequeuing, which can allow duplicate enqueues.
- FIFO order is what keeps BFS layered.
- A stack would produce depth-first behavior instead.
How to recognize this kind of problem
- The task processes items in order of discovery or arrival.
- The prompt mentions layers, minutes, days, or rounds spreading outward.
- The oldest waiting item should be handled next.
Next recommended lesson
Continue through this topic with Least You Need to Know: Recursion Trees and Recurrence Intuition.
Least You Need to Know: Recursion Trees and Recurrence IntuitionRelated lessons
Keep going with nearby lessons in the same topic.