Queue — FIFO semantics, enqueue - dequeue, circular array implementation: Worked examples

You have met the parent queue note and its rules. Now we hunt down every situation a circular-array queue can face and solve each one by hand, index by index. The goal: after this page, no queue scenario can surprise you.

Before we start, one reminder of the machine we are driving. A circular queue is described by exactly three numbers plus the array:

The scenario matrix

Every queue exercise is really one of these cells. We will hit all of them.

#	Case class	What makes it tricky	Example
A	Plain FIFO, no wrap	baseline: does order come out right?	Ex 1
B	Rear wraps past the end	`rear` falls off, must reappear at 0	Ex 2
C	Front wraps past the end	`front` itself crosses the seam	Ex 3
D	Fill to full, then reject	`isFull` boundary, overflow	Ex 4
E	Drain to empty, then reject	`isEmpty` boundary, underflow	Ex 5
F	Full vs empty ambiguity	why `front==rear` is not enough	Ex 6
G	Degenerate capacity $N = 1$	smallest possible ring	Ex 7
H	Real-world word problem	BFS-style level processing	Ex 8
I	Exam twist: reconstruct state	given a snapshot, find front/count	Ex 9

Cells A–G are the mechanical cases. H connects to Breadth-First Search (BFS). I is the kind of gotcha exams love. (Capacity $N = 0$ is the invalid case flagged above — no worked example, because no operation is defined.)

Throughout, I draw the array as a ring of chairs so the wrap is visible. Filled chairs are burnt orange, the front chair has a teal marker, the rear (next-free) chair has a plum marker.

Case A — plain FIFO, no wrap

Worked example Example 1 (cell A)

Start empty, $N = 5$ . Do: enqueue(10), enqueue(20), enqueue(30), dequeue(), dequeue(). What comes out, and in what order?

Forecast: guess the two returned values before reading on. (First-in leaves first — so...?)

Start: front=0, count=0. Why this step? We must fix the starting state; every later index is computed from it.
enqueue(10): rear $= (0 + 0) mod 5 = 0$ , write arr[0]=10, count=1. Why this step? The next free slot is front+count; with nothing stored yet that is slot 0.
enqueue(20): rear $= (0 + 1) mod 5 = 1$ , arr[1]=20, count=2. Why this step? One element already sits at slot 0, so the next arrival goes one slot further along — front+count = 0+1.
enqueue(30): rear $= (0 + 2) mod 5 = 2$ , arr[2]=30, count=3. Array: [10,20,30,_,_]. Why this step? Two elements occupy slots 0,1; the rear formula automatically points at slot 2, the first free one.
dequeue(): read arr[front]=arr[0]=10, then front=(0+1)\bmod 5 = 1, count=2. Returns 10. Why this step? Dequeue always reads at front then advances front — the oldest leaves.
dequeue(): read arr[1]=20, front=(1+1)\bmod 5 = 2, count=1. Returns 20. Why this step? After the first dequeue front pointed at slot 1 (holding 20), so the next-oldest element is 20 — advancing front again exposes 30.

Read the figure: the teal front arrow rests on idx 2 and the plum rear arrow on idx 3 — exactly the final state. The single orange chair (holding 30) confirms count=1; the gap of empty cream chairs to its right is the space 10 and 20 vacated.

Verify: 10 entered before 20, and 10 left before 20 — FIFO holds. Final state front=2, count=1 still holds 30 at arr[2], and rear $= (2 + 1) mod 5 = 3$ points at the next free slot. ✅

Case B — the rear wraps

This is the reason circular queues exist. Watch rear fall off the right edge and land at 0.

Worked example Example 2 (cell B)

$N = 4$ . Current state: front=2, count=2, array [_, _, A, B] (A at idx 2, B at idx 3). Do enqueue(C).

Forecast: the two occupied slots are 2 and 3. Where can C possibly go?

Compute rear: rear $= (2 + 2) mod 4 = 4 mod 4 = 0$ . Why this step? front+count = 4 walks past the last index (3); $mod 4$ folds it back to the start.
Write: arr[0]=C, so array = [C, _, A, B], count=3, front unchanged at 2. Why unchanged? Enqueue never touches the front; only arrivals at the rear.

Read the figure: trace the two orange chairs at idx 2 (A) and idx 3 (B), then follow the ring clockwise off the top back to idx 0 — where the newly-added C now sits (also orange). The plum rear arrow lands on idx 1, the next free slot after C. This picture is the wrap: physically C precedes A, logically it follows B.

Verify: logical order front→rear is arr[2], arr[3], arr[0] = A, B, C — exactly the arrival order, even though physically C sits before A in the array. Without the modulo, step 1 would give index 4 → out-of-bounds crash. ✅

Case C — the front wraps

Case B wrapped the rear. Now the front itself crosses the seam during a dequeue.

Worked example Example 3 (cell C)

Continue Example 2: state front=2, count=3, array [C, _, A, B]. Do dequeue(), then dequeue().

Forecast: which element leaves first, and at what point does front land on index 0?

dequeue #1: read arr[front]=arr[2]=A. Then front=(2+1)\bmod 4 = 3, count=2. Returns A. Why this step? A is the oldest (it entered before B and C), so FIFO must release it first; advancing front to 3 exposes B as the new oldest.
dequeue #2: read arr[3]=B. Then front=(3+1)\bmod 4 = 0, count=1. Returns B. Why this step? front was at the last index 3; advancing gives 4, and $4 mod 4 = 0$ — the front crosses the seam and now sits at index 0, where C lives.

Read the figure: only one orange chair remains — C at idx 0 — and the teal front arrow now points straight at it, having jumped across the top seam from idx 3. The plum rear arrow sits at idx 1. Compare with the s02 figure: A and B have vanished, and front has visibly wrapped.

Verify: remaining element is C at arr[0], with front=0, count=1, rear $= (0 + 1) mod 4 = 1$ . Order out so far: A, B — still FIFO. The next dequeue would return C. ✅

Case D — fill to full, then reject

Worked example Example 4 (cell D — the

isFull boundary) $N = 3$ , empty. Do enqueue(1), enqueue(2), enqueue(3), then enqueue(4).

Forecast: three slots, four arrivals. What must the fourth do?

enqueue(1): rear $= (0 + 0) mod 3 = 0$ , count=1. Why this step? Empty queue → first arrival takes slot 0, the only free-and-lowest index.
enqueue(2): rear $= (0 + 1) mod 3 = 1$ , count=2. Why this step? One element sits at slot 0; the rear formula advances to slot 1 automatically.
enqueue(3): rear $= (0 + 2) mod 3 = 2$ , count=3. Now count == N, so isFull is true. Why this step? Slots 0,1 are taken; slot 2 is the last free one — filling it brings count up to the capacity $N = 3$ .
enqueue(4): is_full() returns count==N → 3==3 → true, so the code raises OverflowError — element 4 is rejected. Why this step? All three physical slots hold live data; there is genuinely nowhere to put it. OverflowError is the guard defined above: it stops the write before any slot is clobbered. This is a real full, not a phantom "walked off the end" full.

Verify: the test fired at exactly count=3=N, not one early or one late. Array [1,2,3], front=0. Notice rear would have been $(0 + 3) mod 3 = 0$ = front — which is why we can't use rear==front to mean "not full"; see Ex 6. ✅

Case E — drain to empty, then reject

Worked example Example 5 (cell E — the

isEmpty boundary) Continue Ex 4: [1,2,3], front=0, count=3. Do three dequeues, then a fourth.

Forecast: what order comes out, and what does the fourth dequeue do?

dequeue: arr[0]=1, front=1, count=2. Returns 1. Why this step? 1 is the oldest element (it entered first), so FIFO releases it first; front advances to slot 1 exposing 2.
dequeue: arr[1]=2, front=2, count=1. Returns 2. Why this step? After releasing 1, slot 1 holds the new oldest element (2); read it, then advance.
dequeue: arr[2]=3, front=(2+1)\bmod3=0, count=0. Returns 3. Now isEmpty is true. Why this step? Slot 2 holds the last remaining element; reading it and advancing front (which wraps 2→0) empties the queue, count hits 0.
dequeue: is_empty() → count==0 → true, raises IndexError. Why this step? count=0 means zero live elements; reading arr[front] would return stale garbage (the old 1). IndexError is the guard defined above — it prevents this underflow bug.

Verify: out order 1,2,3 = in order → FIFO. Final front=0, count=0 — note front circled all the way back to 0, and yet we correctly call it empty because count, not the index, is the truth. ✅

Case F — full vs empty ambiguity

Cases D and E both ended with front == rear (both equalled 0). One was full, one was empty. That is the whole point of tracking count.

Worked example Example 6 (cell F)

$N = 3$ . Snapshot X: front=0, and the array physically holds live values in all three slots. Snapshot Y: front=0, and the array holds no live values. In both, someone computed rear $= (front + count) mod N$ and got rear=0. Distinguish full from empty.

Forecast: if you only knew front and rear, could you tell them apart?

Full case: count=3, rear $= (0 + 3) mod 3 = 0$ . So rear==front==0. Why this step? Three elements starting at slot 0 wrap exactly once, so the next-free pointer lands back on front.
Empty case: count=0, rear $= (0 + 0) mod 3 = 0$ . So rear==front==0 — identical pointers! Why this step? With nothing stored, the next-free slot is front — same collision, opposite meaning.
Resolve with count: full ⟺ count==N==3; empty ⟺ count==0. The two snapshots have count 3 vs 0 — never ambiguous. Why this step? count is a separate number that pointers cannot fake; it breaks the tie the pointers created.

Read the figure: two rings sit side by side. The left ring is all orange (three filled chairs → full); the right ring is all cream (three empty chairs → empty). Yet under both rings the caption reads rear==front==0 — the identical pointer collision. Your eye can tell them apart only because the chairs are coloured, i.e. only because you can see the count. The pointers alone are indistinguishable.

Verify: the pointer-only test front==rear returns 0==0=true in both cases — provably useless here. The count test separates them cleanly. ✅

Case G — the degenerate ring, $N = 1$

Every data structure should be tested at its smallest legal size (recall $N \geq 1$ ; $N = 0$ is invalid). A one-chair ring is the extreme.

Worked example Example 7 (cell G)

$N = 1$ . Empty. Do enqueue(9), enqueue(8), dequeue(), dequeue().

Forecast: with a single slot, how many elements can coexist?

enqueue(9): rear $= (0 + 0) mod 1 = 0$ , arr[0]=9, count=1. Now count==N==1 → full. Why this step? The one and only slot is index 0; filling it immediately reaches capacity, so the queue is full after a single enqueue.
enqueue(8): is_full() true → OverflowError. Only one chair; 8 waits outside. Why this step? Capacity 1 means at most one live element ever; the guard rejects 8 exactly as it rejected 4 in Example 4.
dequeue: arr[0]=9, front=(0+1)\bmod1 = 0, count=0. Returns 9. Why front stays 0? On a 1-ring the only index is 0; $mod 1$ of any integer is 0, so front cannot move anywhere else.
dequeue: is_empty() true → IndexError. Why this step? count is now 0, so there is nothing to read; the empty-guard fires.

Verify: with $N = 1$ the queue holds either 0 or 1 items; front is permanently 0 (since $x mod 1 = 0$ for every integer $x$ ). Both boundary guards fired correctly. ✅

Case H — real-world word problem (BFS level count)

Worked example Example 8 (cell H)

A Breadth-First Search (BFS) visits a tree: root R has children P,Q; P has child S. We enqueue nodes as we discover them and dequeue to process. Order of events: enqueue R; dequeue R (discover P,Q → enqueue both); dequeue P (discover S → enqueue S); dequeue Q (no children); dequeue S. Use $N = 4$ . In what order are nodes processed?

Forecast: BFS processes level 0, then level 1, then level 2. Predict the sequence.

enqueue R: [R,_,_,_], front=0, count=1. Why this step? BFS seeds the queue with the start node so it becomes the first thing processed.
dequeue → process R. front=1, count=0. Discovering P,Q → enqueue P (rear=(1+0)%4=1), enqueue Q (rear=(1+1)%4=2). [_,P,Q,_], front=1, count=2. Why this step? Processing a node means removing it (FIFO) and appending its freshly-discovered children at the rear, so they are served after everything already waiting — that is what keeps the search breadth-first.
dequeue → process P. front=2, count=1. Discover S → enqueue S (rear=(2+1)%4=3). [_,_,Q,S], front=2, count=2. Why this step? P entered before Q, so FIFO processes P next; P's child S is enqueued behind Q, guaranteeing all of level 1 finishes before level 2 begins.
dequeue → process Q. front=3, count=1. No children. Why this step? Q was enqueued right after P, so it is the next-oldest; it has no children, so nothing new is added.
dequeue → process S. front=(3+1)%4=0, count=0. Why front wraps here? S sat at index 3, the last slot; advancing crosses the seam to 0. S is the last node and the only level-2 node, correctly processed last.

Verify: processing order R, P, Q, S. That is exactly level-order: level 0 = {R}, level 1 = {P,Q}, level 2 = {S}. FIFO is why BFS explores breadth-first: the oldest-discovered node is always processed next. ✅

Case I — exam twist: reconstruct the hidden state

Exams love to give you a physical snapshot and ask for the invisible front/count.

Worked example Example 9 (cell I)

You are told: $N = 6$ ; the queue currently holds, in FIFO order front→rear, the values [X, Y, Z]; and their physical positions in the array are indices 4, 5, 0 respectively. Find front, count, and the value of rear (next free slot). Then verify rear points at an empty slot.

Forecast: the front element X sits at index 4 — so front is...?

front = index of the oldest element = 4. Why this step? front is by definition the slot of the front (oldest) element, which is X at index 4.
count = 3 (three live elements X,Y,Z). Why this step? count is simply how many elements are stored, and we were handed three values.
Check the layout is consistent: slots should be front, front+1, front+2 mod 6 = 4, 5, 6%6=0. That matches the given 4,5,0 — including the wrap from 5 to 0. Good, the snapshot is self-consistent. Why this step? Before trusting the numbers we confirm the given positions really are count consecutive wrapping slots from front — the defining shape of a queue.
rear = (front + count) mod N = (4 + 3) mod 6 = 7 mod 6 = 1. Why this step? The next free slot is one past the last occupied index (0), and the rear formula computes it directly: $0 + 1 = 1$ .

Verify: rear $= 1$ . Occupied indices are ${4, 5, 0}$ ; index 1 is not among them, so rear correctly points at a free slot. count=3 < N=6, so the queue is neither full nor empty — consistent. ✅

Recall Feynman recap: the one rule behind every case

All nine cases obey a single sentence: the queue occupies count consecutive chairs on the ring, starting at front, and wrapping with mod N. Front chair leaves on dequeue; the chair just past the last occupied one receives on enqueue. If count hits N you are full (enqueue throws OverflowError); if it hits 0 you are empty (dequeue throws IndexError). Memorise the ring picture, not the cases.

Active Recall

In Example 2 (

N = 4

, front=2, count=2), what index does enqueue(C) write to?

rear=(2+2)%4=0, so arr[0]=C.

In Example 4, at what count does enqueue start rejecting, and which exception does it throw?

At countN3; it throws OverflowError (queue full).

Which exception does dequeue throw on an empty queue, and why?

IndexError — count==0 means the front slot has no valid element to read.

Why can't front==rear distinguish full from empty (Example 6)?

Because with count=0 and count=N both give rear=(front+count)%N=front; identical pointers, different meanings.

What is the smallest legal capacity, and what breaks at

N = 0

N \geq 1

; at

N = 0

there are no slots and

mod 0

is undefined (division by zero), so the queue is invalid.

On a ring with

N = 1

(Example 7), what is front always equal to?

0, since

x mod 1 = 0

for every integer

x

In the BFS run (Example 8), what processing order does FIFO produce?

R, P, Q, S — exact level order (breadth-first).

Given front=4, count=3, N=6 (Example 9), what is rear?

(4+3)%6 = 7%6 = 1.