Design Circular Queue

Ring Buffer

Design a fixed-capacity first-in, first-out queue on one array: two indexes that wrap around, a size counter that tells full from empty, and every operation in O(1).

Overview

A circular queue, also called a ring buffer, is a queue that lives in one array of fixed size. Elements enter at the back and leave at the front, as in any queue, but instead of shifting everything forward after a dequeue, the queue keeps two indexes that move through the array and wrap to index 0 when they reach the end. The array is treated as a ring.

The interview version asks for enqueue, dequeue, peek, is_empty and is_full, all in O(1), with the capacity fixed when the queue is created. The problem is small, so the interviewer watches the details: the wrap with modular arithmetic, and the one real trap, that a queue whose front and back indexes are equal can be either empty or full. A size counter settles that in one line.

Ring buffers are how bounded buffers are built in practice. Java's ArrayBlockingQueue is an array-backed FIFO queue whose capacity cannot change after construction; Python's collections.deque takes a maxlen and drops from the far end when full; the Linux kernel's kfifo rounds its size up to a power of two so the wrap is a bit mask. Knowing which behavior each one picks when full is a good closing point.

Scoping the problem

What happens on enqueue when full? — Reject, block, or overwrite the oldest; three different queues — Reject and return False; the others are follow-ups
What happens on dequeue when empty? — Return a sentinel or raise — Raise IndexError, as list.pop does
Is the capacity fixed? — A growing ring needs a copy that preserves order — Fixed
Do we need peek and len? — Cheap to add; len needs the size counter — Yes
Many threads? — Turns the ring into a bounded buffer with a lock and two conditions — Follow-up
What are the elements? — Anything; the queue never inspects them — Any object

The ring

Two indexes: front is where the next dequeue reads, back is where the next enqueue writes. Both advance with (i + 1) % capacity, so after the last slot comes slot 0.

The trace below runs the code on a queue of capacity 3, far enough to wrap. Slots show the array; a dot is an empty slot.

1 — enqueue(1) — 1 . . — 0 — 1 — 1 — True
2 — enqueue(2) — 1 2 . — 0 — 2 — 2 — True
3 — enqueue(3) — 1 2 3 — 0 — 0 — 3 — True; back wrapped to 0
4 — enqueue(4) — 1 2 3 — 0 — 0 — 3 — False: full
5 — dequeue() — . 2 3 — 1 — 0 — 2 — 1
6 — enqueue(4) — 4 2 3 — 1 — 1 — 3 — True: slot 0 is reused
7 — dequeue() three times — . . . — 1 — 1 — 0 — 2, 3, 4 in order
8 — dequeue() — . . . — 1 — 1 — 0 — raises IndexError

After step 3 and after step 7, front == back. One state is full and the other is empty. Only the size counter tells them apart.

Full or empty?

Size counter (the code) — size == 0 is empty, size == capacity is full — One integer; every operation updates it — Simple queues; also gives len for free
Waste one slot — Full when (back + 1) % capacity == front; the array holds capacity minus 1 items — No counter, but one slot is never used — Classic textbook version
Free-running counters — in and out count every write and read forever; in - out is the size and in & mask the slot; needs a power-of-two capacity — Two integers that may overflow, which unsigned arithmetic makes harmless — Linux kfifo, whose size is rounded up to a power of two

What to do when full

The core design rejects an enqueue on a full queue. The two other behaviors are common, and each is a small change to the same code.

Reject — Returns False or raises — Callers that can retry or drop — The LeetCode-style problem
Block — Waits until a dequeue makes room — Producer and consumer threads — Java ArrayBlockingQueue.put, Python queue.Queue(maxsize)
Overwrite — Drops the oldest element and writes the new one — Logs and metrics, where the latest values matter most — Python deque(maxlen=n) discards from the opposite end

Complexity

enqueue, dequeue, peek — O(1) — One index read, one write, one modulo
is_empty, is_full, len — O(1) — Compare the size counter
Memory — O(capacity) — The array is allocated once; no per-element nodes

Contrast with a plain Python list used as a queue: pop(0) shifts every remaining element, which the collections documentation describes as an O(n) memory move. A ring buffer never shifts anything.

What you will be able to do

Write the ring with two wrapping indexes and a size counter, and trace it through a wrap by hand.
Explain why front == back is ambiguous and name three ways to resolve it.
Choose reject, block or overwrite when the queue is full, and name a library that does each.
Turn the ring into a thread-safe bounded buffer with a lock and two conditions.
Compare a ring buffer with a linked-list queue and a plain list.

Functional requirements

enqueue(value) adds at the back and returns True, or returns False when the queue is full
dequeue() removes and returns the front element, or raises IndexError when empty
peek() returns the front element without removing it, or raises IndexError when empty
is_empty(), is_full() and len() report the state
Capacity is fixed at construction and must be positive
Order is first in, first out, across any number of wraps

Non-functional requirements

Every operation runs in O(1) time
Memory is O(capacity), allocated once; no allocation per element
A dequeued slot is cleared so the queue does not keep a reference alive
The class is not thread-safe by itself; the bounded-buffer variant adds a lock and conditions

Interview questions

Why keep a size counter? Comparing front and back seems enough.
How would you make it a bounded buffer for producer and consumer threads?
Ring buffer or linked-list queue? When would you pick each?
How would you let the queue grow when it is full?
What bugs do people write in this problem?