Representing Queues (pp.261-265)

SICP Scheme

キューを作ります。Θ(1)にするためにデータをためるリスト本体と、その前端(front-ptr)と後端(rear-ptr)を保持するpairがデータ構造になります。
が、しかしここでの実装は 空っぽの場合、というのを front-ptr が nilを指してる場合、としています。空の状態では実際のデータを溜めるリスト本体は無しで、insert時に空かどうかチェックして動作を変えてます。以下コード抜粋。

(define (insert-queue-sicp! queue item)
  (let ((new-pair (cons item '())))
    (cond ((empty-queue-sicp? 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))))

どうも趣味じゃない。(eq? front-ptr rear-ptr) だったら空、にしておけばinsertは以下にできる筈です。

(define (insert-queue! queue value)
  (let ((item (cons value '())))
    (set-cdr! (cdr queue) item)
    (set-cdr! queue item))
  queue)

というわけでそうやって書き換え。

(define (make-queue)
  (let ((queue-list (list 'dummy)))
    (cons queue-list queue-list)))

(define (empty-queue? queue)
  (eq? (front-ptr queue) (rear-ptr queue)))

(define (delete-queue! queue )
  (if (empty-queue? queue)
      (error "queue is empty!")
      (set-car! queue (cdar queue))))

(define (front-queue queue)
  (if (empty-queue? queue)
      (error "queue is empty!")
      (car (cdar queue))))

(define (pop-queue! queue)
  (let ((item (front-queue queue)))
    (delete-queue! queue)
    item))

常に１要素ゴミができてしまうのが問題なのですが、たいしたコストではないだろうと勝手に思いこむことにします。

あとで追記予定・・・