データ構造

データ及びデータ構造

令和元年度 秋期 問 62

下から上へ品物を積み上げて、上にある品物から順に取り出す装置がある。この装置に対する操作は、次の二つに限られる。

PUSH x : 品物 x を 1 個積み上げる。
POP : 一番上の品物を 1 個取り出す。

最初は何も積まれていない状態から開始して、 a、 b、c の順で三つの品物が到着する。一つの装置だけを使った場合、POP 操作で取り出される品物の順番として あり得ないもの はどれか。

ア　a, b, c

イ　b, a, c

ウ　c, a, b

エ　c, b, a

令和元年度 秋期 問 62

解答

ウ　 c, a, b

ア　 a, b, c の場合

この手順で取り出される順番は、a, b, c となります。

イ　 b, a, c の場合

この手順で取り出される順番は、b, a, c となります。

ウ　 c, a, b の場合

エの場合 を見るとわかるように、c を最初に取り出すには、a, b, c の順番に連続で PUSH する必要があります。
このとき、取り出す順番は c, b, a だけになります。

よって、c, a, b で取り出されることは あり得ないです。

エ　 c, b, a の場合

この手順で取り出される順番は、c, b, a となります。