スタックとは？

スタックの意味

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

スタックの具体例

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

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

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

スタックと関連する用語

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

スタックが出た過去問

• 逆ポーランド表記法で表された式を評価する場合、途中の結果を格納するためのスタックを用意し、式の項や演算子を左から右に順に入力し処理する。スタックが図の状態のとき…

  正解：C 演算子 D

  要点：RPNは演算子で上位2つをポップ、後から出た方が左項

  逆ポーランド表記法の評価では、演算子が現れるとスタックから2つ取り出して演算し、結果を積み直します。先に取り出されるのはスタックの最上位である D で、次が C です。二項演算では先に取り出した値が右側の被演算数になるため、中置表記に直すと C 演算子 D となります。引き算や割り算のように順序が結果に影響する演算では、この向きの取り違えが誤答に直結します。

  出典：平成28年度 秋期 応用情報技術者試験 午前 問3（IPA）

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

  正解：5

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

  3個のデータに対する push と pop の並べ方の総数はカタラン数C(3)=5通りである。実際に列挙すると ABC、ACB、BAC、BCA、CBA の5通りで、CABは作れない。Aより先にCを出した時点でBはAより先に出るしかないためである。

  出典：平成28年度 春期 応用情報技術者試験 午前 問5（IPA）

• CPUのスタックポインタが示すものはどれか。

  正解：サブルーチン呼出し時に，戻り先アドレス及びレジスタの内容を格納するメモリのアドレス

  要点：スタックポインタは退避データを積む位置を指す

  スタックポインタは、スタック領域の先頭位置を保持するレジスタである。サブルーチン呼出しや割込みの際に戻り先アドレスやレジスタ内容を退避する場所を示す。

  出典：平成28年度 春期 応用情報技術者試験 午前 問8（IPA）

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

  正解：LIFO

  要点：再帰の状態退避はLIFO（スタック）で管理する

  再帰呼出しでは、呼び出した順序と逆の順序で復帰するため、最後に退避した情報を最初に取り出す必要がある。この後入れ先出しの性質をもつ記憶管理方式がLIFOであり、スタックとして実装される。復帰アドレスやレジスタの内容はスタックフレームとして積み上げられる。

  出典：平成30年度 春期 応用情報技術者試験 午前 問8（IPA）

• プログラムの実行時に利用される記憶領域にスタック領域とヒープ領域がある。それらの領域に関する記述のうち、適切なものはどれか。

  正解：サブルーチンからの戻り番地の退避にはスタック領域が使用され、割当てと解放の順序に関連がないデータの格納にはヒープ領域が使用される。

  要点：スタックは後入れ先出し、ヒープは任意順で確保・解放する領域

  スタック領域は後入れ先出しで管理され、サブルーチンの戻り番地や局所変数など、呼出しと復帰に対応して確保・解放されるデータに使われる。一方ヒープ領域は任意の時点で確保と解放ができるため、確保順と解放順が対応しない動的データの格納に使われる。

  出典：令和1年度 春期 応用情報技術者試験 午前 問17（IPA）