A queue keeps both ends within reach.
A linked queue keeps a pointer to the next item to remove and another pointer to the last pair, so each operation changes only the end it owns.
Why does constant local insertion need a rear pointer as well as a front pointer?
- Represent a queue as linked mutable pairs
- Follow set-cdr! at the rear during insertion
- Follow the front pointer during deletion
- Recognize when a one-item queue shares both pointers
Insertion creates one pair. An empty queue makes both pointers name that pair. A nonempty queue changes the old rear cdr to the new pair and then advances rear, without searching from front.
Deletion does not rewrite the links. It advances front to its current cdr. After inserting a, b, and c and deleting once, front names the b pair while rear still names the c pair.
- Output
- —
- Value
- —
- Diagnostic
- —
The first program returns (b c #f). The second returns (solo solo #t).
Find the cdr mutation that links each new nonempty insertion to the old rear pair. Then distinguish it from the binding assignment that advances rear or front.
Change the program and compare the result.
Delete once more from the first program. Predict the front value, rear value, and eq? result before running it.
Show hint
After the second deletion, both pointers name the one remaining c pair.