正答3
解説
正解は3です。
図は、A、B、Cの順に右からデータが入り、スタックの上端から左へ取り出される構造を示しています。
スタックは後入れ先出し（LIFO：Last In First Out）なので、挿入と取出しの順序の組合せによって出力順序が変わります。
【計算】
Aを入れてすぐ出し、Bも同様にし、Cも同様にすると、出力はABCです。
Aを出したあとB、Cを入れてから出すと、出力はACBです。
A、Bを入れてBを先に出し、Aを出してからCを出すと、出力はBACです。
A、Bを入れてBを出し、Cを入れて出してからAを出すと、出力はBCAです。
A、B、Cを全部入れてから出すと、出力はCBAです。
CABは、Cを最初に出すためにA、Bが入った状態になり、Bより先にAを出せないので実現できません。
よって、出力順序は5通りです。
【選択肢別解説】
1：× 3通りでは、上で示した5通りのうち一部しか数えていません。
挿入と取出しを途中で交互に行うパターンも含める必要があります。
2：× 4通りでは、BCAのように一度取り出してから新たに挿入するパターンを数え漏らしています。
実現できる順序は5通りです。
3：○ 実現できる順序はABC、ACB、BAC、BCA、CBAの5通りです。
この数はカタラン数と呼ばれ、n＝3のとき5になります。
4：× 6通りは、3個のデータの並べ方すべて（3！＝6）です。
スタックではCの後にAを出してからBを出すCABが作れないので、6通りにはなりません。
【ポイント】
n個のデータをスタックに通して得られる出力順序の数はカタラン数で、n＝3で5通り、n＝4で14通りです。
「最初に出たものより前に入ったデータは、入った順と逆にしか出せない」と考えると、実現できない順序を見分けられます。