下から上へ品物を積み上げて，上にある品物から順に取り出す装置がある。この装置に対する操作は，次の二つに限られる。 PUSH x：品物xを1個積み上げる。 POP： 一番上の品物を1個取り出す。 （下図：PUSHで品物を積み上げ，POPで取り出す装置の模式図） 最初は何も積まれていない状態から開始して，a，b，cの順で三つの品物が到着する。一つの装置だけを使った場合，POP操作で取り出される品物の順番としてあり得ないものはどれか。
- アa, b, c
- イb, a, c
- ウc, a, b
- エc, b, a
正解と解説を見る
正解
ウ c, a, b
この装置はスタック(後入れ先出し、LIFO)の動作をする装置であり、a,b,cの順に積み上げた場合、POPでは最後に積んだものから順に取り出されるのが基本(c,b,a)だが、PUSHとPOPを交互に行うことで様々な出力順が実現できる。しかし「c,a,b」という順序は、最初にcを取り出した時点でスタックにはaが下、bが上の状態で残っているため、次に取り出せるのは必ずbであり、bより先にaを取り出すことは不可能である。したがって、あり得ない順番は正解の2(c,a,b)である。