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

スタックで出力可能な順序はどれか【午前2 解説】

要点まとめ

• 結論: 到着順 A, B, C, D に対して一つのスタックで出力可能なのは選択肢のうち ウ (C, B, D, A) だけです。
• 根拠: スタックは後入れ先出し(LIFO)なので、到着時に積んだ要素は直後に出力する以外は下から取り出せず、出力順はスタック操作で再現可能かどうかで決まります。
• 差がつくポイント: 入力を「即時出力」するか「積む」かの判断を到着順にシミュレーションして、常に欲しい次の出力がスタックのトップか現在到着要素かを確認します。

正解の理由

1. A を積む（出力しない）
2. B を積む（出力しない）
3. C が到着したら即座に出力（必要な最初の要素）
4. スタックのトップは B なので B を出力
5. D が到着したら即座に出力
6. 残った A をスタックから出力
   以上により C, B, D, A が得られ、スタックの LIFO 性を満たしています。

よくある誤解

• 「到着時に必ず積むべき」と思い込み、到着要素を即時出力できることを忘れて誤判断する。到着要素は積まずに直接出力できる点が重要です。
• スタック内の要素を任意の順で取り出せると誤解する。下層の要素は上の要素をすべて取り出さないとアクセスできません。
• 到着順の中間操作を記録せず直感で判定してしまい、早めに矛盾に気付けないことがある。

解法ステップ

1. 空のスタックを用意し、次に出力したい要素を目標順列の先頭に設定する。
2. 入力列を先頭から順に見ていく。各要素について：
   • 現在到着した要素が目標の次の出力ならば（積まずに）出力し、目標のポインタを進める。
   • そうでなければスタックに積む。
3. 入力要素を処理した後、スタックのトップが目標の次の出力ならばポップして出力、ポップを繰り返す。
4. 最終的に目標順列をすべて出力できればその順列は「スタックで可能」、途中で必要な要素がスタックのトップにない状態で矛盾が生じれば不可能。
5. 実際の試験では各選択肢をこのシミュレーションで検証するのが最短確実。

選択肢別の誤答解説

• ア：A, D, B, C
  • A を最初に出力するため A を即時出力（OK）。その後 B, C を積んだ状態で D が到着すると D は出力可能です。しかし D 出力後のスタックのトップは C のため次に B を出力することはできず、順序を実現できません。従って不可能です。
• イ：B, D, A, C
  • B を先に得るために A を積んで B を出力（OK）。その後 C を積み、D を出力（OK）するとスタックには A（底）と C（上）が残ります。次に A を出力したいがトップは C のため不可能です。よって不可能です。
• ウ：C, B, D, A（正解）
  • シミュレーション: A を積む → B を積む → C を到着時に出力 → スタックのトップ B をポップして出力 → D を到着時に出力 → 残った A をポップして出力。すべて可能です。
• エ：D, C, A, B
  • D を最初に出力するためには A, B, C を積んだ後に D を出力する必要がありますが、D 出力後に C を出力するためにはスタックトップが C でなければならず、積んだ順序の関係からそのままでは成立しません。試すと矛盾が生じます。

補足コラム

• スタックで実現可能な並べ替え（スタック順列）は数学的には「スタックパーミュテーション」と呼ばれ、全順列のうち実現可能なものの個数はカタラン数で表されます。
• 判定の鍵は「現在欲しい出力がスタックのトップか到着要素か」を逐次チェックすること。試験では紙にスタックを簡単に書いてシミュレーションすると確実です。

FAQ