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

要点まとめ

• 結論：入力順序 A,B,C,D に対して、単一のスタックのみを用いて出力可能なのは選択肢ウの C,B,D,A のみで、他はスタックの LIFO 性により実現できません。
• 根拠：スタックは後入れ先出し（LIFO）で、ある要素より後にプッシュされた要素が上にある間はその下の要素を取り出せないという入出力制約が成否を決定します。
• 差がつくポイント：出力順を左から見て必要なら入力を順にプッシュし、トップが一致したらポップする貪欲シミュレーションで可否を短時間で判定できます。

正解の理由

1. push A（スタック上: [A]）
2. push B（[A, B]）
3. push C（[A, B, C]）
4. pop → C を出力（出力列: C、スタックは [A, B]）
5. pop → B を出力（出力列: C, B、スタックは [A]）
6. push D（[A, D]）
7. pop → D を出力（出力列: C, B, D、スタックは [A]）
8. pop → A を出力（出力列: C, B, D, A、スタックは空）

よくある誤解

• 「すべての順列がスタック一つで作れる」と思い込む：実際は LIFO 制約により多数の順列が不可能で、特定の逆転（上にある要素が先に出る必要がある場合）が問題になります。
• 「一度全てプッシュしてからポップすればどの順番でもできる」との誤認：全てプッシュしてからポップすると逆順（D,C,B,A）になるだけで、任意順にはなりません。
• 「部分的に別解があるはず」と考えて操作を雑に推測すること：可否判定は貪欲にシミュレーションするか、逆転関係を論理的に検討するのが確実です。

解法ステップ

1. 目標出力列を左から順に見ます（ここでは C→B→D→A）。
2. 入力列の先頭から順に、必要な要素がスタックのトップに来るまで push を繰り返します。
3. 目標の要素がスタックのトップに来たら pop して出力に追加します。
4. 目標要素を出力できない（入力を全て使ってもトップに来ない）場合は不可能と判断します。
5. これを全要素に対して行い、最後まで成功すれば可、途中で失敗すれば不可です。

選択肢別の誤答解説

• ア: A, D, B, C
  A を最初に出すのは可能（push A → pop A）。しかし次に D を出すには B と C をスタックに積む必要があり、D を pop した後に B を先に出すことはできません（C が B の上にあるため）。よって不可。
• イ: B, D, A, C
  B を最初に出す操作は可能（push A, push B, pop B）。その後 D を出すには C と D を積むが、D を出した後に A を出すとなると C が A の上に残っており A を先に出せないため不可。
• ウ: C, B, D, A
  前節の通り、操作列（push A, push B, push C, pop C, pop B, push D, pop D, pop A）で実現可能。よって正解。
• エ: D, C, A, B
  D を最初に出すには全てプッシュしてから D を pop するが、その後 C を出しても残るスタックは [A,B]（B が A の上）であり、A を C の後に出すことが要求されても B が邪魔をして A を先に取り出せないため不可。

補足コラム

• 単一スタックで入力順を出力順に変換可能な並びの総数は n 個の場合カタラン数（Catalan number）で表されます（例えば n=4 のときは 14 通り）。
• 実務的には、スタックで実現できるかは「ある要素を出したい時、それより前に入った要素のうち出力済でないものが上に出てきてしまうか」をチェックするだけで判定できます。
• 複数スタックやキュー＋スタック等を組み合わせると可能な並びのクラスは変わります。問題によって許される操作の違いに注意しましょう。

FAQ