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

邮箱及Skype：nomasp@outlook.com
Facebook：https://www.facebook.com/yuwang.ke
CSDN博客：http://blog.csdn.net/nomasp
新浪微博：http://weibo.com/nomasp