基本情報 平成21年度 春期 問5：テクノロジ系に関する問題

答えは a「1と3」 です。

スタックは「お皿の山」をイメージしてください。新しく置いた皿が一番上、取り出すときも一番上から取ります（最後に置いたものが最初に出る＝LIFO）。

操作を1つずつ追うとこうなります。

1. push 1 → 山：[1]

2. push 2 → 山：[1, 2]

3. pop → 一番上の2を取る → 山：[1]

4. push 3 → 山：[1, 3]

5. push 4 → 山：[1, 3, 4]

6. pop → 4を取る → 山：[1, 3]

7. push 5 → 山：[1, 3, 5]

8. pop → 5を取る → 山：[1, 3]

残ったのは 1と3。

👉 覚え方：スタックは「後入れ先出し」。お皿の山と覚える！

なぜこれが正解か

正解は a。スタックはLIFO（Last In First Out：後入れ先出し）のデータ構造で、push（積む）とpop（取り出す）はどちらも最上段に対して行う。

操作を順にトレース（左が底、右が上）：

• push1 → [1]
• push2 → [1,2]
• pop → [1]（2を取り出す）
• push3 → [1,3]
• push4 → [1,3,4]
• pop → [1,3]（4を取り出す）
• push5 → [1,3,5]
• pop → [1,3]（5を取り出す）

結果、残るのは 1と3。

各選択肢の解説

• b「2と4」：popされた値の組合せで誤り。
• c「2と5」：同じく取り出された値。
• d「4と5」：最後の2回のpop対象。

覚え方・ひっかけ注意

pushで右へ伸ばし、popで右端を消す、と紙に書きながら追うと確実。「残ったデータ」を聞かれているか「取り出した順」を聞かれているかを必ず最初に確認すること。

理論的背景

スタックは抽象データ型（ADT）の代表で、push/popの計算量はいずれもO(1)。実装は配列ベース（top変数を持つ）と連結リストベース（先頭挿入/先頭削除）の2方式が一般的。配列実装はキャッシュ効率が良いが容量上限あり、連結リスト実装は動的拡張可能だがポインタ分のメモリオーバーヘッドがある。

実務での使われ方

関数呼び出しのコールスタック（戻り番地・ローカル変数・引数の保存）、式の評価（逆ポーランド記法による電卓実装）、構文解析（括弧の対応チェック）、Undo機能、深さ優先探索（DFS）の経路保持など極めて広範。CPUのレジスタにもスタックポインタ（SP）が用意され、ハードウェアレベルで支援される基本構造。

試験での位置づけ

FEではほぼ毎回1問はスタック/キュー関連が出る最頻出テーマ。トレース問題（本問のタイプ）、用途を選ぶ問題、キューとの比較問題（FIFO vs LIFO）が定番。応用情報・基本情報の午後では、逆ポーランド記法の評価や再帰の呼び出し履歴を題材にした実装問題も頻出。

選択肢の発展補足

キュー（Queue）はFIFO（First In First Out）で先頭から取り出す。両端から出し入れできるのが両端キュー（deque）、優先度順に取り出すのがプライオリティキュー（実装はヒープ：O(log n)）。スタックオーバーフロー（過剰なpush・無限再帰）はセキュリティ攻撃（バッファオーバーフロー）の温床としてもFE午後・情報処理安全確保支援士で頻出。