[ 目次, 前節, 次節, 索引 ]

3.3.2 キューの表現



変更子set-car!set-cdr!を使うと, 対を使って, cons, carおよびcdrだけでは作れなかったデータ構造を構成することが出来る. 本節では,キューというデータ構造を対を使って表現する方法を示す. 3.3.3節では表というデータ構造を表現する方法を示す.

   キュー(queue)は項目を一方の端 (キューの後尾(rear)という)から挿入し, 他方の端 (先頭(front))から削除する並びである. 図3.18は最初は空のキューに, 項目abを挿入したものである. 次にaを削除, cdを挿入, bを削除する. 項目は常に挿入した順に削除するので, キューは FIFO(first in first out)バッファということがある.



図3.18 キュー演算

  データ抽象を使い, キューを次の演算で定義したと考える:

• 構成子:
(make-queue)
空のキュー(項目の一つもないキュー)を返す.

• 二つの選択子:
(empty-queue? queue)
キューが空であることをテストする.

(front-queue queue)
キューの先頭のオブジェクトを返す. キューが空ならエラーとする. キューは修正しない.

• 二つの変更子:
(insert-queue! queue⟩  ⟨item)
キューの後尾に項目を挿入し, 修正したキューを値として返す.

(delete-queue! queue)
キューの先頭の項目を削除し, 修正したキューを値として返す. 削除の前にキューが空ならエラーとする.

   キューは項目の並びだから, 当然これを通常のリストとして表現出来る; キューの先頭はリストのcarである. キューに項目を挿入するには, 新しい項目をリストの最後に挿入連結することになる. キューからの項目の削除は, 単にリストのcdrをとることだ. しかしこの表現は, 項目を挿入するのに, リストを最後まで走査しなければならず, 非効率である. リストを走査するための唯一の手段はcdr演算の繰返しだから, n項目のリストでは, 走査にΘ(n)のステップが必要である. リスト表現の単純な修正が, この欠点を克服し, キュー演算をΘ(1)ステップを必要とするように, 実装出来る; つまり必要なステップ数は, キューの長さと無関係にある.

   リスト表現の困難は, リストの最後を見つけるための走査が必要なことである. 走査が必要な理由は, リストを対の鎖で表現する標準的方法では, リストの最初へのポインタは, 容易に得られるが, 最後へアクセスするポインタは容易には得られないことだ. この不利を避ける修正は, キューをリストで表現し, 同時にリストの最後の対を指示するポインタを追加することである. 項目を挿入しようとする時は, 後尾ポインタを見ればよく, リストの走査は避けられる.

   そこでキューはそれぞれ通常のリストの最初と最後の対を指示する一対のポインタfront-ptrrear-ptrで表現する. キューを一まとまりのオブジェクトにしたいので, consを使って二つのポインタを組み合せる. つまりキュー自身は二つのポインタのconsとなる. 図3.19にこの表現を示す.



図3.19 先頭と後尾のポインタつきリストによるキューの実装

   キュー演算を次の手続きを使って定義する. これにより, キューと先頭と後尾のポインタを選択し, 修正出来る:


(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)))
make-queue構成子は, 初期の空のキューとしてcarcdrの両方が空リストの対を返す:

(define (make-queue) (cons '() '()))
キューの先頭の項目を選択するには, 先頭を示すポインタで指示した対の carを返す:

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

   キューに項目を挿入するには, その結果が図3.20に示すものになる方法をとる. まずcarが挿入すべき項目で, cdrが空リストである新しい対を作り出す. キューが初めから空なら, キューの先頭と後尾のポインタをこの対へ設定する. そうれなければ, キューの最後の対を, この新しい対を指すように修正し, また後尾ポインタを新しい対へ設定する.



図3.20 図3.19のキューに(insert-queue! q 'd)を使った結果


(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)))) 

   キューの先頭の項目を削除するには, 先頭のポインタを, 先頭の項の cdrポインタを辿ると見つかるキューの二番目の項目を指すように変更するだけである(図3.21参照):22



図3.21 図3.20のキューに(delete-queue! q)を使った結果


(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))) 

問題 3.21


Ben Bitdiddleは上に述べたキューの実装をテストしようと決めた. Lispの解釈系に手続きを入力し, 次々と試みた.
(define q1 (make-queue))

(insert-queue! q1 'a)
((a) a)

(insert-queue! q1 'b)
((a b) b)

(delete-queue! q1)
((b) b)

(delete-queue! q1)
(() b)
「全部違っている」と彼は文句をいう. 「解釈系の応答を見ると, 最後の項目がキューに二度挿入されている. 二つの項目を削除しても, 二番目のb は残っていて, キューは空の筈なのに空でない.」 Eva Lu AtorはBenは事情が分っていないという. 「項目がキューに二回入っているのではないわ.」彼女は説明する. 「標準のLispの印字プログラムは, キューの表現をどうすればよいか知らないだけなの. キューを正しく印字して見たいなら,キューのための印字手続きを自分で定義しなければならない.」 Eva Luのいっていることを説明せよ. 特にBenの例がどうしてあのような印字結果を生じたか説明せよ. 入力としてキューをとり, キューの中の項目の並びを印字する手続き print-queueを定義せよ.

問題 3.22


キューを一対のポインタで表現する代りに, キューを局所状態を持つ手続きとして作ることが出来る. 局所状態は通常のリストの最初と最後へのポインタからなる. 従ってmake-queueは次の形である.
(define (make-queue)
  (let ((front-ptr ... )
        (rear-ptr ... ))
    ⟨内部手続きの定義⟩
    (define (dispatch m) ...)
    dispatch))
make-queueの定義を完成し, この表現を使ってキューを実装せよ.

問題 3.23


デキュー(deque)(「douebl-ended queue」)は, 項目が先頭と後尾のどちらででも挿入や削除が出来る並びである. デキューの演算は, 構成子 make-queue, 述語empty-queue?, 選択子front-queue rear-queue, 変更子front-insert-queue!, rear-insert-queue!, front-delete-queue!および rear-delete-queue!である. 対を使ってデキューを表現する方法を示し, 演算を実装せよ.23 すべての演算はΘ(1)ステップで達成しなければならない.



22 先頭の項目がキューの最後の項目なら, 先頭のポインタは削除の後, 空リストになり, キューは空になる; 後尾ポインタは依然として削除した項目を指してはいるが, empty-queue?は先頭のポインタだけ見ているので, 更新を気にする必要はない.

23 解釈系に循環を含む構造を印字させないよう注意せよ. (問題3.13参照)




[ 目次, 前節, 次節, 索引 ]