ITパスポート 2018年 春期 問96

先入れ先出し（FIFO）処理とキュー【ITパスポート 解説】

正解の理由

解法ステップ

1. 用語の確認
   • キュー（queue）：待ち行列のように、先に入れた要素が先に出るデータ構造。
   • FIFO（First-In First-Out：先入れ先出し）：先に入れたものが先に出るルール。
   • enqueue（エンキュー、追加）：キューに値を入れる操作。
   • dequeue（デキュー、取り出し）：キューから値を取り出す操作。
2. 問題の操作を順に追う
   • enqueue 8 → キュー状態: [8] （先頭が左）
   • enqueue 1 → キュー状態: [8, 1]
   • enqueue 6 → キュー状態: [8, 1, 6]
   • enqueue 3 → キュー状態: [8, 1, 6, 3]
3. 取り出し（dequeue）を2回行う
   • 1回目の dequeue → 取り出されるのは先頭の 8。キューは [1, 6, 3] になる。
   • 2回目の dequeue → 取り出されるのは次の先頭 1。
4. 結論：2回目の取り出しで得られる値は 1（ア）。

選択肢別の誤答解説

• ア（1）
  正しい。上の通り、追加順に従って2回目に 1 が出ます。ア と明示的に一致します。
• イ（3）
  間違い。3 は最後に追加した要素なので、FIFO のキューでは一番最後に取り出されます。2回目ではまだ出ません。
• ウ（6）
  間違い。6 は3番目に追加された要素です。2回目の取り出しは2番目に追加された 1 が出るため、6 はまだ残っています。
• エ（8）
  間違い。8 は最初に追加された要素で、1回目の取り出しで既に取り出されています。したがって2回目には出ません。

よくある誤解

1. 「値の大小や並び替えで決まる」と考える
   値の大きさ（8が最大など）や数字の大小は関係ありません。キューは「入れた順番」を保持するだけです。
2. スタック（LIFO）と混同する
   スタックは LIFO（Last-In First-Out：後に入れたものが先に出る）という性質を持ちます。最後に入れた 3 を先に取り出すのがスタックの動作で、キューとは逆です。これを混同すると誤答しやすいです。
3. 取り出し回数の数え間違い（オフ・バイ・ワン）
   「最初の取り出し=0回目」と数えるなどで、何回目にどれが出るかを間違えることがあります。1回目・2回目を正しく数えましょう。

補足コラム

• 日常の例え：スーパーのレジの列を想像してください。先に並んだ人から順に会計を済ませます。これがキュー（FIFO）です。
• キューの用途例：プリンタへの印刷ジョブの管理、ネットワークのパケット処理、タスクの順序管理など。
• 実装のポイント：配列や連結リストで実装できます。配列で実装するときは「先頭」「末尾」を巡回させる環状（サーキュラー）キューにすると効率的です。

FAQ