Skip to content
Tutorials Center
My learning

Topics

Lesson 48 of 225 ยท Stacks and Queues

Queue Puzzles: Binary Numbers, Snakes and Ladders, Stack from Queues, k Queues

Practice queue problems in Python: generate binary numbers 1 to n, find the fewest dice throws in Snakes and Ladders, build a stack from queues and share one array between k queues.

A queue is first in, first out. That one rule powers a surprising number of puzzles, because a queue naturally produces things in order of discovery: shortest paths, level-by-level generation, fair scheduling. This lesson collects four classic queue exercises.

You will generate binary numbers from 1 to n with nothing but a queue, solve Snakes and Ladders as a shortest-path problem with BFS, implement a stack using queues (the reverse of the usual direction), and store k queues in one array with a shared free list. Read Queues and Circular Queues first; the Snakes and Ladders part builds directly on breadth-first search.

Binary numbers 1 to n with a queue

How do you print 1, 10, 11, 100, 101, ... without converting each integer? Notice that every binary number s has two children, s + "0" and s + "1", and that visiting them level by level gives increasing numbers. That is a BFS over an infinite binary tree, and a queue does it:

  1. Start with "1" in the queue.
  2. Repeat n times: pop s, output it, push s + "0" and s + "1".
Python Binary numbers by BFS

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The queue holds at most about n strings, so time and space are O(n) strings (each of length up to log n). The same idea generates numbers made only of digits 5 and 6, or all binary-tree level orders, in increasing order.

Snakes and Ladders: fewest dice throws

The board has squares 1 .. n*n. You start on 1 and need to reach the last square. Each turn you throw a die (1 to 6) and move forward. If you land on the bottom of a ladder you climb to its top; if you land on a snake's head you slide to its tail. What is the minimum number of throws?

Treat every square as a graph node and every die outcome as an edge of equal cost. Equal edge costs mean BFS finds the shortest path. A small twist: apply the snake/ladder jump when you land, but a jump does not count as an extra throw, and you do not chain it with another throw.

Python Snakes and Ladders with BFS

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

For the first board, 3 -> 22 and then a throw or two reaches 30, so the answer is small. If the target square cannot be reached (for example, six snakes in a row), BFS runs out of squares and the function returns -1.

On a real board the squares zigzag (row 1 goes left to right, row 2 right to left). If your input is a 2D grid, convert a square number to coordinates first; if the input is a flat list of jumps, you can ignore the zigzag entirely, as above.

A stack using queues

Now the opposite direction. Implement push, pop and top of a stack using only queue operations (append, popleft, len). There are two classic choices; which operation is expensive?

Make push costly (one queue). After appending the new item, rotate the queue so the new item moves to the front: move the previous len - 1 items from the front to the back. Then pop and top are O(1) because the newest element is always at the front.

Python Stack built from a queue

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Either way, one of the two operations costs O(n). That is a real trade-off: you cannot get both O(1) push and O(1) pop from queue primitives alone (an amortized trick like the one for queues from two stacks does not carry over, because reversing order with a queue destroys the order again).

k queues in one array

Just like k stacks in an array, k queues can share one array of n slots without wasting space. A queue needs both a front and a rear, so we keep:

  • front[q] and rear[q]: slot indexes of each queue's ends (-1 when empty).
  • nxt[i]: the slot behind slot i toward the rear of its queue, or the next free slot if i is free.
  • free: head of the free list.

Enqueue takes a free slot and links it after the current rear. Dequeue unlinks the front slot and returns it to the free list. All operations are O(1).

Python k queues sharing an array

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Common mistakes

  • Chaining a jump with another throw in Snakes and Ladders. A ladder top that is itself a snake head is a separate rule; most definitions apply only one jump per landing.
  • Marking squares as visited too late. Mark a node when you enqueue it, or the queue will contain duplicates.
  • Using list.pop(0) as a queue. It is O(n); use collections.deque.
  • Forgetting to reset rear when a queue becomes empty in KQueues.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Why does a queue generate binary numbers in increasing order?

    Each number s produces s0 and s1; FIFO order processes all numbers of a given length before longer ones, and within a length they are in order.
  2. 2. Why is BFS enough to find the minimum number of dice throws?

    With all edges costing one throw, BFS explores squares in order of throw count.
  3. 3. Building a stack from a single queue so that pop is O(1) makes which operation O(n)?

    push rotates the older items behind the new one so that the newest item is at the front.
  4. 4. In the k-queues-in-one-array design, what does the free list guarantee?

    Any queue can take any free slot, so there is no wasted space reserved per queue.

Summary

  • A queue generates binary numbers 1..n in order: pop s, push s + "0" and s + "1".
  • Snakes and Ladders is a shortest path with equal edge costs, so BFS gives the minimum number of throws.
  • A stack from queues must make either push or pop cost O(n).
  • k queues in one array share a free list for O(1) enqueue and dequeue and no wasted slots.

Next: Priority Queues, where "first in" becomes "most important first".