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

スタックによる出力順序【午前解説】

正解の理由

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