s c h e m a t i c s : c o o k b o o k

(module queue mzscheme
  (provide empty empty? insert remove first)
  
  (define-struct queue (front back) (make-inspector))
  
  (define empty (make-queue '() '()))
  
  ; empty? : queue -> boolean
  ;  is the queue Q empty?
  (define (empty? Q)
    (and (null? (queue-front Q))
         (null? (queue-back Q))))
  
  ; insert : queue elm -> queue
  ;  return a new queue holding both the elements
  ;  from the old queue Q and the new element x
  (define (insert Q x)  
    (make-queue (queue-front Q) 
                (cons x (queue-back Q))))

  ; remove : queue -> (values queue elm)
  ;  return two values, the first a queue with the same elements
  ;  as the queue Q except for the element in front of the queue
  ;  the second a value is the front element of Q
  (define (remove Q)
    (cond
      [(and (null? (queue-front Q)) (null? (queue-back Q)))
       (error "remove: The queue is empty")]
      [(null? (queue-front Q))
       (remove (make-queue (reverse (queue-back Q)) '()))]
      [else
       (values (car (queue-front Q)) 
               (make-queue (cdr (queue-front Q)) (queue-back Q)))]))

  ; first : queue -> element
  ;  return the first element in the non-empty queue Q
  (define (first Q)
    (cond
      [(empty? Q)
       (error "first: The queue is empty")]
      [(null? (queue-front Q))
       (first (make-queue (reverse (queue-back Q)) '()))]
      [else
       (car (queue-front Q))]))
  )

> (require queue)
> (define Q empty)
> (let* ([Q (insert Q 1)]
         [Q (insert Q 2)]
         [Q (insert Q 3)])
    (let*-values ([(x Q) (remove Q)]
                  [(y Q) (remove Q)]
                  [(z Q) (remove Q)])
      (list x y z)))
(list 1 2 3)

> (print-struct #t)
> (remove (insert (insert (insert empty 
                                  1)
                          2)
                  3))
1
#(struct:queue (2 3) ())