[Jscheme-user] Norvig's queue code.

[Jonathan A R. <ja...@mu...>]

There's a nice queue implementation that I first observed in some ML
code of John Reppy's.  It has a more functional feel to it, is easier
to rewrite (I just reconstructed it from memory in about two minutes),
is easier to see as being correct (if it is), and avoids the
circularity problem.  Although 'front' is no longer constant time, the
amortized cost of using the data structure is the same as that of the
conventional approach.

(define (make-queue) (cons '() '()))

(define (enqueue item queue)
  (set-car! queue (cons item (car queue))))

(define (front queue)
  (if (null? (cdr queue))
      (begin (set-cdr! queue (reverse (car queue)))
             (set-car! queue '())))
  (car (cdr queue)))  ;error check desirable here

(define (dequeue queue)
  (let ((f (front queue)))
    (set-cdr! queue (cdr (cdr queue)))
    f))

(define (empty-queue? q)
  (and (null? (car q)) (null? (cdr q))))