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

答えは c です（選択肢cはOCRが乱れていますが、正解は「D, C, B, A」のような後入れ先出しで出力できる列）。

スタックはお皿を積むイメージ。一番上のお皿（最後に置いたもの）からしか取れません。これをLIFO（後入れ先出し）と言います。

A→B→C→Dの順にお皿を全部積んでから取ると、D→C→B→Aの順に出てくる、というのがスタックの基本動作です。

👉 覚え方：スタック＝お皿の山。最後に積んだものから取る。

ほかの選択肢（a, b, d）は、途中で取り出した後に「下にあるはずのもの」が先に出てくる順番なので、1つのスタックでは作れません。

なぜこれが正解か

正解は c。スタックはLIFO（Last In First Out）で動くので、push（積む）とpop（取り出す）を任意に組み合わせて到着順A,B,C,Dを別順序で出力できる。c の「D,C,B,A」型は全部pushしてから順次popすれば作れる典型パターン。

各選択肢の解説（スタック動作で検証）

• a「A,D,B,C」：push A → pop A → push B,C,D → pop D。次にpopするとCが出るのでBは取れず不可能。
• b「B,D,A,C」：push A,B → pop B → push C,D → pop D。次pop=Cが出てAが取れず不可能。
• d「D,C,A,B」：push A,B,C,D → pop D,C。次pop=Bが出てAが先に取れず不可能。
• c：全push後に順次pop、または途中popで作成可能 → 可能。

覚え方・ひっかけ注意

「到着順より早い文字が、より遅い文字の後ろに来る場合、その間の文字は降順でなければならない」がスタック出力可能の判定ルール。Aが最後に出てくる候補は必ず可能（全push→全pop）。キュー（FIFO）と混同しないこと。

理論的背景

到着順 1,2,…,n に対してスタック1つで生成可能な出力順序の総数はカタラン数 C_n = (2n)! / (n!(n+1)!) で与えられる。n=4 のとき C_4 = 14通り、全順序 4! = 24通りの中で14通りだけが実現可能。判定アルゴリズムは「次に出力すべき値がスタックトップなら pop、未到着なら順次 push」で実現可能性をO(n)で判定できる。

紛らわしい禁止パターン

出力列に i, j, k （i<j<k）が i, k, j の順で並ぶ部分列が存在するならスタック生成不可能（Knuth's stack-sortable theorem の特殊ケース）。a, b, d はいずれもこのパターンを含む。

試験での位置づけ

基本情報「アルゴリズムとデータ構造」分野で頻出。スタックは関数呼び出し（コールスタック）・式評価（逆ポーランド記法）・再帰のシミュレーション・括弧の対応判定など実務直結。

応用：実装上の発展

• 2スタックでキューを実装：1スタックで入力、もう1スタックで出力に逆順移送する古典問題。
• コールスタック：CPUのスタックポインタとリターンアドレスの仕組み、バッファオーバーフロー攻撃の原理（スタック破壊型）の理解はセキュリティ分野（応用情報・SC）で必須。
• 逆ポーランド記法（RPN）：演算子をスタックに積みながら式を評価する古典アルゴリズム。コンパイラの構文解析でも使われる。

選択肢の発展補足

bの「B,D,A,C」のような順序を可能にするには2つのスタックや両端キュー（deque）が必要になる。データ構造選定の根本判断にも繋がる典型例。