练习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.

分析

这道题中的局部状态由指向一个常规表的开始和结束指针组成。并且要将insert-queue!和delete-queue!嵌套进整个过程中。通过dispatch来调用这些函数。

(define (make-queue)
    (let ((front-ptr '())
          (rear-ptr '()))

   (define (empty-queue?)
      (null? front-ptr))

   (define (insert-queue! item)
       (cond ((empty-queue?) (let ((init-list (list item))) (set! front-ptr init-list) (set! rear-ptr init-list) front-ptr))
             (else (let ((new-item (list item))) (set-cdr! rear-ptr new-item) (set! rear-ptr new-item) front-ptr))))
   (define (delete-queue!)
       (cond ((empty-queue?) (error "DELETE! called with an empty queue" queue))
             (else (set! front-ptr (cdr front-ptr)) front-ptr)))

   (define (dispatch m)
      (cond ((eq? m 'insert-queue!) insert-queue!)
            ((eq? m 'delete-queue!) (delete-queue!))
            ((eq? m 'empty-queue?) (empty-queue?))
            (else (error "Unknown operation -- DISPATCH" m))))
    dispatch))

测试

(define q3 (make-queue))        

;Value: q3

((q3 'insert-queue!) 'a)                

;Value 15: (a)

((q3 'insert-queue!) 'b)

;Value 16: (a b)

(q3 'delete-queue!)                  

;Value 17: (b)

(q3 'delete-queue!)

;Value: ()

(q3 'empty-queue?)                   

;Value: #t

补充

由于insert-queue！有参数，所以在dispatch中不需要添加括号，否则会报错。

感谢访问，希望对您有所帮助。 欢迎关注或收藏、评论或点赞。

为使本文得到斧正和提问，转载请注明出处：
http://blog.csdn.net/nomasp