AlgoVerse

Circular queue

A queue in a fixed-size array that wraps around to the start when it reaches the end; each enqueue and dequeue is O(1) and no space goes to waste.

A queue in a plain array has a problem: each dequeue at the front leaves an empty slot at the start of the array. A circular queue treats the array as a ring: after the last slot comes the first. So:

Read the full explanation ↓
Input:
n=10PDF export

Positive numbers are ENQUEUE and 0 means DEQUEUE; after some enqueues and dequeues, rear wraps from slot 4 to slot 0.

  1. def circular_queue(ops):
  2. # A positive number is enqueued; 0 dequeues. The queue lives in a fixed array of 5 slots.
  3. cap = 5
  4. buf = [None] * cap
  5. front = 0
  6. rear = 0
  7. size = 0
  8. out = []
  9. for op in ops:
  10. if op > 0:
  11. if size == cap:
  12. continue
  13. rear = (front + size) % cap
  14. buf[rear] = op
  15. size = size + 1
  16. else:
  17. if size == 0:
  18. continue
  19. out.append(buf[front])
  20. buf[front] = None
  21. front = (front + 1) % cap
  22. size = size - 1
  23. return out

Invariant: The queue's items are always the size slots from front on (wrapping around modulo the capacity).

Start

100201302030440550660770809

Local variables

Orange = changed in this step

ops list

10203000405060700

Call stack

  1. circular_queue()line 1
Step 1 of 72
Black = enqueue, dequeue · Orange = key stepenqueue: 0/7 · dequeue: 0/3
    Explanation

    The idea

    A queue in a plain array has a problem: each dequeue at the front leaves an empty slot at the start of the array. A circular queue treats the array as a ring: after the last slot comes the first. So:

    rear  = (front + size) mod cap
front = (front + 1) mod cap      (after a dequeue)

    Full or empty?

    With only front and rear, front = rear could mean full or empty. Here size is kept separately; Horowitz–Sahni always leave one slot empty to avoid the ambiguity instead.

    The input

    A positive number means ENQUEUE that number, and 0 means DEQUEUE. The capacity is 5.