基本情報 平成23年度 秋期 問5｜テクノロジ系に関する問題

答えは b です。

スタックは「お皿を積み重ねる」イメージで、上から順にしか取り出せません（後入れ先出し＝LIFO）。スタック1には上からb・c・dが積まれていて、関数fでスタック1→2へ移し、関数gでスタック2から出力。b・c・d・aの順で出すには、f・f・gの繰り返しなどを組み合わせます。

👉 覚え方：fは「移す」、gは「出す」。

ほかの選択肢：他の選択肢は順番がズレて、出力がb・c・d・aにならない。

なぜこれが正解か

正解は b。スタックはLIFO（Last In First Out、後入れ先出し）のデータ構造。関数f＝スタック1からpopしてスタック2へpush、関数g＝スタック2からpopして出力。問題ではスタック1に上からb,c,d、最下層にa（前提）。b,c,d,aの順で出力するには、まずb,c,dをスタック2に移して取り出し、その後aを移して出力する手順を組む。f・f・g・f・g・f・g・gのような組み合わせ（出題のbの選択肢）で実現できる。

各選択肢の解説

• a：fとgの順序が出力順b,c,d,aを生まない。
• c：fの回数が多すぎてaが最後に出ない。
• d：開始順序が違って出力がズレる。

覚え方・ひっかけ注意

スタック2は逆順で取り出される性質を利用する。最後に出したい要素を最初にスタック2の底に置くのがコツ。実際に紙に積み木で書きながら追うのが確実。

理論的背景

2つのスタックを使った要素の並び替えは、有名な「スタックソート可能順列（stack-sortable permutation）」の問題に関連する。1つのスタックでソート可能な順列は231パターンを含まない順列（Catalan数で数えられる）として知られ、2つのスタックを使うと表現可能な順列クラスが拡大する。アルゴリズムとデータ構造の理論計算量論の入門例として教育される。

実務での使われ方

関数呼び出しのコールスタック、式評価（後置記法のスタックマシン）、深さ優先探索（DFS）、構文解析（再帰下降パーサ・LR構文解析）、Undo機能の実装で日常的に使われる。コンパイラのアクティベーションレコード管理、JavaScript/Pythonのインタプリタ実装、JVMのオペランドスタック等も同じ原理。

試験での位置づけ

基本情報のアルゴリズムとデータ構造分野で必出。スタック（LIFO）とキュー（FIFO）の対比、デック（Deque）、優先度付きキュー（ヒープ）等と組み合わせて出題。応用情報・ESS試験ではスタックオーバーフロー対策、テールコール最適化、ガベージコレクションでのスタック走査が問われる。

選択肢の発展補足

スタックは配列または連結リストで実装され、配列は高速だが容量固定、連結リストは動的だがポインタオーバーヘッドがある。並行プログラミングではロックフリースタック（Treiber stack）が知られ、CAS（Compare-And-Swap）命令で実装される。関数呼び出しのスタック深さに制限がある言語（Pythonデフォルト1000）と、末尾呼び出し最適化により無制限に再帰できる言語（Scheme、Haskell）の違いも理解しておくと応用力がつく。