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