FIFOが実現できる「条件と内部データ構造の要素」について


FIFOとは

FIFO(キュー)とは、入れたデータを順番に取り出すものである。


FIFOが実現できる条件

データはすべて同じ型をもつ。
データは時系列的に発生する。
処理の済んだデータを記憶しておく必要はない。
未処理のデータ数は常にn未満になることが分かっている。

FIFOが実現できる内部データ構造の要素

①:配列A(データと同じ型。大きさはn。)
②:変数X(0以上n未満の整数が記憶できる)
③:変数Y(0以上n未満の整数が記憶できる)
④:関数succ(i)(仮引数iに対して、i+1をnで割った余りを返す)(仮引数iは0以上n未満の値を取る)


実現方法と他の方法が不可である理由

キュー(FIFO):入れたものを順番に取り出す
・発生したデータの格納位置を変数X、取出し位置を変数Yに記録する
・キューが行われた時に関数succの返却値によって値を更新すればよい
→実装可能(関数succ(i)は要素数nの配列を循環使用するため)

スタック(LIFO):最後に入れたものを最初に取り出す
・要素を取出したときに、次の取出し位置を減算によって決める必要がある
→内部データの構造にはそのような要素はないので、実現不可

根付き木:ある要素を基準にした時に上下関係があるもの
・根に当たる要素をA[0]に記録する
・【親の要素番号をi】とした時、左右の子をそれぞれ2✕i、2✕i+1に相当する位置に記録する
→という操作ができれば可能だが、当条件にはそれに該当する関数はない。実現不可

優先度キュー:優先度に従ってデータを取り出す
・処理順番が格納順と無関係で、優先度を考慮しなくてはいけない
・優先度順に格納する場合には、データの値のほかに優先度を記録する必要がある
→実現不可