下から上へ品物を積み上げて、上にある品物から順に取り出す装置がある。
この装置に対する操作は、次の二つに限られる。
PUSH x:品物xを1個積み上げる。
POP:一番上の品物を1個取り出す。
最初は何も積まれていない状態から開始してa、b、cの順で三つの品物が到着する。
一つの装置だけを使った場合、POP操作で取り出される品物の順番としてあり得ないものはどれか。
ア | a、b、c |
イ | b、a、c |
ウ | c、a、b |
エ | c、b、a |
答え ウ
【解説】
ア | 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は、a、b、cの順で三つの品物が到着した場合に取り出すことはできません。 |
エ | c、b、a、PUSH a→PUSH b→PUSH c→POP(c)→POP(b)→POP(a)で可能です。 |
【キーワード】
・スタック