データ構造 (全8問中1問目)
No.1
下から上へ品物を積み上げて，上にある品物から順に取り出す装置がある。この装置に対する操作は，次の二つに限られる。
PUSH x：品物xを1個積み上げる。
POP：一番上の品物を1個取り出す。
最初は何も積まれていない状態から開始して，a，b，cの順で三つの品物が到着する。一つの装置だけを使った場合，POP操作で取り出される品物の順番としてあり得ないものはどれか。
PUSH x：品物xを1個積み上げる。
POP：一番上の品物を1個取り出す。
出典：令和元年秋期 問62
- a，b，c
- b，a，c
- c，a，b
- c，b，a
分類
テクノロジ系 » アルゴリズムとプログラミング » データ構造
正解
ウ
解説
本問のようにPUSHとPOPという2つの操作のみによって、データの追加と削除を行うデータ構造を「スタック」といいます。スタックにおいて取り出すデータは、常に最後に入れたデータになるので後入れ先出しと呼ばれます。
選択肢ごとにPUSH操作とPOP操作のみで順番が実現できるか検証します。[ ]は装置の中の状態を表しています。横向きになっていますが左側を装置の底として考えてください。
選択肢ごとに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]次にaを取り出す必要がありますが、POP操作を行うとbが取り出されます。bより下に積まれているaは、bより先に取り出すことができません。
PUSH b：[a，b]
PUSH c：[a，b，c]
POP：[a，b] → cを取り出す - 以下の手順で可能です。PUSH a：[a]
PUSH b：[a，b]
PUSH c：[a，b，c]
POP：[a，b] → cを取り出す
POP：[a] → bを取り出す
POP：[] → aを取り出す