平成22年度 春期 ITパスポート試験 問85 解説 スタックのデータ構造

この問題は、入力順 $X, Y, Z$ をスタックというデータ構造の制約に従って並び替えたとき、どのような出力順が実現可能かを問うものです。スタックは「後入れ先出し（LIFO：Last-In, First-Out）」というルールを持ち、「最後に入れたデータを最初に取り出す」ことしかできません。

解答のコツは、各選択肢の順序になるように、入力・スタックへの積込・スタックからの取出しをシミュレーションすることです。

スタックの基本ルール

スタックは、皿を重ねるような構造です。上から皿を置き、上から皿を取る動作を繰り返します。このとき、最も新しく入れたデータが常に一番上にあり、一番最初に取り出されます。したがって、入力順が決まっている中で、スタックを挟むと「一度スタックに入れたものは、後から入れたものほど先に出力される」という制約が加わります。

順序の検証プロセス

入力順が $X, Y, Z$ と固定されている場合、それぞれの選択肢が実現可能か確認します。

• ア $X, Z, Y$ の場合：

  1. $X$ を入力し、そのまま左側へ出力（操作1）。
  2. $Y$ を入力し、スタックへ積む（操作2）。
  3. $Z$ を入力し、そのまま左側へ出力（操作1）。
  4. スタックに残った $Y$ を取り出す（操作3）。 結果：$X, Z, Y$ となり実現可能です。

• イ $Y, Z, X$ の場合：

  1. $X$ をスタックへ積む（操作2）。
  2. $Y$ を入力し、そのまま左側へ出力（操作1）。
  3. $Z$ を入力し、そのまま左側へ出力（操作1）。
  4. スタックに残った $X$ を取り出す（操作3）。 結果：$Y, Z, X$ となり実現可能です。

• ウ $Z, X, Y$ の場合： まず $Z$ を出力するには、その前にある $X$ と $Y$ をすべてスタックに積まなければなりません。スタックには下が $X$、上が $Y$ の順で積まれます。この状態で $Z$ を出力した後、次にスタックから取り出せるのは一番上の $Y$ です。したがって $Z, Y, X$ の順にはなりますが、$Z, X, Y$ という順序で取り出すことはスタックの構造上できません。

• エ $Z, Y, X$ の場合：

  1. $X, Y, Z$ を順番にスタックへ積む（操作2を3回）。
  2. スタックから $Z, Y, X$ の順で取り出す（操作3を3回）。 結果：$Z, Y, X$ となり実現可能です。

データ構造とアルゴリズムの考え方

この問題は、コンピュータがデータを処理する際の「順序の制御」を理解しているかを問うています。スタックの構造は、例えばWebブラウザの「戻る」ボタン（直前に見たページが最後に出る）や、プログラムにおける関数の呼び出し管理（最後に行われた処理から先に終了する）など、現代のITシステムにおいて非常に重要な役割を果たしています。

試験対策としては、単に暗記するのではなく、実際に手元で「積む・出す」のシミュレーションができるようにしておくことが重要です。試験中に時間が許せば、簡単なメモ用紙に「スタック」と「出力順」の枠を書いて動かしてみるのが、最も確実な正答への近道です。

参考リンク

• ITパスポート試験のスタックとキューのわかりやすい解説
• スタック構造を使ってブラウザの戻る機能を再現してみた（Qiita）
• データ構造スタックの正確な定義（Wikipedia）