基本情報技術者 2013年 秋期 午前（科目A） 問05

要点まとめ

• 結論：次に行うDEQで取り出される値は5です。操作列を順に追うと先頭に残るのが値5で、正解はウです。
• 根拠：待ち行列はFIFO（先入れ先出し）であるため、ENQ/DEQを順に適用すると取り出し順が確定し、5が次に出ることになります。
• 差がつくポイント：スタックと混同して後入れを先に取り出す誤解やDEQの回数を数え間違うミスに注意し、操作後の状態を逐一書くことが有効です。

正解の理由

よくある誤解

• DEQの回数不足や過剰を見落として、まだ残っている要素の順序を誤ること。
• スタック（LIFO）と混同して「最後に入れた6が出る」と考えてしまうこと。
• 操作をまとめて概念的に考えすぎて、各ステップでの状態変化を書き出さないために誤答すること。

解法ステップ

1. 初期状態：待ち行列 Q = []
2. ENQ 1 → Q = [1]
3. ENQ 2 → Q = [1, 2]
4. ENQ 3 → Q = [1, 2, 3]
5. DEQ → 1 を取り出す、Q = [2, 3]
6. ENQ 4 → Q = [2, 3, 4]
7. ENQ 5 → Q = [2, 3, 4, 5]
8. DEQ → 2 を取り出す、Q = [3, 4, 5]
9. ENQ 6 → Q = [3, 4, 5, 6]
10. DEQ → 3 を取り出す、Q = [4, 5, 6]
11. DEQ → 4 を取り出す、Q = [5, 6]
12. 次のDEQで先頭の5が取り出される → 答えは5（ウ）

選択肢別の誤答解説

• ア: 1 — 操作列の最初のDEQで1は取り出されますが、その後もENQ/DEQが続くため1は既に出ており、次に出る値ではありません。
• イ: 2 — 2も途中で取り出されます（2は2回目のDEQで出る）が、最後に残る先頭ではないため誤りです。
• ウ: 正解（5） — シミュレーションの通り、最後に残った先頭要素が5であり、次のDEQで取り出されます。
• エ: 6 — 6は最後に入れられた要素ですが、FIFOでは先に入った5が先に出るため、6はその次に出ます。スタックと混同すると6を選びがちです。

補足コラム

• キューの基本性質：入れる操作をENQ（enqueue）、出す操作をDEQ（dequeue）と呼び、実装は配列の頭尾を使う環状バッファや連結リストが一般的です。
• 計算量：ENQ/DEQはいずれも適切に実装すればO(1)で実行可能です。
• 実務での利用例：プリントキュー、タスクスケジューリング、幅優先探索（BFS）などでキューが使われます。

FAQ