TAOCP 2.4 Exercise 15
Replace the explicit stack by a linked stack whose links occupy the unused `SIB` fields of the nodes that are on the stack.
Section 2.4: Multilinked Structures
Exercise 15. [**] [25] (David S. Wise.) Reformulate Algorithm A so that no extra storage
is used for the stack. [Hint: The SIB fields of all nodes pointed to by the
stack are \Lambda in the present formulation.]
Verified: no
Solve time: 1m06s
Replace the explicit stack by a linked stack whose links occupy the unused SIB fields of the nodes that are on the stack. Whenever Algorithm A would push a node pointer P onto the stack, set
$SIB(P)\leftarrow \text{TOP},\qquad \text{TOP}\leftarrow P.$
Whenever Algorithm A would pop, perform
$P\leftarrow \text{TOP},\qquad \text{TOP}\leftarrow SIB(P).$
This is correct because every node that can appear on the stack has SIB(P)=\Lambda in the original formulation; hence the SIB field contains no information that must be preserved. The stack is therefore represented as a chain through the SIB fields themselves, with TOP as its only external pointer. Algorithm A is otherwise unchanged, and no storage beyond the single pointer TOP is required.