Why does dequeuing from a ring buffer cost O(1) when a shift-down array queue costs O(n)?
answer
- does the data actually move?
- count the writes per dequeue
- two cursors into one fixed array
- what follows the last slot
- advance an index modulo capacity
basics
~20 sA ring buffer moves an index instead of data: dequeue reads the slot at head, then advances head by one, wrapping to zero past the last slot. Nothing is copied. A shift-down queue relocates every remaining element.
solid answer
~50 sA ring buffer stores items in one fixed array and keeps two cursors: `head`, the oldest item, and a write position for the newest. Dequeue reads `a[head]` and sets `head = (head + 1) mod N` — a single index update, so no element ever moves. Enqueue does the mirror image at the write end. Because the array is treated as a circle, the slots vacated at the front are reused when the write cursor wraps, which is exactly what the shift-down design is paying O(n) to achieve: it physically slides every surviving element one position left so index 0 is always the front. Both ends are O(1) worst case, not amortized, since there is no copying and no reallocation. The price is a capacity fixed up front and a policy for what happens when the buffer is full.
code
pseudocode · 10 lines// a = fixed array of N slots; head = index of the oldest item
// count = number of items currently stored
dequeue():
if count == 0:
return EMPTY
x = a[head]
head = (head + 1) mod N // after the last slot, wraps to 0
count = count - 1
return xgo deeper
Be ready to say plainly that dequeue moves an index, not data, and to write the wraparound expression for advancing that index. Knowing which two pieces of state a ring buffer keeps is the whole screening question.
Explain why the vacated front slots get reused rather than leaked, why both operations are worst-case and not amortized constant, and how you reach the i-th oldest item without walking.
Show you know what the fixed capacity buys and costs: no allocation on the hot path, a predictable memory ceiling, and a mandatory decision about the write that has nowhere to go.
Own the choice between a ring and an unbounded queue as a systems tradeoff — bounded memory and no per-item allocation against the need to decide, up front and in public, what the system does when the bound is reached.
## The problem A queue needs O(1) at both ends: append at the back, remove from the front. A plain array gives you a cheap back — write at the next free slot — but an expensive front. If you insist that the front item always lives at index 0, then removing it means sliding every other element down one position: n-1 copies, O(n) per dequeue, O(n^2) to drain a full queue. The obvious repair is to stop sliding and just remember where the front is: keep a `head` index and advance it on removal. That fixes the copying but leaks the array — the slots before `head` are dead space that never gets reused, so a queue that processes a million items needs a million slots even if it never holds more than ten at a time. ## The insight A ring buffer reuses that dead prefix by treating the array as a circle. The state is: - `a` — one allocation of N slots, the capacity, fixed at construction - `head` — the index of the oldest stored item - and either a `tail` (the next slot to write) or a `count` of stored items; you need something beyond `head` alone Wraparound is the whole trick: `(i + 1) mod N` sends the last index back to 0 instead of off the end. Dequeue becomes read-then-advance-head; enqueue becomes write-then-advance-tail. Neither touches any other element, so both are O(1) in the worst case — genuinely worst case, not amortized, because nothing is ever copied and nothing is ever reallocated. Random access survives too: the i-th oldest item lives at `a[(head + i) mod N]`, still O(1). What you lose is not indexing but *contiguity of logical order*. ## Cost comparison | Design | Enqueue | Dequeue | i-th oldest | Per-item overhead | |---|---|---|---|---| | Shift-down array queue | O(1) | O(n) | O(1) | none | | Array with advancing head, no wrap | O(1) | O(1) | O(1) | grows without bound | | Ring buffer | O(1) | O(1) | O(1) | none, one allocation | | Linked-list queue | O(1) | O(1) | O(n) | a link per element, plus an allocation per element | The linked list matches the ring on the queue operations and is unbounded, which sounds strictly better until you count what it costs per element: an allocation, a pointer, and a scattered memory layout that defeats prefetching. The ring is one contiguous block written in a predictable stride, which is why it is the default in real-time, embedded and streaming paths where allocation is banned and the memory ceiling is fixed. ## What you give up **Capacity is decided in advance.** That is the deal: fixed memory in exchange for no allocation. It forces a decision the unbounded designs let you postpone — what happens on the write that has nowhere to go. Overwriting the oldest and rejecting the newest are both legitimate; picking by accident is not. **Logical order can straddle the wrap.** After the write cursor has wrapped, the stored items occupy two physical ranges: `head..N-1` and `0..tail-1`. Iteration handles that fine, but any consumer that wants one contiguous view of the contents has to do two copies, or re-linearize. **Growing is not free.** You can grow a ring — allocate a larger array, copy the items out in logical order so they start at index 0, reset the cursors — but that copy is O(n), and it throws away the fixed-footprint property that motivated the ring in the first place. If you find yourself growing routinely, the ring was the wrong choice. ## Invariants worth stating out loud In an interview, name them: the stored items are exactly the slots from `head` forward for `count` positions, taken modulo N; `count` is between 0 and N; `head` and the write cursor are always in `0..N-1`; and no operation reads or writes a slot outside that live span. Most ring-buffer bugs are a violation of one of those four, not a failure of the idea.
- After the write cursor has wrapped, where do the stored items sit in memory, and why does that matter?They sit in two physical ranges: from `head` to the end of the array, then from index 0 up to the write cursor. Iteration is unaffected, but anything that wants a single contiguous view — a bulk copy, a range handed to a writer — has to do it as two segments, or re-linearize into a fresh buffer. Forgetting the second segment is one of the most common ring-buffer bugs.
- Can a ring buffer grow, and what does growth cost?Yes: allocate a larger array, copy the items out in logical order so the oldest lands at index 0, then reset head to 0 and the write cursor to the item count. The copy is O(n), amortized O(1) per item if you double. But growth forfeits the fixed-footprint guarantee that made the ring attractive, so a ring that grows routinely is usually the wrong structure for the job.
A row of numbered lockers with two chalk marks: one on the oldest occupied locker, one on the next free one. Emptying a locker moves a chalk mark, not the contents of every other locker.
saying these in an interview costs you the question
- Says elements shift down when the head index advances
- Thinks a ring buffer is a circular linked list
- Claims a ring buffer can grow without copying
- Believes indexing into a wrapped buffer is O(n)
- Calls the O(1) dequeue amortized rather than worst case