ITパスポート 2010年 春期 問85

スタックによる順序変換【ITパスポート解説】

正解の理由

解法ステップ

1. スタックの性質を理解する
   • スタックは「積む（push）」と「取り出す（pop）」の2操作で、最後に積んだものが最初に取り出されます（LIFO。皿を積んだイメージで、上の皿から取ると考えると分かりやすいです）。
2. 入力X → Y → Zを順に処理し、出力希望順を実現できるか試行する
   • 各入力に対し「①そのまま出力」「②スタックへ積む」のどちらかを選べます。いつでもスタックの上から「③取り出して出力」できます。
   • 疑わしい順番（ここではZ, X, Y）について、全ての操作パターンを試すか、スタックの順序制約から不可能を論理的に示します。
3. Z, X, Yが不可能である論理的証明（簡潔な方法）
   • Zを先に出すには、Z到着時に ①（そのまま出力）を選ぶか、すべてを積んで後で取り出す手しかありません。
   • XとYのどちらかをスタックに入れている場合、Xは先に入力されているのでYが上に来ます。よって、Zより後にXとYを出すにはスタックから先にYが出てXが出ます（出力順はY, X）。これではXの先出（X→Y）はできません。
   • 結論：Zを先に出し、その後Xを先に、Yを後に出す（Z, X, Y）は実現できない。

選択肢別の誤答解説

• ア: X, Z, Y
  • 可能です。操作例：Xを①で出力（X）、Yを②でスタックに積む、Zを①で出力（Z）、最後にスタックを③で取り出す（Y）。出力列はX, Z, Y。
• イ: Y, Z, X
  • 可能です。操作例：Xを②で積む、Yを①で出力（Y）、Zを①で出力（Z）、最後にスタックを③で取り出す（X）。出力列はY, Z, X。
• ウ: Z, X, Y
  • 不可能です（前節の通り）。Zを先に出し、その後XをYより先に出すには、YをXの下にしておかなければなりません。しかしXは先に入るため、Yが上になり、PopするとYが先に出てしまいます。したがってZ, X, Yの順は作れません。
• エ: Z, Y, X
  • 可能です。操作例：Xを②で積む、Yを②で積む（スタック上は下からX → Y）、Zを①で出力（Z）、その後スタックを③で2回取り出してY, Xと出力。出力列はZ, Y, X。

よくある誤解

1. 「スタックに積めば自由に順序を作れる」
   • スタックは順序を反転する道具ですが、すべての並べ替えが可能なわけではありません。LIFOの制約で特定の順序は不可能です。
2. 「Zを先に出せば、残りは自由にできる」
   • Zを先にした後のXとYの順は、既に積まれているかどうかで決まり、積まれていればY→Xの順になります。状況により制約が残ります。

補足コラム

• この問題は「スタックで生成できる順列（stack permutations）」の典型です。一般に入力1..nに対して単一スタックで可能な出力順は限られ、数学的には特定のパターンを避ける（pattern-avoiding）順列になります。実務的にはコンパイラの括弧検査や、Undo（取り消し）機能の内部動作イメージに近い考え方です。
• 例え話：お皿を積むとき、最後に積んだお皿を最初に取り出すので、途中で「一つ下のお皿だけ先に取り出す」ことはできません。

FAQ