応用情報技術者 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