In a circular-array queue, how do wrapping head and tail indices make dequeue O(1)?
answer
- nothing stored has to move
- the array's end is not the queue's end
- two numbers describe the whole state
- what wraps an index past the last slot
- advance the front position modulo capacity
basics
~20 sA circular-array queue never moves stored elements. Dequeue advances the front index by one modulo the array's capacity, and enqueue writes at the wrapped back position, so both are O(1) and freed front slots get reused.
solid answer
~50 sThe quadratic array queue moves the data to keep the front at slot 0. A circular queue moves the *index* instead: it keeps a `head` position and advances it modulo the capacity, so dequeue is a read plus one increment — O(1), no element touched. Enqueue writes at the wrapped back position and is O(1) too. Because both indices wrap, the slots freed at the front are reclaimed for later arrivals rather than abandoned, so a fixed array can serve an unlimited number of tickets as long as it never holds more than its capacity at one instant. The array itself is still an ordinary contiguous block — the circle exists only in the index arithmetic, which is why the live elements can legitimately sit in slots 6, 7, 0, 1 and still be in FIFO order.
code
pseudocode · 14 lines// array a[0..cap-1]; head = slot of oldest item; count = items held
enqueue(v):
if count == cap: return FULL
back = (head + count) mod cap
a[back] = v
count = count + 1
dequeue():
if count == 0: return EMPTY
v = a[head]
head = (head + 1) mod cap
count = count - 1
return vgo deeper
Know that a queue can be built on a fixed array where the front position moves instead of the data, and that both enqueue and dequeue are then constant time. Being able to draw the two indices on an eight-slot array is enough here.
Explain the arithmetic: the back position is derived from the front and the count, and taking positions modulo the capacity makes slot 0 the successor of the last slot. State plainly that no stored element ever changes address.
Show you can review one of these safely — that live items may legitimately wrap past the end, that dumping the raw array reads out of order, and that the fixed capacity forces a decision at the moment the array fills.
Frame the contiguous ring against a node-per-item design: equal asymptotics, very different constants, allocation behaviour and memory footprint. Be ready to justify the choice from measured locality and a memory budget, not from the complexity table.
## The idea in one line The expensive array queue keeps the front pinned to slot 0 and pays O(n) per dequeue to maintain that. A circular-array queue drops the pinning: it lets the front *be wherever it is* and tracks it with an index. Nothing stored ever moves, so both ends become O(1). ## The two pieces of state Take the ticket-intake buffer again: a fixed array of `cap` slots holding ticket records. Keep - `head` — the slot holding the oldest ticket, and - `count` — how many tickets are currently held. The back position is derived: `(head + count) mod cap`. Dequeue reads `a[head]`, sets `head = (head + 1) mod cap`, decrements `count`. Enqueue writes at the derived back position and increments `count`. Both are a handful of arithmetic operations and one memory access — genuinely constant time, independent of how many tickets are held. ## Why the modulo is the whole trick Memory is not circular. The array is a plain contiguous block, slots 0 through cap-1, and slot cap-1 has no physical neighbour. Taking every position modulo `cap` redefines the *successor* relation: the slot after cap-1 is slot 0. That single arithmetic convention turns a straight line of storage into a ring of positions, and once positions form a ring, "the front advanced" never runs off an end. This is why a live queue can occupy slots 6, 7, 0, 1 of an eight-slot array and be perfectly healthy. Read in FIFO order starting from `head` and wrapping, the order is exactly arrival order. It is only if you iterate the raw slots 0..cap-1 that it looks scrambled — a real reading bug when someone debugs by dumping the backing array. ## What it buys, precisely - **Dequeue: O(1) worst case**, not amortized. No copying is deferred and none is hiding; the cost is the same every time. - **Space: bounded and reused.** A non-wrapping `head` index also gives O(1) dequeue, but it abandons the prefix: after cap dequeues the array is full of dead slots and you must compact or reallocate. Wrapping reclaims each freed slot for the next arrival, so a queue that sees a million tickets pass through never needs more than its capacity in memory. - **Locality.** Elements stay in one contiguous block with no per-node headers or pointer chasing, which is usually why a contiguous queue beats a linked one in practice at equal asymptotics. ## What it costs The capacity is fixed at the moment of allocation. When `count == cap`, the enqueue cannot simply write, and the implementation must do one of two things: refuse the item and report that, or allocate a larger array and copy the live elements out in FIFO order — starting at `head` and wrapping — into slots 0..count-1 of the new array. That copy is O(n), and under growth doubling it amortizes to O(1) per enqueue, exactly as for a plain dynamic array. Note that the copy is *not* the shifting defect coming back: it happens once per doubling, not once per dequeue. Which of those two behaviours the queue exposes is an interface decision rather than a mechanical one, and it is decided by whether the queue is allowed to consume memory without a ceiling. ## The mental model that keeps you correct Think of the array as a window and the queue as a stretch of arrival order sliding through it. `head` says where the stretch begins; `count` says how long it is; `mod cap` says the window's right edge is stitched to its left edge. Every queue operation is a small edit to those two numbers, and no ticket record ever changes address between the moment it is enqueued and the moment it is served. That property — *stored elements never move* — is the actual content of the O(1) claim, and it is the sentence to say out loud in an interview. ## Common misreadings "Circular" does not mean unbounded: the ring has a fixed number of slots and holding more than `cap` items at once is impossible without growing. "Circular" does not mean elements get relocated to the start when they wrap — they are written wherever the arithmetic points and stay there. And the O(1) here is not an amortized dodge: unlike the growth-doubling append, one dequeue really is constant work, every time.
- Physical memory is not circular — so what actually makes the array behave that way?Only the index arithmetic. The storage stays an ordinary contiguous block; taking positions modulo the capacity redefines the successor of slot cap-1 as slot 0. The ring lives in the index space, not in the memory layout, which is why the trick costs nothing beyond one modulo per operation.
- What happens when the circular array fills up?Either the enqueue is refused and reports that, or a larger array is allocated and the live elements are copied out in FIFO order starting at the front index and wrapping. The copy is O(n), amortized to O(1) per enqueue under growth doubling. Which behaviour the queue exposes is an interface choice, not a consequence of the data structure.
- Why not just advance a front index without wrapping?It gives the same O(1) dequeue but leaks space: every dequeued slot is abandoned, so after `cap` removals the array is exhausted even if the queue is empty, forcing a compaction or reallocation. Wrapping recycles each freed slot, letting a fixed array serve an unbounded number of items as long as the instantaneous depth stays within capacity.
Seats numbered around a round table. When the person in seat 1 leaves, nobody slides over; you just remember that the queue now starts at seat 2, and seat 1 is free for the next arrival.
saying these in an interview costs you the question
- The circular queue moves elements back to the start
- Wrapping indices make the queue unbounded
- Read slots 0 through count-1 to see queue order
- The modulo makes each operation logarithmic
- A queue whose items wrap past the end is corrupted