スタックで得られる出力順序の数
出典: 令和7年度 春期 応用情報技術者試験 午前 問5 (IPA)
A，B，C の順序で入力されるデータがある。各データについてスタックへの挿入と取出しを 1 回ずつ行うことができる場合，データの出力順序は何通りあるか。
- ア 3
- イ 4
- ウ 5
- エ 6
正解と解説を見る
正解: ウ
- ア: 3 通りでは足りません。A B C, A C B, B A C, B C A, C B A の 5 通りがあります。
- イ: 4 通りでは足りません。5 通りあります。
- ウ: 出力できる順序は A B C, A C B, B A C, B C A, C B A の 5 通りなので正しい答えです。
- エ: 6 通りは全順列の数です。C A B は出力できないので 5 通りです。
ポイント
A, B, C の順に入力し、スタックの挿入 (push) と取出し (pop) を組み合わせて並べ替えます。出力順を全て書き出します。
| 出力順 | 操作 |
|---|---|
| A B C | A 入れて出す、B 入れて出す、C 入れて出す |
| A C B | A 入れて出す、B, C を入れて C, B の順に出す |
| B A C | A, B を入れて B, A の順に出す、C |
| B C A | A, B を入れて B を出し、C を入れて出し、A を出す |
| C B A | A, B, C を入れて C, B, A の順に出す |
C A B は、A が B より下にあるため出せません。よって 5 通り です。