Q about Problem 19-2 in "Lisp" by Winston and Horn

Question

Problem 19-2 in "Lisp" by Winston and Horn states,

In depth-first search, all of the partial paths in the queue at a given point in the search are related to one another in a simple way: each is the extension by one node of the partial path after it in the queue. The queue might, for example, look like this: ((D C B A) (C B A) (B A) (A))

However, I don't see how that's the case. For example, I get output like the following:

(depth-first 's 'f) 
queue: ((S)) 
(S) 
queue: ((A S) (D S)) 
(S A) 
queue: ((B A S) (D A S) (D S)) 
(S A B) 
queue: ((C B A S) (E B A S) (D A S) (D S)) 
(S A B C) 
queue: ((E B A S) (D A S) (D S)) 
(S A B E) 
queue: ((D E B A S) (F E B A S) (D A S) (D S)) 
(S A B E D) 
queue: ((F E B A S) (D A S) (D S)) 
(S A B E F) 

where I put a print statement at the beginning of the routine:

(defun depth-first (start finish &optional 
                    (queue (list (list start)))) 
  (format t "~%queue: ~a" queue) 
  (cond ((endp queue) nil) 
        ((eq finish (first (first queue))) 
         (reverse (first queue))) 
        (t (depth-first 
            start 
            finish 
            (append (extend (first queue)) 
                    (rest queue)))))) 

In this case, no partial path in the queue is the extension by one node of the partial path after it in the queue. Is this a misprint in the exercise or is there some input that does actually give the queue he gives?

Answer 1

See answer by Pascal Bourguignon.