TAOCP 2.1 Exercise 3

Algorithm A inserts a card at the top of the pile.

taocpmathematicsalgorithmsvolume-1simple

Section 2.1: Introduction

Exercise 3. [11] Give an algorithm that essentially undoes the effect of Algorithm A: It removes the top card of the pile (if the pile is not empty) and sets NEWCARD to the address of this card.

Verified: no
Solve time: -

Solution

Algorithm A inserts a card at the top of the pile. If TOP contains the address of the current top card and NEWCARD contains the address of the card to be inserted, the effect is

  1. NEXT(NEWCARD) ← TOP;
  2. TOP ← NEWCARD.

To undo this operation, when the pile is nonempty, we must remove the top card, make the second card become the new top, and place the address of the removed card into NEWCARD.

The algorithm is therefore:

R1. [Pile empty?] If TOP = Λ, terminate.

R2. [Save top card.] Set NEWCARD ← TOP.

R3. [Remove top card.] Set TOP ← NEXT(TOP).

After step R2, NEWCARD contains the address of the card that is currently at the top of the pile. Step R3 changes TOP to the address of the next card in the chain. Hence the former top card is no longer in the pile, and NEWCARD contains its address.

If the pile originally consisted of a single card, then NEXT(TOP) = Λ; therefore step R3 sets TOP ← Λ, leaving the pile empty, which is correct.

Thus the algorithm removes the top card whenever the pile is nonempty and sets NEWCARD to the address of that card. The effect is exactly the inverse of Algorithm A. ∎