解説

A→B→Cの順に入力され、各データに対してスタックへの挿入と取出しを1回ずつ行える場合の出力順序を数えます。スタックはLIFO（後入れ先出し）です。可能な出力順序を列挙すると：①ABC（Aを挿入→取出し→Bを挿入→取出し→Cを挿入→取出し）②ACB（A取出し→B挿入→C挿入→C取出し→B取出し）③BAC（A・B挿入→B取出し→A取出し→C挿入→C取出し）④BCA（A・B挿入→B取出し→C挿入→C取出し→A取出し）⑤CBA（A・B・C挿入→C取出し→B取出し→A取出し）の5通りです。なお「CAB」はスタックの性質上実現不可能（CをAより先に取り出すにはBとAがスタックに残っている必要がある）であり、6通りにはなりません。

なぜ他の選択肢は違うのか

選択肢 ア

3通りは過少評価です。スタックを使わず単純に通過させた場合（ABCのみ）や一部の組み合わせを見落とした場合に誤りやすい選択肢です。

選択肢 イ

4通りも不正解です。5通りのうち1つを見落とした場合に選びがちです。ABCを全パターン列挙する際の確認が必要です。

選択肢 エ

6通りは3つの値の全順列（3!=6）ですが、スタックの制約上「CAB」は実現不可能なため6通りにはなりません。スタックなし（単純キュー的）に混同しないよう注意。

解くときのポイント

スタックの出力順列は必ず全列挙で確認する。n=3のとき最大5通り（カタラン数C(3)=5）。「CAB」が不可能である理由（CをAより先に出すにはAが下にあるがBも残っている矛盾）を理解する。