スタックとは？

スタックの意味

最後に入れたデータを最初に取り出す（後入れ先出し）データ構造。push（積む）とpop（取り出す）で操作する。関数呼出し時の戻り番地や局所変数の退避・復元に使われる。

スタックの具体例

再帰呼出しでは、呼び出すたびに現在の状態をスタックへ積み、戻るときに逆順で復元する。逆ポーランド表記の評価もスタックで行う。

スタックは試験でどう引っ掛けられる？

n個の要素をスタック経由で出力するときに作れる順序の総数はカタラン数になる。単純にn!ではない。

スタックと関連する用語

• キュー
• 逆ポーランド表記法

スタックが出た過去問

• 4ブロックのキャッシュメモリC0〜C3が表に示す状態である。ここで，新たに別のブロックの内容をキャッシュメモリにロードする必要が生じたとき，C2のブロックを置換…

  正解：LRU

  要点：LRUは最終参照が最古、FIFOはロードが最古を追い出す

  C2は最終参照時刻が0:05で4つの中で最も古く、最後に使われてから最も長く放置されている。最長未使用のブロックを追い出すのはLRUである。FIFOならロード時刻が最も古いC0、LIFOなら最も新しいC3、LFUなら参照回数が最少のC1が対象になる。

  出典：平成29年度 春期 高度共通_午前I試験 am1 問6（IPA）

• 再帰的な処理を実現するためには、再帰的に呼び出したときのレジスタ及びメモリの内容を保存しておく必要がある。そのための記憶管理方式はどれか。

  正解：LIFO

  要点：再帰呼出しの退避・復元はLIFO（スタック）で行う

  再帰呼出しでは、呼び出しのたびに戻り番地やレジスタの内容、局所変数を退避し、復帰時には最後に退避したものから順に取り出す必要がある。この「後入れ先出し」の順序で管理する方式がLIFO（スタック）であり、実際にプログラムの実行時にはスタック領域が用いられる。

  出典：平成30年度 春期 高度共通_午前I試験 am1 問3（IPA）

• 式A+B×Cの逆ポーランド表記法による表現として、適切なものはどれか。

  正解：ABC×+

  要点：逆ポーランド表記は被演算子の後ろに演算子を置く後置記法

  逆ポーランド表記法（後置記法）では、被演算子を先に並べ、演算子をその後ろに置く。A+B×Cは乗算が先なのでBC×となり、これとAを加算するのでABC×+となる。左から読み、被演算子はスタックに積み、演算子が現れたら直前の2つを取り出して演算する、と考えると確認しやすい。

  出典：令和2年度 10月 高度共通_午前I試験 am1 問1（IPA）

• A, B, Cの順序で入力されるデータがある。各データについてスタックへの挿入と取出しを1回ずつ行うことができる場合、データの出力順序は何通りあるか。

  正解：5

  要点：スタックで作れる出力順序の数はカタラン数になる

  スタックはLIFOなので、各データについて挿入・取出しを1回ずつ行うときに得られる出力順序の数はカタラン数で求められ、要素3個では5通りになる。実際に列挙すると、ABC・ACB・BAC・BCA・CBAの5通りが可能である。先にCを出してから残りをA→Bの順に出すこと（CAB）は、Cを取り出した時点でスタック内がB・Aの並びになっているため実現できない。

  出典：令和3年度 春期 高度共通_午前I試験 am1 問2（IPA）

• A, B, Cの順序で入力されるデータがある。各データについてスタックへの挿入と取出しを1回ずつ行うことができる場合、データの出力順序は何通りあるか。

  正解：5

  要点：スタック経由の出力順序数は要素数nのカタラン数

  各データについて挿入と取出しを1回ずつ行える場合の出力順序の総数は、要素数nに対するカタラン数で求まる。n＝3のときは5通りであり、具体的にはABC、ACB、BAC、BCA、CBAが実現できる。入力順の最初の要素より前に後続要素を出し切ったうえで先頭要素を最後より前に出すCABだけは、スタックのLIFO性から作れない。

  出典：令和7年度 春期 高度共通_午前I試験 am1 問3（IPA）