;;;
    ;;; queues with mutation
    ;;;
    ;;; ADU SICP October 2000.
    ;;; 
    ;;; This differs from the implementation in the SICP text as the
    ;;; interface is simplified to four external operations (although
    ;;; there is no enforcement of that):
    ;;;
    ;;; 1. make-queue   -- returns an empty queue.
    ;;; 2. empty-queue? -- a predicate on the fullness of queues.
    ;;; 3. enqueue      -- add an elt to the tail of the queue.
    ;;; 4. dequeue      -- remove an elt from the head of the queue
    ;;;                    and return it.
    ;;;
    ;;; John Pezaris.
    
    
    ;;; The constructor.
    ;;;
    
    (define (make-queue) (cons '() '()))
    
    ;;; A couple of helper functions that are here
    ;;; more to remind us of the representation than
    ;;; to be really used.
    
    (define (front-of q) (car q))
    (define (tail-of  q) (cdr q))
    
    
    ;;; A predicate to test the state of a Q.
    ;;;
    
    (define (empty-queue? q)
      (null? (front-of q)))
    
    
    ;;; enqueue
    ;;;
    ;;; A means to add things to the Q (will go on the tail of the Q).
    ;;; Notice that an empty Q needs special handling.  Returns the
    ;;; modified Q.
    
    (define (enqueue q elt)
      (let ((new-entry (cons elt '())))
        (cond ((empty-queue? q)
               (set-car! q new-entry)	; set head pointer to single entry
               (set-cdr! q new-entry)	; set tail pointer to same
               q)
              (else
               (set-cdr! (cdr q) new-entry)	; (1) set head pointer
               (set-cdr! q       new-entry)	; (2) set tail pointer
               q))))
    
    
    ;;; dequeue
    ;;;
    ;;; A means to pull an item off the front of the Q.  Modifies the Q, 
    ;;; and returns the newly-dequeued element.
    
    (define (dequeue q)
      (cond ((empty-queue? q)
             (error "Q is empty"))
            (else
             (let ((elt (caar q)))	; (1) save the elt at front of q
               (set-car! q (cdar q))	; (2) mutate front-of q to point to next
               elt))))			; return removed elt
    

    ;;;
    ;;; end.