以下是新的队列实现:
;;; 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