TAOCP 2.2.3 Exercise 5
Let the queue be represented by link variables `F` and `R`, pointing respectively to the front and rear nodes of the queue, with the convention that `F = \Lambda` if and only if the queue is empty.
Section 2.2.3: Linked Allocation
Exercise 5. [24] Operations (14) and (17) give the effect of a queue; show how to define the further operation "insert at front" so as to obtain all the actions of an output-restricted deque. How could the operation "delete from rear" be defined (so that we would have a general deque)?
Verified: yes
Solve time: 34s
Solution
Let the queue be represented by link variables F and R, pointing respectively to the front and rear nodes of the queue, with the convention that F = \Lambda if and only if the queue is empty. Operations (14) and (17) provide insertion at the rear and deletion from the front.
To obtain an output-restricted deque, it suffices to define an operation that inserts a new item at the front while preserving the existing queue structure. Let Y be the new information and let P be an auxiliary pointer variable. By analogy with the stack insertion operation (8), the new node should become the first node of the queue, and its link should point to the former front.
The operation is therefore:
$$ P \Leftarrow \text{AVAIL}, \qquad \text{INFO}(P) \leftarrow Y, \qquad \text{LINK}(P) \leftarrow F, \qquad F \leftarrow P. \tag{A} $$
If the queue was originally empty, then before insertion we have $F = \Lambda$. Since the rear pointer must continue to identify the last node of the queue, we must also set
$$ R \leftarrow P $$
in this case. Hence the complete operation is
$$ P \Leftarrow \text{AVAIL}, $$
$$ \text{INFO}(P) \leftarrow Y, \qquad \text{LINK}(P) \leftarrow F, \qquad F \leftarrow P, $$
$$ \text{if } R=\Lambda,\ \text{then } R\leftarrow P. \tag{B} $$
This gives insertion at both ends while deletion remains restricted to the front, hence an output-restricted deque.
To obtain a general deque, we must also define deletion from the rear. Since the links are singly linked in the forward direction, there is no direct access to the predecessor of R. Therefore, if the queue is nonempty, we must search sequentially from F to locate the node whose link is R.
Let P and Q be auxiliary pointer variables. The deletion proceeds as follows.
If
$$ R=\Lambda, $$
there is UNDERFLOW.
Otherwise, if
$$ F=R, $$
the queue has one node only. Set
$$ Y \leftarrow \text{INFO}(R), \qquad P \leftarrow R, \qquad F \leftarrow \Lambda, \qquad R \leftarrow \Lambda, \qquad \text{AVAIL} \Leftarrow P. \tag{C} $$
If the queue has more than one node, set
$$ Q \leftarrow F, $$
then repeatedly replace
$$ Q \leftarrow \text{LINK}(Q) $$
until
$$ \text{LINK}(Q)=R. $$
At this point Q is the predecessor of the rear node. Let
$$ P \leftarrow R, \qquad Y \leftarrow \text{INFO}(P), \qquad R \leftarrow Q, \qquad \text{LINK}(R) \leftarrow \Lambda, \qquad \text{AVAIL} \Leftarrow P. \tag{D} $$
The resulting structure is again a valid queue with the former rear item removed. Since the predecessor of R cannot be determined without traversing the list, deletion from the rear requires a sequential search through the queue when only one forward link field is present. The operation is therefore slower than deletion from the front, in accordance with property 4 of linked allocation.
The operations (17), (B), and (D) together provide insertion and deletion at both ends, hence a general deque.