令和元年度 秋期 基本情報技術者試験 午前 問8
テクノロジ／アルゴリズムA, C, K, S, T の順に文字が入力される。スタックを利用して，S, T, A, C, K という順に文字を出力するために，最小限必要となるスタックは何個か。ここで，どのスタックにおいてもポップ操作が実行されたときには必ず文字を出力する。また，スタック間の文字の移動は行わない。
出典：令和元年度 秋期 基本情報技術者試験 午前 問8
- ア1
- イ2
- ウ3
- エ4
正解：ウ
解説
スタックは後入れ先出しなので，一つのスタックに複数の文字を積むと，取り出す順序は積んだ順の逆になります。A, C, K, S, T の入力に対して S と T は入力直後にそのまま出力できますが，残る A, C, K はこの順で出力しなければなりません。同じスタックに2文字以上を積むと押し込んだ順の逆にしか出せないため，A，C，K は別々のスタックに1文字ずつ保持する必要があり，最小3個となります。
選択肢ごとの解説
- ア誤り。1個だと A, C, K を積んだ後の取出し順が K, C, A となり，要求される A, C, K の順に出せません。
- イ誤り。2個では A, C, K のいずれか2文字が同じスタックに入り，その2文字は入力順の逆にしか出せないため出力順を満たせません。
- ウ正しい。A，C，K をそれぞれ別のスタックに1文字ずつ積み，S，T は入力直後に出力してから A，C，K を順にポップすれば実現できます。
- エ誤り。4個あれば実現できますが，3個で足りるので「最小限必要となる」個数ではありません。