[0046] キュー

平成11年度秋期 (旧)第2種情報処理技術者試験より
 FIFO(First-In First-Out)の処理に適したデータ構造はどれか。
2分木
キュー
スタック
ヒープ

正解

解説

 データ構造に関する問題です。

 FIFOとは、文字通り、First In(最初に入ってきたものが)First Out(最初に出る)ための処理方式です。身近なところでいうと、プリンタの印刷順序は、FIFOになっています。プリンタは、コンピュータ本体と比べるとかなり低速な機器ですので、一斉に利用されると直ぐに印刷待ち状態になります。プリンタは、印刷のジョブを到達順に印刷します。つまり「First In」の印刷データを、「First Out」しているわけです。

 LIFO(Last In First Out)と呼ばれるものもあります。これは、Last In(最後に入ってきたものが)First Out(最初に出る)ための処理方式です。

 FIFOやLIFOの概念は、情報処理の世界に限られたものではなく、日常のなかでもたくさんあります。例えば、簿記の勉強をされた方はご存知と思いますが、棚卸資産の評価方法として「商品は仕入れの早い順に払い出される」先入先出法(FIFO)や、後入先出法(LIFO)というのもあります。

  -----------------------

 それでは選択肢の説明をしていきましょう。まずは、スタックとキューです。

 スタック(Stack)は、いくつかのデータを保存するためのデータ構造です。スタックにデータを挿入する事を プッシュ (push) と呼び、データを取り出す事を プル (pull) と呼びます。

 キュー (Queue) もスタックと同様に、複数のデータを保存するためのデータ構造です。スタックと異なる点は、スタックが一番最後に挿入されたデータが一番最初に取り出される (LIFO) のに対して、キューは、最初に入れられたデータが最初に取り出されます(FIFO)。



 2分木は、効率の良いデータ検索を行うために、データの大きさを比較しながら保存されているツリー状のデータ構造です。

 ヒープ(heap)は、全ての親が必ず2つの子を持つ完全2分木(最後の親は片方の子だけでもよい)で、どの親と子を比べても、「親<子」になっているツリー構造のことです。2分探索木のように左右の子の大小関係は問いません。「ヒープソート」と呼ばれる並べ替えアルゴリズムで利用されます。

 ヒープという単語は、「プログラムで利用可能なメモリ領域」の意味で利用されることもあるので注意してください。

 以上より、イが正解となります。
※ 解説の内容は執筆時点のものであり,含まれている情報の正確性,妥当性について保証するものではありません。ご注意ください・・・

関連する(かもしれない)問題