正答3
解説
正解は3です。
図は、A、B、Cが右から順にスタックへ入り、上から取り出されて左へ出力される様子を示しています。
スタックは後入れ先出し（LIFO：Last In First Out）のデータ構造です。
挿入と取出しのタイミングを工夫して、どの出力順序が作れるかを数えます。
【計算】
A、B、Cの並べ方は全部で3!＝6通りです。
ABCは、挿入と取出しを1つずつ交互に行えば得られます。
ACBは、Aを入れて出し、B、Cを入れてからC、Bの順に出せば得られます。
BACは、A、Bを入れてB、Aと出し、最後にCを入れて出せば得られます。
BCAは、A、Bを入れてBを出し、Cを入れて出し、最後にAを出せば得られます。
CBAは、すべて入れてからC、B、Aの順に出せば得られます。
CABは作れません。
Cを最初に出す時点ではA、Bがスタックに残っており、Bが上にあるので、次にAを出すことはできません。
したがって、作れる順序は6－1＝5通りです。
【選択肢別解説】
1：× 3通りは少なすぎます。
【計算】のとおり、ABC、ACB、BAC、BCA、CBAの5通りが作れます。
2：× 4通りは、作れる順序を1つ数え落とした値です。
作れないのはCABの1通りだけなので、正しくは5通りです。
3：○ 6通りの並びのうちCABだけが作れないので、5通りです。
4：× 6通りは3つのデータの全順列の数です。
スタックの制約によりCABは出力できないので、6通りにはなりません。
【ポイント】
n個のデータをスタックに通して得られる出力順序の数はカタラン数で表され、n＝3のとき5通りです。
「先に出したものより前に入れたものは、入れた順の逆にしか出せない」と考えると判定が速くなります。