下から上へ品物を積み上げて，上にある品物から順に取り出す装置がある。
この装置に対する操作は，次の二つに限られる。
PUSH x：品物xを1個積み上げる。
POP：一番上の品物を1個取り出す。
最初は何も積まれていない状態から開始して，a，b，cの順で三つの品物が到着する。
一つの装置だけを使った場合，POP操作で取り出される品物の順番としてあり得ないものはどれか。
正答3
解説
正解は3です。
この問題は「あり得ないもの」を選ぶので、○ が答え（実現できない取り出し順）です。
図には、PUSHの矢印が装置の上から入り、POPの矢印が上から出ていく様子が描かれています。
つまり、最後に積んだ品物から先に取り出すスタック（LIFO：Last In First Out、後入れ先出し）です。
品物は必ずa、b、cの順に積まれるので、各順番が実現できるかを確かめます。
【選択肢別解説】
1：× PUSH a、POP、PUSH b、POP、PUSH c、POPと操作すると、a、b、cの順に取り出せます。
あり得る順番です。
2：× PUSH a、PUSH b、POP、POP、PUSH c、POPと操作すると、b、a、cの順に取り出せます。
あり得る順番です。
3：○ cを最初に取り出すには、a、b、cをすべて積んでからPOPする必要があります。
そのとき装置の一番上はbなので、次にaを取り出すことはできません。
4：× PUSH a、PUSH b、PUSH c、POP、POP、POPと操作すると、c、b、aの順に取り出せます。
あり得る順番です。
【ポイント】
スタックは後入れ先出し、キューは先入れ先出し（FIFO：First In First Out）です。
スタックでは、ある品物を取り出した時点で、それより下にある品物は積んだ順の逆でしか出てきません。