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

Before we start, one picture to keep in your head the whole way down: the array is a ring of fixed size. Throughout this page, $N$ = the array's capacity (the total number of slots — the ring has exactly $N$ chairs, numbered $0$ to $N - 1$ ). Only two numbers ever move: front (the index where the oldest element sits) and count (how many elements are seated). The rear (next free slot) is derived, never stored.

Figure — Queue — FIFO semantics, enqueue - dequeue, circular array implementation

What this figure shows (read before continuing): six array slots (indices 0–5, so $N = 6$ ) bent into a ring so the last slot touches the first. Three elements A, B, C occupy indices 2, 3, 4 (blue). The yellow arrow marks front (index 2 — the oldest element, A, leaves next). The green arrow marks rear, the next free slot, which sits just past the last occupied slot. The red centre label is count = 3, the number of seated elements. Notice rear is not stored anywhere on the ring — it is computed from front and count, which is exactly the formula we derive next.

Deriving `rear` from a picture (do not memorize it — see it)

Intuition Why rear must equal (front + count) mod N

Recall $N$ is the capacity — the number of slots on the ring, indexed $0$ through $N - 1$ . Look at the ring figure. The queue occupies a run of consecutive slots starting at front. Walk that run:

Slot 0 of the run is front itself (the oldest element).
Slot 1 of the run is front + 1.
…
The last occupied slot is front + (count − 1), because there are count elements and we count from 0.

The next free slot — where a new element goes — is one step past the last occupied one: $last occupied + 1 = (front + (count - 1)) + 1 = front + count .$ That is the raw index. But the ring only has slots $0$ to $N - 1$ ; if front + count runs off the end, we must wrap it back. Wrapping = taking the remainder after dividing by $N$ , written $mod N$ . Hence: $rear = (front + count) mod N$ In the figure: $front = 2$ , $count = 3$ , so $rear = (2 + 3) mod 6 = 5$ — exactly the slot the green arrow points to. The formula is not a rule to trust; it is just "one step past the last element, wrapped."

The single formula everything below leans on:

Level 1 — Recognition

Exercise 1.1 (L1)

A structure removes the element that has been waiting the longest. New elements join at the back. Is this a stack or a queue? What is the acronym for its discipline?

Recall Solution 1.1

Removing the oldest is FIFO — First In, First Out. This is a queue. (A stack would remove the newest — LIFO.)

Exercise 1.2 (L1)

For a circular queue with capacity $N = 6$ , front = 4, count = 0. Is the queue empty, full, or neither?

Recall Solution 1.2

The test is count, not the value of front. Since $count = 0$ , the queue is empty — regardless of where front happens to point. (This is exactly why we store count: front alone tells you nothing about occupancy.)

Exercise 1.3 (L1)

Name the single arithmetic operation that lets an index "fall off the end" of the array and reappear at index 0.

Recall Solution 1.3

The modulo (remainder) operation: $next (i) = (i + 1) mod N$ . When $i + 1 = N$ , the remainder is $0$ , wrapping back to the start.

Level 2 — Application

Exercise 2.1 (L2)

Capacity $N = 5$ , front = 3, count = 4. Compute the rear (next free slot index).

Recall Solution 2.1

$rear = (front + count) mod N = (3 + 4) mod 5 = 7 mod 5 = 2.$ The queue occupies indices $3, 4, 0, 1$ (four wrapping slots starting at front), so the next free slot is index 2. ✅

Exercise 2.2 (L2)

Capacity $N = 4$ . Start empty (front = 0, count = 0). Perform, in order: enqueue(P), enqueue(Q), dequeue(), enqueue(R), enqueue(S). Give the final front, count, and the array contents.

Recall Solution 2.2

Track it step by step. rear is always $(front + count) mod 4$ . (In the table below, $mod$ is written out consistently as the mathematical remainder — the same operation your code writes as %.)

step	rear used	front	count	array
enq P	$(0 + 0) mod 4 = 0$	0	1	[P,,,_]
enq Q	$(0 + 1) mod 4 = 1$	0	2	[P,Q,,]
deq	— (read idx 0)	1	1	[,Q,,_], returned P
enq R	$(1 + 1) mod 4 = 2$	1	2	[,Q,R,]
enq S	$(1 + 2) mod 4 = 3$	1	3	[_,Q,R,S]

Note on the array cells: after dequeue() we advance front but do not erase the old slot (its stale value is simply out of the live range). So physically index 0 still holds P — it is just no longer part of the logical queue. The logical contents are the live slots 1, 2, 3. Final: front = 1, count = 3, logical front→rear order is Q, R, S — FIFO preserved (P left first). ✅

Exercise 2.3 (L2)

Capacity $N = 3$ , front = 2, count = 2 (holds elements at indices 2 and 0). You call enqueue(Z). Which physical index does Z land in, and what are the new front / count?

Recall Solution 2.3

$rear = (2 + 2) mod 3 = 4 mod 3 = 1$ . So Z goes to index 1. After enqueue, front is unchanged (2), count becomes 3. The queue is now full ( $count = N = 3$ ). ✅

Level 3 — Analysis

Exercise 3.1 (L3)

A student uses only two indices, front and rear, and no count. With $N = 4$ they enqueue 4 elements into an empty queue. They then test emptiness with front == rear. What does the test report, and why is that catastrophic?

Recall Solution 3.1

Empty start: front = rear = 0. Each enqueue writes at rear then sets rear = (rear+1) \bmod 4. After 4 enqueues: rear = (0+4) \bmod 4 = 0. So now front = rear = 0 again — identical to the empty state.

The test reports "empty" on a completely full queue. Catastrophic: a dequeue guarded by "if not empty" would refuse to run, or worse, a naive loop treats a full buffer as done and drops all 4 elements. This is precisely the ambiguity count was invented to kill. ✅

Exercise 3.2 (L3)

The "sacrifice one slot" scheme fixes the ambiguity without a count: it declares isFull ⟺ (rear + 1) % N == front, keeping one slot permanently empty. With $N = 5$ , how many elements can this queue actually hold? Compare against the count-based design.

Recall Solution 3.2

With one slot always reserved as a gap, usable capacity is $N - 1 = 5 - 1 = 4$ elements. Why: full triggers when advancing rear would collide with front, i.e. when 4 slots are used and one gap remains. The count-based design has no gap and holds all 5. Trade-off: the slot-sacrifice avoids storing a counter (saves one integer, avoids count bookkeeping) but wastes one array cell. The count design uses full capacity at the cost of maintaining the counter. ✅

Exercise 3.3 (L3)

Explain in one sentence why each of enqueue and dequeue is $O (1)$ in the circular array, contrasting with the "shift-left on dequeue" fix.

Recall Solution 3.3

Circular enqueue/dequeue only compute an index and move one counter — a fixed amount of work regardless of how many elements are stored, hence $O (1)$ . The shift-left fix physically moves every remaining element one slot left on each dequeue, which is $O (n)$ work proportional to queue size. The ring avoids all movement by moving indices instead of data. ✅

Level 4 — Synthesis

Exercise 4.1 (L4)

Design (in pseudocode) a dequeue() that returns the element and shrinks the array to half capacity when the queue becomes at most $\frac{1}{4}$ full, to save memory. State the resulting amortized cost per dequeue and why it isn't $O (n)$ every time.

Recall Solution 4.1

def dequeue(self):
    if self.count == 0: raise IndexError("empty")
    x = self.arr[self.front]
    self.front = (self.front + 1) % self.N
    self.count -= 1
    # shrink only when very sparse, and never below some floor
    if self.N > 4 and self.count <= self.N // 4:
        self._resize(self.N // 2)   # copy count elements in FIFO order
    return x

_resize(m) allocates a new array of size m, copies the count live elements starting at logical front into slots 0..count-1, then sets front = 0. That copy is $O (count)$ .

Amortized cost: a resize costs $O (n)$ , but after halving you must dequeue roughly $n /4$ more elements before you can shrink again — so the expensive copy is "paid off" over $Θ (n)$ cheap operations. Averaged out, each dequeue is $O (1)$ amortized. The $\frac{1}{4}$ threshold (not $\frac{1}{2}$ ) creates a hysteresis gap that prevents shrink/grow thrashing at the boundary. This is the classic argument of Amortized Analysis. ✅

Exercise 4.2 (L4)

Breadth-First Search (BFS) uses a queue. On the small graph below (edges: 1–2, 1–3, 2–4, 3–4), run BFS from node 1, enqueueing neighbours in ascending order. List the visit order and show the queue's contents right after node 1 is dequeued.

What this figure shows: four nodes (1 at top, 2 and 3 in the middle layer, 4 at the bottom) with edges 1–2, 1–3, 2–4, 3–4. Colours encode BFS visit order — node 1 (red) is visited first, nodes 2 and 3 (yellow, the distance-1 layer) next, node 4 (green, the distance-2 layer) last. The picture is the point of the exercise: FIFO forces the whole yellow layer to finish before the green one begins.

Recall Solution 4.2

BFS: enqueue start, then repeatedly dequeue a node, mark visited, enqueue its unvisited neighbours.

Start: enqueue 1 → queue [1].
Dequeue 1, visit it. Neighbours 2, 3 (ascending) → enqueue both. Queue right after dequeuing 1: [2, 3].
Dequeue 2, visit. Neighbour 4 unvisited → enqueue. Queue [3, 4].
Dequeue 3, visit. Neighbour 4 already queued/visited → skip. Queue [4].
Dequeue 4, visit. No new nodes. Queue [].

Visit order: 1, 2, 3, 4. FIFO is what guarantees we finish all distance-1 nodes (2, 3) before any distance-2 node (4) — that layer-by-layer sweep is the whole point of using a queue instead of a stack. ✅

Level 5 — Mastery

Backward wrapping: the sign edge case (read before the exercises)

Every operation so far moved an index forward (add 1, wrap with $mod N$ ). Some operations — most importantly push_front on a deque — must move an index backward (subtract 1). Backward moves hide a trap that forward moves never do, so we derive the safe rule from scratch here.

Intuition Why "one before index 0" is the last slot, and why the sign matters

On the ring, stepping back from slot 0 should land on the last slot, index $N - 1$ — because the ring has no true "beginning," slot 0's left neighbour is the slot glued to it. But arithmetic gives $0 - 1 = - 1$ , which is not a valid array index. We need $mod N$ to map $- 1$ back into the legal range $0 \dots N - 1$ .

The subtlety: what does $- 1 mod N$ equal? In mathematics the remainder is chosen non-negative, so $- 1 mod N = N - 1,$ exactly the last slot — perfect. Concretely, add $N$ until you are in range: $- 1 + N = N - 1$ . Let us verify with $N = 5$ : $- 1 + 5 = 4 = N - 1$ . ✅

But many languages disagree. In C, C++, Java, JavaScript, the % operator keeps the sign of the dividend, so -1 % 5 returns $- 1$ , not $4$ . Indexing arr[-1] there is out of bounds (or in Python silently grabs the last element by a different mechanism — a coincidence, not a fix). To be portable and correct, force the result non-negative: $prev (i) = ((i - 1) mod N + N) mod N .$ The inner $mod N$ shrinks large values; the $+ N$ lifts any negative back up; the outer $mod N$ trims the possible extra $N$ . This one expression is safe for every input, including $i = 0$ .

Exercise 5.1 (L5)

You are given a CircularQueue but you have lost the stored rear; you only kept the array snapshot, $N$ , front, and count. Prove that the entire logical sequence (front → rear order) is fully recoverable, and write the index of the $k$ -th element ( $k = 0$ is the front) as a formula. Then apply it: $N = 6$ , front = 4, count = 5, list the physical indices in front-to-rear order.

Recall Solution 5.1

Claim: the $k$ -th element from the front sits at physical index $idx (k) = (front + k) mod N, k = 0, 1, \dots, count - 1.$ Proof: the queue occupies exactly count consecutive slots on the ring, beginning at front, in FIFO order. "Consecutive on a ring" means each next slot is the previous $+ 1$ taken $mod N$ . Starting at front and stepping $k$ times gives $(front + k) mod N$ . Since $k$ ranges over $0.. count - 1$ we generate exactly the occupied slots, in order — no gaps, no repeats (because $count \leq N$ guarantees the $k$ values don't wrap onto each other). Hence the whole sequence is recovered from front and count alone; rear was always redundant. ∎

Apply $N = 6, front = 4, count = 5$ : $idx (0..4) = (4 + k) mod 6 for k = 0, 1, 2, 3, 4 = 4, 5, 0, 1, 2.$ Front-to-rear physical indices: 4, 5, 0, 1, 2. (The one free slot is index 3, which equals the derived $rear = (4 + 5) mod 6 = 9 mod 6 = 3$ — consistent.) ✅

Exercise 5.2 (L5)

A deque adds push_front(x) (insert at the front). Derive the physical index this must write to, in terms of front and $N$ , and explain why a subtraction here still needs the modulo. Apply: $N = 5$ , front = 0, count = 2, do push_front(Q).

Recall Solution 5.2

To insert before the current front, the new front index is one step backward on the ring: $new_front = ((front - 1) mod N + N) mod N .$ We write $Q$ at new_front, set front = new_front, and count += 1.

Why modulo is still needed: stepping backward from index 0 gives $- 1$ , which is not a valid slot. On the ring, "one before slot 0" is the last slot, $N - 1$ . The modulo maps $- 1 \mapsto N - 1$ (using the non-negative-remainder convention derived in the edge-case box above), and the $+ N$ /outer- $mod$ form makes this safe even in languages whose % returns negatives.

Apply $N = 5, front = 0$ : $new_front = ((0 - 1) mod 5 + 5) mod 5 = 4$ . So $Q$ lands at index 4, front becomes 4, count becomes 3. This connects directly to the Circular Buffer / Ring Buffer and the general two-ended ring. ✅

Exercise 5.3 (L5)

Contrast a plain FIFO queue with a Priority Queue on this task: "process 3 arrives, then process 1 (higher priority = lower number), then process 2." A FIFO queue and a priority queue each dequeue three times. Give both output orders and state which structure the circular array natively implements.

Recall Solution 5.3

FIFO queue: dequeues in arrival order → 3, 1, 2. The circular array implements exactly this — position on the ring encodes arrival time, nothing else.
Priority queue: dequeues by priority (smallest number first) → 1, 2, 3. This needs an ordering structure (typically a heap), not arrival order.

The circular array natively implements the FIFO queue, not the priority queue: its dequeue is hard-wired to the oldest arrival at arr[front], with no notion of priority. To get priority you replace the ring with a heap. ✅

Recall One-screen recap of every formula used

Rear (next free) ::: $(front + count) mod N$ $k$ -th element's index ::: $(front + k) mod N$ After dequeue ::: $front \leftarrow (front + 1) mod N, count \leftarrow count - 1$ Push-front (deque), safe backward wrap ::: $front \leftarrow ((front - 1) mod N + N) mod N$ Empty / Full ::: $count = 0$ / $count = N$ Usable slots with one-slot-sacrifice ::: $N - 1$

Related: Parent topic · Modular Arithmetic · Amortized Analysis · Breadth-First Search (BFS) · Deque — Double-Ended Queue · Circular Buffer / Ring Buffer · Priority Queue · Stack — LIFO