解説

A・B・Cの順に入力されるデータを、各データについてスタックへの挿入と取出しを1回ずつ行う場合の出力順序の組み合わせ数を求めます。スタックはLIFO（後入先出し）構造です。各ステップで「次の入力をスタックにプッシュ」か「スタックからポップして出力」を選択できます。全組み合わせを列挙すると: ①A→B→C出力(ABC) ②A→B出力→C出力→A出力→(BAC、BCx不可) ③A→B→C→Cポップ→Bポップ→Aポップ(CBA) ④A→Aポップ→B→C→Cポップ→Bポップ(ACB) ⑤A→Aポップ→B→Bポップ→C→Cポップ(ABC=重複)。正しく列挙するとABC、ACB、BAC、BCA、CBAの5通りです（AとBとCの一部だけが有効）。スタックの制約上CBxAやxCABなど一部の並びは不可能で、合計5通りが正解です。

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

選択肢 ア

3通りは過少な評価です。スタックの特性を利用すれば、ABCの順から複数の出力順を生成できます。単純に「逆順・正順・その他1通り」と誤って解釈した場合に出やすい誤答です。

選択肢 イ

4通りは1通り少ない数え間違いです。全ての有効なプッシュ・ポップの組み合わせを体系的に列挙していくと5通り存在します。

選択肢 エ

6通りはスタックの制約を無視して全順列3!=6を答えた場合です。スタックにより一部の順序（CABなど）は生成不可能であり、最大でも5通りです。

解くときのポイント

スタックで作れない順列の見分け方：「後に入れたものが先に出る必要がある」制約に違反するものを排除する。n要素のスタック出力順序はカタラン数C(n)で、n=3のときC(3)=5。n=4ではC(4)=14。