令和元年度秋期 ITパスポート 問62 解説
下から上へ品物を積み上げて，上にある品物から順に取り出す装置がある。この装置に対する操作は，次の二つに限られる。
PUSH x：品物xを1個積み上げる。
POP：一番上の品物を1個取り出す。
最初は何も積まれていない状態から開始して，a，b，cの順で三つの品物が到着する。一つの装置だけを使った場合，POP操作で取り出される品物の順番としてあり得ないものはどれか。
- アa，b，c
- イb，a，c
- ウc，a，b
- エc，b，a
答えを見る
正解 ウc，a，b
要点スタックは後入れ先出し（LIFO）で、最後に入れたものから取り出す
解説
装置は後から入れた品物を先に取り出すスタック（LIFO）です。cを最初に取り出すには、a、b、cを全て積んでからPOPする必要があり、その時点で上からc、b、aの順に積まれています。そのため、c の次に取り出せるのはbで、aを先に取り出すことはできません。よってウのc、a、bはあり得ません。
- ア：PUSH a、POP、PUSH b、POP、PUSH c、POPで可能。
- イ：PUSH a、PUSH b、POP、POP、PUSH c、POPで可能。
- エ：a、b、cを全て積んでからPOPを3回で可能。