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

スタックの操作順序を問う問題【午前2 解説】

要点まとめ

• 結論：正しい操作順は イ（f,f,g,f,g,f,g,g）で、出力順 b, c, d, a が得られます。
• 根拠：f は S1 からトップを取り S2 のトップに積む操作で、g は S2 のトップを出力する LIFO 特性を利用します。
• 差がつくポイント：S2 に積んだ直後に g を入れることで要素の相対順序を調整し、不要な反転を避けます。

正解の理由

よくある誤解

• 「上の要素が a でなく d がトップだ」と誤認すると操作順序の判断を誤り、出力順が狂います。図の上端がトップと解釈する点を確認してください。
• 「f をまとめて多く実行すれば良い」と考えると S2 に余計な反転が生じ、出力順を崩します。必要な時に g を挟むのが肝心です。
• g が S1 から出力すると誤解するケース：g は常に S2 からしか出力しない点を忘れないでください。

解法ステップ

1. 状態確認：S1 = [a(top), b, c, d], S2 = [] とする（上がトップ）。
2. 目標は出力列 b, c, d, a。まず b を S2 のトップにする必要がある。
3. 操作列 f,f,g,f,g,f,g,g を順に適用して検証する（下に詳細に示す）。

• 初期：S1 = [a, b, c, d], S2 = [], 出力 = []

1. f → a を移動：S1=[b,c,d], S2=[a], 出力=[]
2. f → b を移動：S1=[c,d], S2=[b,a], 出力=[]
3. g → S2 から b を出力：S1=[c,d], S2=[a], 出力=[b]
4. f → c を移動：S1=[d], S2=[c,a], 出力=[b]
5. g → c を出力：S1=[d], S2=[a], 出力=[b,c]
6. f → d を移動：S1=[], S2=[d,a], 出力=[b,c]
7. g → d を出力：S1=[], S2=[a], 出力=[b,c,d]
8. g → a を出力：S1=[], S2=[], 出力=[b,c,d,a]

選択肢別の誤答解説

• ア: f,f,g,f,f,g,g,g
  2 回目以降に f を続けて S2 に多く積むため、出力は b, d, ... のように順序が崩れます（4〜6 手目で期待順と異なる）。
• イ: f,f,g,f,g,f,g,g
  正解。上節の通り、各ステップで S2 のトップが期待する出力になるよう g を挿入しています。
• ウ: f,f,g,f,g,g,f,g
  5〜6 手目で g を連続して a を早く出力してしまい、3 番目に a が出るため順序が b,c,a,… になって誤りです。
• エ: f,f,g,g,f,f,g,g
  3〜4 手目で g を連続して a を早く出力してしまい、b の次に a が出るので誤りです。

補足コラム

• この問題は「スタック（LIFO）」の基本理解と、複数スタックを使った順序制御の練習問題です。S1→S2 の単純な転送は順序を反転させ、途中で出力（g）を挟むことで部分的に反転を解除できます。
• 一般に「二つのスタックを直列に使う」操作は、順序の全体的な変換（スタックパーミュテーション）を生み、出力可能な順列は制約を受けます。試験対策では図示されたトップ・ボトムの確認をまず行ってください。

FAQ