Queues in practice

Build a deque-based task runner and implement BFS shortest-path on an adjacency-list graph.

Two programs that use a deque as their core data structure. The first is a minimal task scheduler; the second is BFS shortest-path — the algorithm that powers "degrees of separation" problems, social-graph features, and level maps in games.

Task queue and BFS shortest path

Python — editable, runs in your browser

from collections import deque

# ── Task queue ──────────────────────────────────────────────────────────────

def run_tasks(tasks):
  """Process tasks in FIFO order, returning the sequence of results."""
  queue = deque(tasks)
  results = []
  while queue:
      task = queue.popleft()
      results.append(f"processed: {task}")
  return results

# ── BFS shortest path ────────────────────────────────────────────────────────

def bfs(graph, start, goal):
  """Return the shortest path from start to goal as a list of nodes.

graph  — adjacency dict: {node: [neighbour, ...]}
  Returns an empty list if no path exists.
  """
  if start == goal:
      return [start]

visited = {start}
  # Each entry in the queue is the path taken so far.
  queue = deque([[start]])

while queue:
      path = queue.popleft()
      node = path[-1]

for neighbour in graph.get(node, []):
          if neighbour == goal:
              return path + [neighbour]
          if neighbour not in visited:
              visited.add(neighbour)
              queue.append(path + [neighbour])

return []   # no path found

# ── demo ─────────────────────────────────────────────────────────────────────

print("=== Task queue ===")
jobs = ["render frame 1", "render frame 2", "save file", "send email"]
for r in run_tasks(jobs):
  print(" ", r)

print()
print("=== BFS shortest path ===")

# Undirected graph stored as a directed adjacency list (both directions).
graph = {
  'A': ['B', 'C'],
  'B': ['A', 'D', 'E'],
  'C': ['A', 'F'],
  'D': ['B'],
  'E': ['B', 'F'],
  'F': ['C', 'E'],
}

pairs = [('A', 'F'), ('D', 'F'), ('A', 'A'), ('D', 'C')]
for s, g in pairs:
  path = bfs(graph, s, g)
  print(f"  {s} -> {g}: {' -> '.join(path) if path else 'no path'}")

How the BFS path-tracking works

Instead of storing just a node in the queue, we store the entire path from start to that node. When we dequeue a path, the last element is the current node. For each unvisited neighbour we append a new path that extends the current one by one step.

The first time we reach goal, the path in hand is guaranteed to be the shortest — no shorter path could arrive later, because shorter paths would have been dequeued first (BFS processes level by level).

The visited set is essential. Without it, BFS would re-enqueue nodes it has already explored, causing exponential blowup on any graph with cycles.

Storing the full path in the queue uses O(n) extra memory per path. For graphs where you only need the distance (not the actual path), store just the node and a separate dist dictionary — you save significant memory on large graphs.

Where to go next

Next: heaps and priority queues — when FIFO is not enough and you need to always process the most important item next.

Finished reading? Mark it complete to track your progress.

Task queue and BFS shortest path

How the BFS path-tracking works

Where to go next

On this page