ITパスポート｜アルゴリズムとプログラミング 問2
下から上へ品物を積み上げて、上にある品物から順に取り出す装置がある。この装置に対する操作は、次の二つに限られる。
- PUSH x
- 品物 x を1個積み上げる。
- POP
- 一番上の品物を1個取り出す。
最初は何も積まれていない状態から開始して、a、b、c の順で三つの品物が到着する。一つの装置だけを使った場合、POP 操作で取り出される品物の順番としてあり得ないものはどれか。
正解：ウ
解説
この装置は、後から入れたものを先に取り出す、スタック（後入れ先出し）です。到着した品物を積んだり、途中で取り出したりして、それぞれの順番が作れるかを確かめます。
- ア（a，b，c）
- PUSH a → POP a → PUSH b → POP b → PUSH c → POP c で作れます。
- イ（b，a，c）
- PUSH a → PUSH b → POP b → POP a → PUSH c → POP c で作れます。
- ウ（c，a，b）
- c を最初に取り出すには、a、b、c を全部積む必要があります。そのとき上から c、b、a の順なので、c の次に取り出せるのは b で、a は取り出せません。
- エ（c，b，a）
- a、b、c を全部積んでから、POP を 3 回行えば作れます。
- ウ 正解。c、a、b の順番はあり得ません。
出典：令和元年度秋期 ITパスポート試験 公開問題 問62（読点「，」を「、」に改変）