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