問題3-21 (3.3.2 Representing Queues)

キューを表現する!!という小節．
単純にリストをキューにしちゃえばいいんだけど，それだと効率が悪いアホか!みたく書いてあって，なんでかというと要素を挿入するために，の時間がかかるからだそうです．これはキューの最後の要素へのポインタがなかなか見つからないからなんですけど，じゃぁすぐに見つけられるようにすればよくね？というお話になっている．

以下のような，キューに関する関数定義がある．

(define (make-queue) (cons '() '()))
(define (front-ptr queue) (car queue))
(define (rear-ptr queue) (cdr queue))
(define (set-front-ptr! queue item) (set-car! queue item))
(define (set-rear-ptr! queue item) (set-cdr! queue item))

(define (empty-queue? queue) (null? (front-ptr queue)))
(define (front-queue queue)
  (if (empty-queue? queue)
      (error "FRONT called with an empty queue" queue)
      (car (front-ptr queue))))

(define (insert-queue! queue item)
  (let ((new-pair (cons item '())))
    (cond ((empty-queue? queue)
	   (set-front-ptr! queue new-pair)
	   (set-rear-ptr! queue new-pair)
	   queue)
	  (else
	   (set-cdr! (rear-ptr queue) new-pair)
	   (set-rear-ptr! queue new-pair)
	   queue))))

(define (delete-queue! queue)
  (cond ((empty-queue? queue)
	 (error "DELETE! called with an empty queue" queue))
	(else
	 (set-front-ptr! queue (cdr (front-ptr queue)))
	 queue)))

でなんか，実際に実行したら，こんなクソみたいな結果がでるけどなんでなんで？という問題．

(define q1 (make-queue))
(insert-queue! q1 'a)
(print q1)             ; ((a) a)    A.
(insert-queue! q1 'b)  
(print q1)             ; ((a b) b)
(delete-queue! q1)     
(print q1)             ; ((b) b)
(delete-queue! q1)     
(print q1)             ; (() b)

どうも，インタプリタはポインタの指す先を print してくれるようです．
例えば A. の場合，'a は 1 つしか存在してはいないんだけど，q1 を構成する 2 つのポインタは両方とも a を指しているので，a が 2 つあるように出力されている．

というわけで，ちゃんとキューの内容を出力する print-queue を作る．

(define (print-queue queue)
  (print (car queue)))

(define q1 (make-queue))
(insert-queue! q1 'a)
(print-queue q1)       ; (a)
(insert-queue! q1 'b)
(print-queue q1)       ; (a b)
(delete-queue! q1)
(print-queue q1)       ; (b)
(delete-queue! q1)   
(print-queue q1)       ; ()