令和1年度 秋期 ITパスポート 問62（テクノロジ）
出典：令和元年度 秋期 ITパスポート試験 公開問題 問62（独立行政法人情報処理推進機構（IPA））
下から上へ品物を積み上げて，上にある品物から順に取り出す装置がある。この装置に対する操作は，次の二つに限られる。
PUSH x：品物xを1個積み上げる。
POP：一番上の品物を1個取り出す。
最初は何も積まれていない状態から開始して，a，b，cの順で三つの品物が到着する。一つの装置だけを使った場合，POP操作で取り出される品物の順番としてあり得ないものはどれか。
- アa，b，c
- イb，a，c
- ウc，a，b
- エc，b，a
正解と解説を見る
正解：ウ
【スタックの仕組み】
問題の装置は、下から上へ品物を積み上げ、上にある品物から順に取り出します。最後に入れたものを最初に取り出す（LIFO：Last In First Out、後入れ先出し）このようなデータ構造を、スタックといいます。
・PUSH：一番上に積む
・POP：一番上から取り出す
品物は a、b、c の順に到着するので、PUSHもこの順にしか行えません。ただし、途中で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 を全て積む必要があり、そのとき上から c、b、a の順に積まれています。c の次に取り出せるのは b なので、c、a、b の順はあり得ません。
エ：c、b、a の順は、PUSH a、PUSH b、PUSH c の後に、POPを3回行えば取り出せます。
よって、正解は選択肢ウです。