ITパスポート 2016年 秋期 問92

スタックによる出力順の判定【ITパスポート 解説】

正解の理由

解法ステップ

1. スタックの性質を確認する。
   • スタック：最後に入れた（push）ものが最初に出る（pop）構造。英語で LIFO（Last In, First Out）。
   • 問題の操作：① 直接出力（パスする）、② スタックに積む（push）、③ スタックから取り出す（pop）。
2. 出力の先頭（最初に左から出したいデータ）を見る。
   • そのデータより前に入っている要素がある場合、それらをどう扱うか考える（出すなら先に出す／残すならスタックに積む）。
3. スタックに残した要素は逆順でしか出せないことを使う。
   • 「あるとき点でスタックに乗っている複数要素の相対順序は逆転する」点が重要。
4. 各選択肢について、上のルールで矛盾が生じるかどうかを検証する。
   • 矛盾が起きれば「出力できない」。

選択肢別の誤答解説

• ア: B, A, D, C
  実現可能です。操作例：
  • A 到着：②（A を積む）
  • B 到着：①（B を直接出力） ← 出力順 1:B
  • ③（スタックから A を取り出す） ← 出力順 2:A
  • C 到着：②（C を積む）
  • D 到着：①（D を直接出力） ← 出力順 3:D
  • ③（C を取り出す） ← 出力順 4:C
• イ: B, D, C, A
  実現可能です。操作例：
  • A 到着：②（A を積む）
  • B 到着：①（B を直接出力） ← 1:B
  • C 到着：②（C を積む） // C は D の後に出したいので積む
  • D 到着：①（D を直接出力） ← 2:D
  • ③（C を取り出す） ← 3:C
  • ③（A を取り出す） ← 4:A
• ウ: C, B, D, A
  実現可能です。操作例：
  • A 到着：②（A を積む）
  • B 到着：②（B を積む） // Aの下にBが来る（Bがトップ）
  • C 到着：①（C を直接出力） ← 1:C
  • ③（B を取り出す） ← 2:B
  • D 到着：①（D を直接出力） ← 3:D
  • ③（A を取り出す） ← 4:A
• エ: C, D, A, B
  実現不可能な理由（上で述べた具体的帰結）：
  • C を最初に出すためには A, B を C が来る前にスタックに積んでおく必要がある（A, B を出してしまうと C が先に出せないため）。
  • 積んだ順は A（底）→ B（上）になるので、後で取り出すときは B が先、A が後。つまりスタックから出す順は B, A になる。
  • しかし要求されているのは A が B の前に出ること（…A, B）。スタックの性質と矛盾し、実現できません。

よくある誤解

1. 「スタックに入れておけば順序は自由に並べ替えられる」
   • 誤りです。スタックは逆順にしか取り出せません。積む順序がそのまま出す順を制限します。
2. 「直接出力（①）できるならスタックの中身は関係ない」
   • 直接出力は可能ですが、一度スタックに積んだ要素の相対順序は変えられません。直接出力で後続を先に出す判断ができても、スタックの既存要素の順序は影響を受けます。

補足コラム

• 単一のスタックで作れる出力順は「スタック順列（stack permutation）」と呼ばれます。直感的には「ある要素を後で出したいなら、それより前の要素は一旦スタックに退避させる必要がある」。でも退避した複数要素は逆順でしか戻せない、これが制約です。
• 用語メモ：
  • push（プッシュ）：データをスタックに積む操作（本問題の②）。
  • pop（ポップ）：スタックからデータを取り出す操作（本問題の③）。
  • LIFO（Last In, First Out）：最後に入れたものを最初に取り出す性質。

FAQ