スタックの出力順序の数
出典: 平成28年度 春期 応用情報技術者試験 午前 問5 (IPA)
A，B，C の順序で入力されるデータがある。各データについてスタックへの挿入と取出しを 1 回ずつ行うことができる場合，データの出力順序は何通りあるか。
- ア 3
- イ 4
- ウ 5
- エ 6
正解と解説を見る
正解: ウ
- ア: 3 通りより多くの順序が作れます (ABC、ACB、BAC、BCA、CBA)。
- イ: 4 通りより多くの順序が作れます (ABC、ACB、BAC、BCA、CBA)。
- ウ: CAB 以外の 5 通りが作れるので正しい答えです。
- エ: 6 通りは全ての並べ方の数です。CAB はスタックでは作れません。
ポイント
A，B，C の順に入れ、途中で好きなときに取り出せる場合の出力順序を数えます。
- ABC、ACB、BAC、BCA、CBA の 5 通り です。
- CAB だけはできません。C を先に出すには A と B を積んだままにする必要があり、そのとき B が A より上にあるので、A を B より先に出せません。