問58
頻出度★☆☆
あるキューに要素 “33”, 要素 “27” 及び要素 “12” の三つがこの順序で格納されている。このキューに要素 “45” を追加した後に要素を二つ取り出す。2 番目に取り出される要素はどれか。
平成23年度 特別試験 ITパスポート試験 問58
テクノロジ系アルゴリズムとプログラミング › データ構造
この問題の解説と、これまでの解答の記録です。
解説
問 58
不正解ア
12 は先頭から数えて 3 番目にあるので、3 回目の取り出しで出る要素。2 回の取り出しでは 33, 27 までしか出ないため誤り。
- イ
正解 キュー (queue) は FIFO＝先入れ先出しのデータ構造で、追加は必ず末尾 (enqueue)、取り出しは必ず先頭 (dequeue) から行う。設問では 33, 27, 12 の順に格納されているので、先頭が 33、次が 27、その次が 12 である。ここに 45 を追加すると末尾に付いて、キューの並びは先頭から 33, 27, 12, 45 となる。この状態から 2 つ取り出すと、1 番目に出るのは先頭の 33、2 番目に出るのは次の 27 になる。よって 2 番目に取り出される要素は 27 で、イ が正解。
不正解ウ
33 は最初に格納された先頭要素なので、FIFO では 1 番目に取り出される要素。設問が問うのは 2 番目なので誤り。
不正解エ
45 は最後に追加された要素で、キューの末尾に付く。これを最初に取り出すのはスタック (LIFO＝後入れ先出し) の動作であり、キューでは 4 番目 (最後) の取り出しになるため誤り。
ここがポイント
- キューは FIFO (先入れ先出し)＝末尾に追加 (enqueue)・先頭から取り出す (dequeue)。取り出し順は格納された順と同じになる。
- 対になるスタックは LIFO (後入れ先出し) で、最後に入れたものが最初に出る。両者の取り出し順の違いを取り違えないことが本問の要点。
用語