ITパスポート｜アルゴリズムとプログラミング 問1
後に入れたデータが先に取り出されるデータ構造（以下、スタックという）がある。これを用いて、図に示すような、右側から入力されたデータの順番を変化させて、左側に出力する装置を考える。この装置に対する操作は次の3通りである。
- ①
- 右側から入力されたデータをそのまま左側に出力する。
- ②
- 右側から入力されたデータをスタックの1番上に積み上げる。
- ③
- スタックの1番上にあるデータを取り出して左側に出力する。
この装置の右側から順番にデータ A、B、C、D を入力した場合に、この①～③の操作を組み合わせても、左側に出力できない順番はどれか。
（図）右から A、B、C、D が入力され、①でそのまま左へ出力するか、②でスタックに積み、③でスタックの一番上から取り出して左へ出力する装置。
正解：エ
解説
スタックからは、積んだのと逆の順番でしか取り出せません。各選択肢の順番が作れるかを確かめます。
- ア（B，A，D，C）
- A を積む → B をそのまま出力 → A を取り出す → C を積む → D をそのまま出力 → C を取り出す。作れます。
- イ（B，D，C，A）
- A を積む → B を出力 → C を積む → D を出力 → C、A の順に取り出す。作れます。
- ウ（C，B，D，A）
- A、B を積む → C を出力 → B を取り出す → D を出力 → A を取り出す。作れます。
- エ（C，D，A，B）
- C を最初に出すには A、B を積む必要があり、上から B、A の順です。D を出した後、A を B より先に取り出すことはできません。
- エ 正解。C、D、A、B の順番は出力できません。
出典：平成28年度秋期 ITパスポート試験 公開問題 問92（読点「，」を「、」に改変）