問題
問62
下から上へ品物を積み上げて、上にある品物から順に取り出す装置がある。この装置に対する操作は、次の二つに限られる。
PUSH x：品物xを1個積み上げる。
POP ：一番上の品物を1個取り出す。
最初は何も積まれていない状態から開始して、a, b, c の順で三つの品物が到着する。一つの装置だけを使った場合、POP操作で取り出される品物の順番としてあり得ないものはどれか。
- a, b, c
- b, a, c
- c, a, b
- c, b, a
[出典：ITパスポート試験 令和元年度 問62]
スポンサーリンク
正解
正解は「ウ」です。
解説
本問は、スタック（LIFO: Last In, First Out）というデータ構造の理解を問う問題です。スタックでは、最後に入れたものが最初に出るという特徴があります。a, b, cの順でPUSHされると、スタックの中は下から順にa, b, cとなります。この状態からPOP操作をすれば、最初に取り出されるのはc、その次にb、最後にaとなります。
よって、POPで取り出される順番としてあり得るのは、c, b, a、または途中で一部POPしてからまたPUSHする操作を加えたb, a, cや、b, c, aなどが可能です。
しかし、「c, a, b」の順番でPOPすることはスタック1つでは不可能です。なぜなら、cを最初にPOPした場合、aはbの下にあるため、bをPOPしなければaは取り出せません。
よって、この順番はスタックの仕様から外れるものになります。 以上から、あり得ない順番は「c, a, b」となり、正解は「ウ」です。
ア(a, b, c):
順番にPUSHして順番にPOPすればそのまま取り出せるため、あり得る順番です。
イ(b, a, c):
一部POPしてから別の順で操作することで実現可能です。
エ(c, b, a):
PUSH順a, b, cのまま全て積んでPOPすれば、この順番で取り出せるため、問題ありません。
難易度
この問題はスタック構造の基本的な理解と、操作のシミュレーションができるかを問う内容であり、初学者にはやや慣れが必要です。しかしながら、スタックの動作が明確に理解できていれば難しくはなく、基礎力確認として適切な難易度と言えます。
スポンサーリンク
用語補足
スタック：
後入れ先出し（LIFO）のデータ構造です。皿を重ねて一番上から取る動作のように、最後に入れたものが最初に取り出されます。
PUSH：
スタックにデータを「積む」操作を指します。PUSH xはxをスタックの一番上に追加します。
POP：
スタックからデータを「取り出す」操作です。最も後から積んだものが最初に取り出されます。
対策
スタックの操作（PUSH・POP）はアルゴリズムの基本です。手を動かして紙にスタックの状態を描きながら操作を追う練習が効果的です。プログラムや問題集でスタックの動作を何度も確認し、順番の変化に慣れておきましょう。
