正答3
解説
正解は3です。
スタックは後から入れたデータを先に取り出すLIFO(Last In First Out:後入れ先出し)の構造です。
到着順A、B、C、Dのまま、途中で取り出し(pop)を挟めるとして、各出力列が作れるかを確かめます。
【選択肢別解説】
1:× AをpushしてすぐpopすればAが出せます。
次にDを出すにはB、C、Dをpushする必要があり、Dのあとに出せるのはCです。
Bを先に出すことはできません。
2:× A、Bをpushし、Bをpopします。
続いてC、Dをpushし、Dをpopすると、スタックの一番上はCです。
Aを先に出すことはできません。
3:○ A、B、Cをpushし、C、Bの順にpopします。
次にDをpushしてpopし、最後に残ったAをpopすれば、C、B、D、Aの順に出力できます。
4:× A、B、C、Dをすべてpushし、D、Cの順にpopすると、一番上はBです。
Aを先に出すことはできません。
【ポイント】
スタックでは、あるデータを出した時点でその下に残っているデータは、積んだ順の逆順でしか出せません。
出力列の中に「下にあるものが上にあるものより先に出る」箇所があれば実現不可能と判断できます。