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

スタック操作順序【午前解説】

正解の理由

解法ステップ

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が出るので誤りです。

よくある誤解

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

補足コラム

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

FAQ