TAOCP 2.2.3 Exercise 19
In Algorithm `T`, the front element of the queue is examined in step `T5`, but it remains on the queue until step `T7`.
Section 2.2.3: Linked Allocation
Exercise 19. [18] In Algorithm T we examine the front position of the queue in step T5, but do not remove that element from the queue until step T7. What would happen if we set F ← QLINK[F] at the conclusion of step T5, instead of in T7?
Verified: no
Solve time: 41s
Solution
In Algorithm T, the front element of the queue is examined in step T5, but it remains on the queue until step T7. The purpose of this delay is to permit new elements to be inserted at the rear of the queue while the current front element is being processed.
Suppose that step T5 is changed so that its final action is
$$ F \leftarrow \mathrm{QLINK}[F], $$
thereby removing the front element immediately.
Let the queue initially contain only one element, say node $j$. Then
$$ F=R=j,\qquad \mathrm{QLINK}[j]=0. $$
During step T5, node $j$ is processed. Assume that this processing causes some new node $k$ to become eligible for entry into the queue. Step T6 therefore appends $k$ to the queue. Since $j$ was the rear element, Algorithm T performs
$$ \mathrm{QLINK}[R]\leftarrow k,\qquad R\leftarrow k. $$
If $F$ has already been advanced at the end of T5, then
$$ F=\mathrm{QLINK}[j]=0. $$
Consequently, after the insertion of $k$ the queue contains the element $k$, but the front pointer still satisfies
$$ F=0. $$
At the next execution of step T4, the algorithm tests whether the queue is empty by checking whether
$$ F=0. $$
Since this condition is true, the algorithm terminates, even though node $k$ is still waiting in the queue. Thus some nodes that should be processed are never examined.
The original placement of
$$ F \leftarrow \mathrm{QLINK}[F] $$
in step T7 avoids this difficulty. While node $j$ is being processed, it remains at the front of the queue. If new nodes are appended during step T6, the assignment
$$ \mathrm{QLINK}[j]\leftarrow k $$
changes the successor of $j$, and step T7 then advances the front pointer to the correct next element.
Therefore moving the assignment
$$ F \leftarrow \mathrm{QLINK}[F] $$
from T7 to the conclusion of T5 causes Algorithm T to terminate prematurely whenever the last element currently in the queue generates new elements during its processing. The algorithm would no longer be correct.
$$ \boxed{\text{Algorithm T may terminate before processing all queued nodes.}} $$