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

空のスタックに対する一連の操作の結果【午前2 解説】

要点まとめ

• 結論：与えられた一連の操作後にスタックに残るのは、最初にpushした1と続いて残った3の二つ、すなわち選択肢アです。操作を順に追えば確実です。
• 根拠：スタックはLIFO（後入れ先出し）であり、各popは直前にpushされた要素を取り出すため、この順序で2・4・5が取り除かれます。
• 差がつくポイント：操作を紙に書いて「トップ」を常に示しながら追うか、コインなどでpush/popを模擬して可視化すると早く正確に解けます。

正解の理由

• push 1 → [1]
• push 2 → [1, 2]
• pop → [1] （2 が取り出される）
• push 3 → [1, 3]
• push 4 → [1, 3, 4]
• pop → [1, 3] （4 が取り出される）
• push 5 → [1, 3, 5]
• pop → [1, 3] （5 が取り出される）
  最終的に残るのは1と3であり、選択肢アが正解です。

よくある誤解

• 「popは最初に入れた要素を取り出す（FIFO）」と勘違いしてキューと混同することがよくあります。
• 操作をまとめて考えて「どれだけpushされたか」だけで判断し、順序を追わないミスも多いです。

解法ステップ

1. 問題文の操作を左から順に読む。
2. スタックの性質がLIFO（後入れ先出し）であることを確認する。
3. 各操作ごとにスタックの中身を更新してメモする（トップがどれかを意識）。
4. 最後の操作まで追って残った要素を答える。

選択肢別の誤答解説

• ア: 正解。上の追跡で最終的に残るのは1と3であり一致します。
• イ: 2と4は、それぞれ最初と中盤のpopで取り出されるため選べません。
• ウ: 2は最初のpopで既に取り出され、5も最後のpopで取り除かれるため誤りです。
• エ: 4は中盤のpopで取り出され、5もその後のpopで取り除かれるため残りません。

補足コラム

• スタックはデータ構造の基本で、関数呼び出しの戻り先管理や逆ポーランド記法の評価、括弧の整合性チェックなど多くの場面で使われます。
• push/popの操作はいずれも平均してO(1)で実行できます（配列やリンクドリストで実装した場合）。
• 問題を解く際は、実体的にコインや付箋で「積む/取り出す」を試すと直感的に理解できます。

FAQ