my attempt to do the exercises in sicp.

Friday, November 27, 2009

sicp exercise 3.22

; Exercise 3.22.  Instead of representing a queue as a pair of pointers, we can build a queue as a procedure with local state. The local state will consist of pointers to the beginning and the end of an ordinary list. Thus, the make-queue procedure will have the form
; (define (make-queue)
;   (let ((front-ptr ...)
;        (rear-ptr ...))
;           <definitions of internal procedures>
;        (define (dispatch m) ...)
;              dispatch))
; Complete the definition of make-queue and provide implementations of the queue operations using this representation.

(define (make-queue)
  (let ((front-ptr '())
        (rear-ptr  '()))
    (define (set-front-ptr! item)(set! front-ptr item))
    (define (set-rear-ptr!  item)(set! rear-ptr  item))
    (define (empty-queue?)(null? front-ptr))
    (define (front-queue)
      (if (empty-queue?)
        (error "FRONT called with empty queue")
        (car front-ptr)))
    (define (insert-queue! item)
      (let ((new-pair (cons item '())))
        (cond ((empty-queue?)
               (set-front-ptr! new-pair)
               (set-rear-ptr! new-pair))
                (set-cdr! rear-ptr new-pair)
                (set-rear-ptr! new-pair)))))
    (define (delete-queue!)
      (cond ((empty-queue?)
             (error "DELETE! called on empty queue"))
              (set-front-ptr! (cdr front-ptr)))))
    (define (print-queue)
      (display front-ptr))
    (define (dispatch m)
      (cond ((eq? m 'empty-queue? )  empty-queue?)
            ((eq? m 'insert-queue!) insert-queue!)
            ((eq? m 'delete-queue!) delete-queue!)
            ((eq? m 'front-queue  )   front-queue)
            ((eq? m 'print-queue  )   print-queue)
            (else (error "ERROR"))))

(define (empty-queue? queue) ((queue 'empty-queue?)))
(define (insert-queue! queue item) ((queue 'insert-queue!) item))
(define (delete-queue! queue) ((queue 'delete-queue!)))
(define (front-queue queue) ((queue 'front-queue)))
(define (print-queue queue) ((queue 'print-queue)))

(define q1 (make-queue))

(insert-queue! q1 'a)
(insert-queue! q1 'b)

(print-queue q1) (newline)

(delete-queue! q1)
(delete-queue! q1)

(print-queue q1) (newline)

No comments: