問題
問92
後に入れたデータが先に取り出されるデータ構造（以下、スタックという）がある。これを用いて、図に示すような、右側から入力されたデータの順番を変化させて、左側に出力する装置を考える。この装置に対する操作は次の3通りである。
- ① 右側から入力されたデータをそのまま左側に出力する。
- ② 右側から入力されたデータをスタックの1番上に積み上げる。
- ③ スタックの1番上にあるデータを取り出して左側に出力する。
この装置の右側から順番にデータ A, B, C, Dを入力した場合に、この①～③の操作を組み合わせても、左側に出力できない順番はどれか。
- B, A, D, C
- B, D, C, A
- C, B, D, A
- C, D, A, B
[出典：ITパスポート試験 平成28年度秋期 問92]
正解
正解は「エ」です。
解説
この問題は、データ構造の一種である「スタック」の性質を理解しているかを問うものです。スタックは「Last-In, First-Out（LIFO）」、つまり最後に入れたものが最初に出てくるという特徴を持っています。具体的には、本棚に本を積み重ねていくようなイメージです。一番上に積んだ本が一番最初に取り出せますよね。 入力されるデータはA、B、C、Dの順です。
操作は①直接出力、②スタックにプッシュ（積み上げる）、③スタックからポップ（取り出す）の3種類です。選択肢「エ：C, D, A, B」が出力できない理由を考えてみましょう。 CとDを最初に出力するためには、AとBはスタックにプッシュされている必要があります。
例えば、A、Bの順にスタックにプッシュされると、スタックの中は「Bが一番上、Aがその下」という状態になります（[B, A]）。その後、C、Dを直接出力するか、スタックにプッシュしてポップします。仮にC、Dが先に出力された後、スタックに残ったA、Bをポップで取り出す場合を考えます。スタックはLIFOなので、トップにあるBが最初に取り出され、次にAが取り出されることになります。つまり、「B, A」という順序でしか取り出せません。
しかし、選択肢「エ」の出力順は「C, D, A, B」です。これは、CとDの後に「A, B」の順でデータが取り出されることを意味します。スタックにA、Bの順にプッシュした場合、ポップで「A, B」の順にデータを出すことはLIFOの原則に反するため不可能です。したがって、この出力順は実現できません。
ア(B, A, D, C):
この出力順は実現可能です。例えば、Aをスタックにプッシュし、次にBを直接出力します。その後スタックからAをポップします。次にCをスタックにプッシュし、Dを直接出力し、スタックからCをポップすると「B, A, D, C」と出力できます。
イ(B, D, C, A):
この出力順は実現可能です。例えば、Aをスタックにプッシュし、Bを直接出力します。次にCをスタックにプッシュし、Dを直接出力し、スタックからCをポップします。最後にスタックからAをポップすると「B, D, C, A」と出力できます。
ウ(C, B, D, A):
この出力順は実現可能です。例えば、A、Bをスタックにプッシュし、次にCを直接出力します。その後Dをスタックにプッシュし、スタックからD、B、Aの順にポップすると「C, D, B, A」と出力できます。
難易度
この問題は、スタックという基本的なデータ構造の概念を理解しているかに加えて、具体的な操作のシミュレーション能力が求められるため、初学者にとっては少し難しいと感じるかもしれません。各選択肢の出力順が実現可能かどうか、試行錯誤しながら確認する必要があるため、解答に時間がかかる可能性があります。
用語補足
スタック：
データを一時的に保管する領域の一種で、後に入れたデータが先に取り出される（LIFO: Last-In, First-Out）という特徴があります。例えるなら、積み重ねられたお皿のようなもので、一番上のお皿（最後に置いたお皿）からしか取り出せません。
LIFO：
「Last-In, First-Out」の略で、データが格納された順序とは逆の順序で取り出される原則を指します。スタックというデータ構造の基本的な特性です。たとえば、郵便ポストに手紙を入れる場合、最後に投函した手紙が一番上にあるので、それから順に取り出されるイメージです。
プッシュ：
スタックにデータを追加する操作のことです。お皿を積み重ねる例で言えば、新しいお皿を一番上に置く行為が「プッシュ」に当たります。
ポップ：
スタックからデータを取り出す操作のことです。スタックのLIFOの原則に従って、一番上にあるデータ（最後にプッシュされたデータ）が取り出されます。お皿の例で言えば、一番上のお皿を取り除く行為が「ポップ」です。
対策
この問題を解くためのポイントは、スタックが持つLIFO（Last-In, First-Out）の性質を正確に理解することです。データがどのようにスタックに入り、どのように出てくるのかを、入力順と出力順の関係で把握しましょう。具体的な対策としては、実際に紙とペンを使って、入力されるデータ（A, B, C, D）と、①直接出力、②プッシュ、③ポップの3つの操作を組み合わせながら、各選択肢の出力順をシミュレーションしてみる練習が有効です。特に、スタックに複数のデータが入っているときに、どの順番でしか取り出せないのかを繰り返し確認することが重要です。
