令和元年度 秋期 基本情報技術者試験 問8

解説

正解は3です。 スタックは、最後に入れたものから先に取り出すLIFO（Last In First Out：後入れ先出し）のデータ構造です。 入力順はA、C、K、S、Tで、出力順はS、T、A、C、Kです。 最初に出力するSは4番目に入力されるので、A、C、Kの3文字はSより前にどこかのスタックに積んでおく必要があります。 その後、A、C、Kは入力順と同じ順序で出力しなければなりません。 同じスタックに2文字を積むと、後から積んだ文字が先に出てきます。 例えばAの上にCを積むと、Cが先に出てしまい、A、Cの順に出力できません。 したがって、A、C、Kはそれぞれ別のスタックに積む必要があり、スタックは3個必要です。 SとTは、入力された直後にどれかのスタックへ積んですぐ取り出せば、そのまま出力できます。 【選択肢別解説】 1：× 1個では、A、C、Kが1つのスタックに積まれ、K、C、Aの逆順でしか出力できません。 2：× 2個では、A、C、Kのうち2文字が同じスタックに入ります。 その2文字は入力と逆の順で出てしまうので、出力順を守れません。 3：○ A、C、Kを別々のスタックに1文字ずつ積めば、S、Tを出力した後にA、C、Kの順で取り出せます。 これが最小の個数です。 4：× 4個でも実現できますが、3個で足りるので最小限の個数ではありません。 【ポイント】 入力順を保ったまま出力したい文字どうしは、同じスタックに入れられません。 「同じ順序で出したい文字の数」が必要なスタック数の下限になると考えると解きやすくなります。