Skip to content

List-backed queues with a read index [ref]

Problem

  • Read values from q = [1, 2] using a head index while appending 3 during iteration.
  • Preserve the first two items as one level before appending 3.
  • Verify that indexing the queue does not remove already read entries.

Python solution

q = [1, 2]
head, seen = 0, []
while head < len(q):
    value = q[head]
    head += 1
    seen.append(value)
    if value == 1:
        q.append(3)
(seen, head)  # ([1, 2, 3], 3)

q = [1, 2]
level_size = len(q)
q.append(3)
[q[i] for i in range(level_size)]  # [1, 2]

(q, q[0])  # ([1, 2, 3], 1)