TAOCP 2.2.2 Exercise 1

Let $X[1], \ldots, X[M]$ be the memory locations for the queue, with `F` and `R` the front and rear pointers, respectively, as in (6a) and (7a).

taocpmathematicsalgorithmsvolume-1simple

Section 2.2.2: Sequential Allocation

Exercise 1. [15] In the queue operations given by (6a) and (7a), how many items can be in the queue at one time without OVERFLOW occurring?

Verified: no
Solve time: -

Solution

Let $X[1], \ldots, X[M]$ be the memory locations for the queue, with F and R the front and rear pointers, respectively, as in (6a) and (7a). The queue is initially empty when F = R = 1. An insertion increments R (modulo $M$) and stores a value at $X[R]$, but an OVERFLOW occurs if after incrementing R we have R = F. A deletion increments F (modulo $M$) and retrieves $X[F]$, with UNDERFLOW if F = R.

We seek the maximum number of items $Q_\max$ that can reside in the queue without causing OVERFLOW. Let the current number of items in the queue be $Q$. Then, after an insertion, the condition for OVERFLOW is

$$ R = F \iff Q = ? $$

We analyze the queue modulo $M$. Since the queue indices wrap around, the distance from F to R in modulo $M$ arithmetic equals the number of items:

  1. If R \ge F, then the number of items is $Q = R - F$.
  2. If R < F, then $Q = M - (F - R) = M + R - F$.

The OVERFLOW condition is R = F immediately after incrementing R. Denote the rear before insertion as $R_0$; then after increment:

$$ R = \begin{cases} R_0 + 1,& \text{if } R_0 < M,\ 1,& \text{if } R_0 = M. \end{cases} $$

If after this update $R = F$, then insertion is forbidden. Thus, the number of items just before OVERFLOW occurs is

Q_\max = M - 1.

To verify, consider an example with $M = 5$:

  • Empty queue: F = R = 1, Q = 0.
  • Insertions: R takes values $2,3,4,5. The queue contains $1,2,3,4 items, respectively.
  • Next insertion attempts to set R = 1. Now R = F = 1 triggers OVERFLOW.

Hence, at most $M - 1$ items can occupy the queue without OVERFLOW.

This completes the proof.

∎

$$ \boxed{M-1} $$