练习 3.22

以下是新的队列实现：

;;; 22-queue.scm

(define (make-queue)
    (let ((front-ptr '())
          (rear-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 (empty-queue?)
            (null? 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 "Unknow operation -- DISPATCH" m))))
        dispatch))

实现使用了两个变量作为指针，分别指向队列的前端和后端。

测试：

1 ]=> (load "22-queue.scm")

;Loading "22-queue.scm"... done
;Value: make-queue

1 ]=> (define q (make-queue))                   ; 创建队列

;Value: q

1 ]=> ((q 'insert-queue!) 'a)                   ; 插入

;Value 11: (a)

1 ]=> ((q 'insert-queue!) 'b)

;Value 11: (a b)

1 ]=> (q 'delete-queue!)                        ; 删除

;Value 12: (b)

1 ]=> (q 'delete-queue!)

;Value: ()

1 ]=> (q 'empty-queue?)                         ; 空队列

;Value: #t

1 ]=> ((q 'insert-queue!) 'not-empty-now)

;Value 14: (not-empty-now)

1 ]=> (q 'empty-queue?)

;Value: #f

讨论

blog comments powered by Disqus