平成28年度 秋期 ITパスポート試験 公開問題 問92 解説 スタックのデータ構造

この問題は、スタックというデータ構造の根本的なルールである「後入れ先出し（LIFO：Last-In First-Out）」を理解しているかを問うています。正解を見つけるための最も確実な方法は、各選択肢の出力順序を実現するためにどのような操作が必要かを、1つずつシミュレートすることです。

不可能な順序である「エ」を例に、なぜ出力できないのかを確認してみましょう。

1. $C$ を最初に出力するためには、その前に入力される $A$ と $B$ をスタックに保存しておく必要があります（操作②）。このとき、スタックの中身は下から順に $A, B$ となっています。
2. 次に $C$ が右から来たときに、そのまま左へ出力します（操作①）。
3. 続いて $D$ を出力するためには、右から来た $D$ をそのまま左へ出力します（操作①）。ここまでの出力は $C, D$ です。
4. この時点で、スタックには $A$ と $B$ が残っており、上にあるのは後に入れた $B$ です。
5. スタックから取り出す（操作③）と、必ず $B$ が先に出て、その次に $A$ が出ます。

つまり、最初に $C, D$ と出力した場合、その後に続くのは必ず $B, A$ の順になり、$A, B$ の順で出すことは物理的に不可能です。

スタックの仕組みとLIFO

スタックは、データを机の上に積み上げる本のように管理する構造です。新しい本は一番上に積み、使うときも一番上から取ります。この「最後に置いたものが、最初に取り出される」という性質を LIFO (Last-In First-Out) と呼びます。

この問題の装置は、以下の3つのルートを持っています。

• 通路をそのまま通り抜ける（操作①）
• 一時保管場所（スタック）に置く（操作②）
• 一時保管場所の「一番上」から取り出す（操作③）

ポイントは、一度スタックに入れてしまったデータは、自分より後にスタックに入ったデータがすべて運び出されるまで、外に出られないという点です。選択肢「エ」において $A$ が $B$ より先に出力できないのは、スタック内で $B$ が $A$ の上に蓋（ふた）をしてしまっているからです。

なぜスタックを学ぶのか

ITパスポート試験でスタックが頻出する理由は、コンピュータの内部動作において極めて重要な役割を果たしているからです。

例えば、プログラミングにおいて「関数の中で別の関数を呼び出す」という処理が行われる際、呼び出し元のプログラムがどこまで進んでいたかという情報をスタックに積み上げます。処理が終わるとスタックから情報を取り出し（ポップし）、元の場所に戻ります。このように「途中の状態を一時的に保存し、後で逆順に辿って戻る」という処理にスタックは最適です。

また、私たちが日常的に使うアプリケーションの「元に戻す（Undo）」機能もスタックで実現されています。操作した履歴をスタックに積み上げ、キャンセルしたいときは一番新しい履歴から順に取り除いていくことで、直前の状態を復元しています。

この問題を解く力は、単なるパズルではなく、コンピュータが「手順をどのように管理し、複雑な処理を矛盾なく実行しているか」という論理的思考の基礎につながっています。

参考リンク

• スタックとは - ITを分かりやすく解説
• JavaScriptでスタック(Stack)のデータ構造を実装する
• スタック (データ構造) - Wikipedia