なんか相対論のは教科書みたいに上から目線をあとあと読んで感じたので、このページはそういうことがないように行こうかなと。
今回、キューのいろいろと書いたけれど、結局のところガウディ本の3.4節に載ってるキューの特徴を確認していこうというだけの話。
・償却的一定時間単用的キュー
特徴はとりあえず、「リストの先頭に要素を突っ込むのは得意だから、それをうまく使っちゃおう」というもの。先頭と尾部に分けて、尾部を逆転しておく。こうすることで(逆転した)尾部の先頭に挿入したい要素を入れるだけでエンキューが可能となる。時間的な無駄を減らすため、先頭がnilになったときだけ逆転した尾部を逆転し(つまり元の並びに戻し)、先頭にする。
・最悪時一定時間単用的キュー
差分リストの尾部をデータフロー変数にすることで挿入を一定時間で行えるようにするというもの。もちろんキューに差分リストが使える場合に限る。
以上、すごく簡単にまとめてみた。簡単すぎかも・・・