理系学生日記

おまえはいつまで学生気分なのか

問題3-22 (3.3.2 Representing Queues)

クロージャでキューを実現する.

(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 an empty queue")
	  front-ptr))
    (define (insert-queue! item)
      (let ((new-pair (cons item '())))
	(cond ((empty-queue?)
	       (print "new-pair=" new-pair)
	       (set-front-ptr! new-pair)
	       (set-rear-ptr! new-pair)
	       dispatch)
	      (else
	       (set-cdr! rear-ptr new-pair)
	       (set-rear-ptr! new-pair)
	       dispatch))))
    (define (delete-queue!)
      (cond ((empty-queue?)
	     (error "DELETE! called with an empty queue"))
	    (else
	     (set-front-ptr! (cdr front-ptr))
	     dispatch)))
    (define (print-queue)
      (print front-ptr))
    (define (dispatch m)
      (cond ((eq? m 'insert-queue!) insert-queue!)
	    ((eq? m 'delete-queue!) delete-queue!)
	    ((eq? m 'front-queue) front-queue)
	    ((eq? m 'print-queue) print-queue)
	    ((eq? m 'empty-queue?) empty-queue?)
	    (else (error "Undefined operation: " m ))))
    dispatch))
(define q1 (make-queue))
((q1 'insert-queue!) 'a)
((q1 'print-queue))  ; (a)
((q1 'insert-queue!) 'b)
((q1 'print-queue))  ; (a b)
((q1 'delete-queue!))
((q1 'print-queue))  ; (b)
((q1 'delete-queue!))
((q1 'print-queue))  ; ()