TAOCP 2.2.3 Exercise 1
Operation (8) does not mention `OVERFLOW` because it assumes that a new node can always be obtained from the `AVAIL` stack or the storage pool.
Section 2.2.3: Linked Allocation
Exercise 1. [10] Operation (9) for popping up a stack mentions the possibility of UNDERFLOW; why doesn't operation (8), pushing down a stack, mention the possibility of OVERFLOW?
Verified: no
Solve time: 39s
Operation (8) does not mention OVERFLOW because it assumes that a new node can always be obtained from the AVAIL stack or the storage pool. In the formulation of (8), the assignment
$$ P \Leftarrow \text{AVAIL} $$
implicitly relies on the availability of at least one free node. If AVAIL = \Lambda and the storage pool is exhausted, then the procedure for (8) would indeed encounter OVERFLOW, as described in equation (6) or (7). However, the basic stack push operation is written under the assumption that memory allocation succeeds, whereas the pop operation (9) must explicitly handle the case that the stack is empty, which is an intrinsic property of the stack contents rather than the availability of memory.
Thus the difference arises from the nature of the operations: popping fails only if the stack contains no elements, a state that is intrinsic to the stack itself, whereas pushing fails only if external memory is unavailable, a situation that is treated separately in the memory allocation mechanism. This completes the proof.
∎