Visual walkthrough — Queue — FIFO semantics, enqueue - dequeue, circular array implementation

We derive the whole circular queue from zero. No prior formula assumed.

Step 0 — The words we will use

Before any symbol, plain meanings. Keep these five in your head:

Everything below is made of only these five ideas.

Step 1 — Lay out the boxes, put the front at the left

WHAT. Draw an empty array of $N=5$ boxes, numbered $0$ to $4$. Nothing is inside yet, so $\text{count}=0$ and we park $\text{front}=0$.

WHY. We need a fixed reference point. front is our only memory of "where the line begins." We start it at $0$ purely by convention — any index would do, but $0$ is tidy.

PICTURE. The boxes are empty. The green arrow labelled front sits under box $0$. No coral (data) anywhere yet.

$\text{count}=0⟺\text{queue is empty}$

• $\text{count}$ — the running tally of elements. Here it is $0$.
• The double arrow $⟺$ means "these two statements are the same thing." An empty queue is exactly the case $\text{count}=0$ — no other test needed.

Step 2 — Enqueue: where does a new element go?

WHAT. We enqueue(A). The element must land in the box just after the last occupied box. With nothing inside, the "box just after front" is front itself.

WHY. The elements always sit in a solid block starting at front. If there are $\text{count}$ of them starting at front, the next free slot is $\text{count}$ steps past front. Right now $\text{count}=0$, so the next slot is $\text{front}+0=0$.

PICTURE. Box $0$ turns coral, labelled A. front still points at box $0$. A new dashed arrow, rear, marks "the next free slot," which after placing A now sits at box $1$.

$\text{rear}=\text{front}+\text{count}$

• $\text{front}$ — where the block starts ($0$).
• $\text{count}$ — how long the block is (was $0$, so rear was $0$; after adding A, $\text{count}=1$ so rear $=1$).
• $\text{rear}$ — the index of the next free box, i.e. where the next enqueue will write.

No modulo yet — nothing has fallen off the end. We add it exactly when we need it, in Step 5.

Step 3 — Fill up, watch the block grow rightward

WHAT. Enqueue B, then C. Each time: write at rear, then $\text{count}$ grows by $1$.

WHY. Every enqueue lengthens the block by one, so the "next free slot" $\text{rear}=\text{front}+\text{count}$ slides one box to the right each time. front never moves during enqueue — the oldest element (A) is untouched.

PICTURE. Boxes $0,1,2$ are coral: A, B, C. front stays at $0$; rear has walked to box $3$. The occupied block is highlighted in mint.

$\text{after 3 enqueues:}\text{front}=0,\text{count}=3,\text{rear}=0+3=3$

• $\text{front}=0$ — unchanged; enqueue never touches the front.
• $\text{count}=3$ — three elements A, B, C.
• $\text{rear}=3$ — the free box where a fourth element would go.

Step 4 — Dequeue: the front walks forward, a gap opens on the left

WHAT. dequeue() twice. Each removes the element at front (returning A, then B), then moves front one box to the right.

WHY. FIFO = the oldest leaves first. The oldest is always at front. After handing it out, the new oldest is the box one step right, so front advances by $1$. Crucially, $\text{count}$ shrinks by $1$ — so the rear formula still balances.

PICTURE. Boxes $0,1$ are now empty (a grey "wasted" gap on the left). front points at box $2$ (C). Notice the empty boxes on the left — this is the seed of the whole problem.

$\text{front}\leftarrow (\text{front}+1),\text{count}\leftarrow (\text{count}-1)$

• The arrow $\leftarrow$ means "gets updated to."
• After two dequeues: $\text{front}=2$, $\text{count}=1$ (only C remains), so $\text{rear}=2+1=3$ still.

Step 5 — The wrap: glue box $N-1$ to box $0$ with modulo

WHAT. Now $\text{front}=2$, $\text{count}=1$ (only C, at box $2$). Enqueue D, then E. The first goes to box $3$. But the next rear wants to be box $4$... then box $5$, which does not exist. We wrap it back to box $0$.

WHY THIS TOOL — the modulo. We need an operation that takes any index and folds it back into the valid range $0\dots N-1$, turning the straight row into a ring. That operation is modulo, written $\mathrm{mod}$. Why modulo and not, say, an if index == N: index = 0? Because modulo handles every overshoot in one stroke — even jumps of more than one — and is the exact mathematical statement of "positions on a ring of size $N$." $a\mathrm{mod}N$ answers the question: "if I walk $a$ steps around a ring of $N$ boxes starting at $0$, which box do I land on?"

$\text{rear}=(\text{front}+\text{count})\mathrm{mod}N$

• $\text{front}+\text{count}$ — the un-wrapped target: how far past box $0$ we would be on an infinite row.
• $\mathrm{mod}N$ — folds that number back onto the ring of $N$ boxes. E.g. $(2+2)\mathrm{mod}5=4$; $(2+3)\mathrm{mod}5=0$ ← the wrap.
• $\text{rear}$ — the real box index, always in $0\dots N-1$.

PICTURE. The array is redrawn as an actual ring of $5$ boxes. Box $4$ sits next to box $0$. D lands in box $3$; E wraps around into box $0$. front (green) at box $2$, rear sweeping to box $1$. The logical order following the ring clockwise is C → D → E.

Let's verify the wrap with a tiny $N=4$ ring (the parent's Example 2): $\text{front}=2$, $\text{count}=2$, holding A at box $2$, B at box $3$. Enqueue C: $\text{rear}=(2+2)\mathrm{mod}4=4\mathrm{mod}4=0.$ So C lands in box $0$ — physically at the "start," logically at the "end." Impossible to get right without $\mathrm{mod}$.

Step 6 — dequeue also wraps, for the same reason

WHAT. When front itself reaches the last box and we dequeue, it too must jump back to box $0$.

WHY. front walks the same ring. The instant it would step off the right edge it must reappear at $0$ — identical logic to rear. So the update carries the same $\mathrm{mod}N$.

PICTURE. front is at box $4$ (last box). One dequeue: green arrow leaps across the glued seam to box $0$.

$\text{front}\leftarrow (\text{front}+1)\mathrm{mod}N$

• $\text{front}+1$ — step one box clockwise.
• $\mathrm{mod}N$ — if that was box $N$ (off the edge), fold it to box $0$.

Example on $N=5$: $\text{front}=4\Rightarrow (4+1)\mathrm{mod}5=0$. ✅

Step 7 — The degenerate twins: full and empty look identical (without count)

WHAT. Consider a ring with only a front and a rear index and no count. Empty: $\text{front}=\text{rear}=0$. Now fill all $N$ boxes: rear wraps all the way back to $\text{front}$. Both give $\text{front}=\text{rear}$.

WHY IT BREAKS. The single test $\text{front}==\text{rear}$ is being asked to mean two opposite things at once — a full ring and an empty ring produce the identical picture. A test that cannot tell a full room from an empty room is useless.

PICTURE. Two rings side by side: left one all-grey (empty), right one all-coral (full). Both have front and rear arrows stacked on the same box. Same pointers, opposite meaning.

THE FIX — track count, and the ambiguity vanishes: $\text{empty}⟺\text{count}=0,\text{full}⟺\text{count}=N.$

• $\text{count}=0$ — zero elements. Unmistakably empty.
• $\text{count}=N$ — all $N$ boxes used. Unmistakably full.

Because $0\ne N$ (for any real capacity $N\ge 1$), these two states can never be confused. This is why the reference code carries count instead of a rear index.

The one-picture summary

Everything on one canvas: the ring of $N$ boxes, front (green) pointing at the oldest element, the occupied block sweeping clockwise, rear (dashed) marking the next free box, and the two master formulas glued to the seam where the wrap happens.

$\boxed{\text{rear}=(\text{front}+\text{count})\mathrm{mod}N}\boxed{\text{front}\leftarrow (\text{front}+1)\mathrm{mod}N}$ $\text{empty}⟺\text{count}=0\text{full}⟺\text{count}=N$

This structure is the beating heart of a ring buffer, powers the frontier in Breadth-First Search (BFS), and generalises to the deque and priority queue. Its per-operation cost is a flat $O(1)$ — see Amortized Analysis for why "no shifting, ever" matters.

Active Recall