令和元年秋期試験問題 問62

下から上へ品物を積み上げて,上にある品物から順に取り出す装置がある。この装置に対する操作は,次の二つに限られる。
 PUSH x:品物xを1個積み上げる。
 POP:一番上の品物を1個取り出す。
62.png
最初は何も積まれていない状態から開始して,a,b,cの順で三つの品物が到着する。一つの装置だけを使った場合,POP操作で取り出される品物の順番としてあり得ないものはどれか。

  • a,b,c
  • b,a,c
  • c,a,b
  • c,b,a
正解 問題へ
分野:テクノロジ系
中分類:アルゴリズムとプログラミング
小分類:データ構造
解説
本問のようにPUSHとPOPという2つの操作のみによって、データの追加と削除を行うデータ構造を「スタック」といいます。スタックにおいて取り出すデータは、常に最後に入れたデータになるので後入れ先出しと呼ばれます。

選択肢ごとにPUSH操作とPOP操作のみで順番が実現できるか検証します。[ ]は装置の中の状態を表しています。横向きになっていますが左側を装置の底として考えてください。
  • 以下の手順で可能です。
    PUSH a:[a]
    POP:[] → aを取り出す
    PUSH b:[b]
    POP:[] → bを取り出す
    PUSH c:[c]
    POP:[] → cを取り出す
  • 以下の手順で可能です。
    PUSH a:[a]
    PUSH b:[a,b]
    POP:[a] → bを取り出す
    POP:[] → aを取り出す
    PUSH c:[c]
    POP:[] → cを取り出す
  • 正しい。順番としてあり得ません。
    PUSH a:[a]
    PUSH b:[a,b]
    PUSH c:[a,b,c]
    POP:[a,b] → cを取り出す
    次にaを取り出す必要がありますが、POP操作を行うとbが取り出されます。bより下に積まれているaは、bより先に取り出すことができません。
  • 以下の手順で可能です。
    PUSH a:[a]
    PUSH b:[a,b]
    PUSH c:[a,b,c]
    POP:[a,b] → cを取り出す
    POP:[a] → bを取り出す
    POP:[] → aを取り出す

Pagetop