23.4 まとめ

キュー

キューは、最後に入ったデータが最後に処理されるという意味でLILO(Last In Last Out)の データ構造を扱うものである。様々な形で実装できるが、要素数の変化に対応できる点から リストを用いてしばしば実現される。

スタック

スタックは、最初に入ったデータが最後に処理されるという意味でFILO(First In Last Out)の データ構造を扱うものである。スタックの実現もキューと同じような意味からリストで 実現される事が多い。

FI,FO,LI,LO

ここまでに出て来た用語の FI(First In), FO(First Out), LI(Last In),LO(Last Out)を用いると、４種類あるので あるから、４通りのデータ構造があると言えるが、実は LILO と FIFO は同じものである (最初に入ったものが最初に処理されるのと、最後に入ったものが最後に処理されるのは 同じ)。同様に、FILO と LIFO は同じであるので、結局２種類しかない点には注意しよう。

デク

キューの性質と、スタックの性質を合わせ持ったものは、デク(DEQ: Double Ended Que) とも呼ばれる。緊急データはスタック的に処理し、それ以外の通常の順番での処理には キューとして使うような場合に用いられる。従って、リストで実現すればほとんど キューと同じである(処理の容易さから、双方向リンクトリストで実現する場合が多い)。

最初のページ 戻る 次へ 最後のページ 目次