応用情報技術者 2012年 春期 午前2 問06

スタックの出力順序【午前2解説】

正解の理由

解法ステップ

1. スタックは LIFO（後入れ先出し）であることを確認する。
2. 入力順 A → B → C に対し、各要素を push するか pop するかの操作列で到達可能な出力列を列挙する。
3. 列挙による確認、または一般式（カタラン数）で個数を求める。n 個の場合の個数はカタラン数 $C_n=\frac{1}{n+1}\left(\genfrac{}{}{0ex}{}{2n}{n}\right)$ であり、ここで $n=3$ より $$C_3=\frac{1}{4}\left(\genfrac{}{}{0ex}{}{6}{3}\right)=\frac{1}{4}\times 20=5.$$

• ABC: push A, pop A → A； push B, pop B → B； push C, pop C → C
• ACB: push A, pop A → A； push B, push C, pop C → C, pop B → B
• BAC: push A, push B, pop B → B, pop A → A； push C, pop C → C
• BCA: push A, push B, pop B → B； push C, pop C → C； pop A → A
• CBA: push A, push B, push C, pop C → C, pop B → B, pop A → A

選択肢別の誤答解説

• ア: 3
  スタックで可能な順序は 3 より多く、列挙すれば 5 通り存在するため過小評価です。
• イ: 4
  4 とするのは一つを見落としているケースです。実際はもう1通り（例えば BCA や BAC のどちらか）を含めると 5 になります。
• ウ: 5（正解）
  上述の5通り（ABC, ACB, BAC, BCA, CBA）がすべて実現可能で、個数は 5 です。
• エ: 6
  6 は全順列の数ですが、スタック制約により順列のうち少なくとも1つ（CAB）が実現不可能なので、総数は 6 にはなりません。

よくある誤解

• 全ての順列が可能だと考える誤り：スタックは LIFO なので、途中で上にある要素を先に取り出さなければならず、例えば CAB のように C を取り出した後に A を B より先に取り出すことはできません。
• 操作手順の説明ミス：列挙する際に push/pop の順序と対応する出力を正しく書かないと、実現可能かどうかを誤判断しやすいです。各出力に対して「どの時点で pop したか」を明示すると誤りが減ります。

補足コラム

FAQ