解説

スタック（LIFO: 後入れ先出し）の動作を問う問題です。入力順は A、C、K、S、T で、出力順は S、T、A、C、K にしたい。ポップしたら必ず出力する（取り出して保留はできない）、スタック間の文字移動は不可、という制約があります。まず出力の前半を考えると、S と T は入力された時点で即座に出力すればよいので、どれかのスタックに積んですぐポップすれば済みます。問題は A、C、K の3文字です。これらは S、T より先に入力されますが、出力は S、T の後で、しかも入力と同じ順序（A→C→K）で出力しなければなりません。スタックは後入れ先出しの構造なので、同じスタックに2文字以上積むと取り出し順が必ず逆転します。例えば A と C を同じスタックに積むと C が先に出てしまい、A→C の順に出力できません。したがって A、C、K はそれぞれ別のスタックに1文字ずつ保管するしかなく、最低3個のスタックが必要です。S と T は既存の3個のうち空いているスタックを使い回せるため追加は不要で、ウが正解です。

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

選択肢 ア

スタック1個では、A、C、K の3文字を積むと取り出し順が K、C、A と完全に逆転してしまい、求められている A→C→K の順では出力できません。LIFO（後入れ先出し）構造の根本的な性質により、積んだ順と同じ順で取り出すことは不可能です。入力順を保ったまま後で出力したい文字が複数ある場合、1個のスタックでは対応できないことを理解しているかが問われています。

選択肢 イ

スタック2個の場合、A、C、K の3文字を保管するには、鳩の巣原理により少なくとも2文字がどれか同じスタックに入ります。同じスタックに入った2文字は取り出し順が必ず逆転するため、A→C→K という入力順どおりの出力が実現できません。例えば A と C を同じスタックに積めば C が先に出てしまいます。3文字を順序保存するには3個の独立した保管場所が必要です。

選択肢 エ

スタック4個あれば A、C、K を別々に保管して順番に取り出すことは当然可能ですが、この問題が問うているのは「最小限必要となる」個数です。3個で A、C、K の保管と S、T の通過処理がすべて実現できるため、4個は最小ではありません。「実現可能な個数」と「最小の個数」は別の問いであることに注意し、より少ない個数で可能かを必ず検討する姿勢が必要です。

解くときのポイント

スタック問題は「同じスタックに積んだ2文字は必ず逆順で出る」が判断基準。入力順のまま出力したい文字の数だけスタックが要る、と整理すると速い。