スタックとは？

スタックの意味

最後に入れたデータを最初に取り出す後入先出（LIFO）のデータ構造。データを積む操作をプッシュ、取り出す操作をポップという。関数呼び出しの戻り番地の保存、式の評価、再帰処理の実現などに使われ、FEでは操作列から最終状態を答える問題が定番。

スタックの具体例

空のスタックにA、B、Cの順にプッシュすると、ポップではC、B、Aの順に出てくる。「push 1, push 2, pop, push 3, pop, pop」なら取り出される順は2、3、1となる。関数が呼ばれるたびに戻り番地を積み、戻るときに取り出す。

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

キュー（先入先出）との取り違えが最頻出。またプッシュとポップが交互に混ざる操作列では、途中経過を1つずつ書き出さないと順序を誤る。空の状態でポップするとアンダフロー、容量超過のプッシュはオーバフローとなる。

スタックと関連する用語

• キュー
• 逆ポーランド記法
• 深さ優先探索

スタックが出た過去問

• 下から上へデータを積み上げ、上にあるデータから順に取り出すデータ構造（以下、スタックという）がある。これを用いて、図に示すような、右側から入力されたデータの順番…

  正解：Z, X, Y

  要点：スタックは後入れ先出しで順序が制約される

  スタックは後に入れたものが先に出る構造なので、いったん積んだデータより先に、それより下にあるデータを取り出すことはできない。Zを最初に出すにはX、Yを順に積む必要があり、その状態でスタックの一番上はYであるから、次に出せるのはYに限られる。したがってZの次にXが出る順番は実現できない。

  出典：平成22年度 春期 ITパスポート試験 問85（IPA）

• IPv6に関する記述として、適切なものはどれか。

  正解：アドレス空間が128ビットの大きさをもつので、IPv4に比べて多くのアドレスを割り当てることができる。

  要点：IPv6は128ビットでアドレス枯渇に対応するプロトコル

  IPv6はアドレス長を128ビットに拡張したプロトコルで、32ビットのIPv4に比べて桁違いに多くのアドレスを扱える。IPv4アドレスの枯渇に対応するために策定されたもので、移行期には同一のネットワーク上で両者を併用（デュアルスタック）できる。有線・無線や伝送媒体の種類とは無関係に利用できる。

  出典：平成25年度 秋期 ITパスポート試験 問63（IPA）

• 後に入れたデータが先に取り出されるデータ構造（以下，スタックという）がある。これを用いて，図に示すような，右側から入力されたデータの順番を変化させて，左側に出力…

  正解：C, D, A, B

  要点：スタックは後入れ先出し、積んだ順の逆でしか出せない

  スタックは後入れ先出しなので、積んだ順の逆でしか取り出せない。Cを最初に出すにはAとBを積む必要があり、スタック内はAが下、Bが上になる。この状態ではAより先にBが出るため、AをBより先に出す順番は作れない。

  出典：平成28年度 秋期 ITパスポート試験 問92（IPA）

• 複数のデータが格納されているスタックからのデータの取出し方として、適切なものはどれか。

  正解：最後に格納されたデータを最初に取り出す。

  要点：スタックは後入れ先出し、キューは先入れ先出し

  積み上げた物を上から取っていくように、最後に入れたものを最初に取り出すデータ構造が問われている。この方式は後入れ先出しと呼ばれ、関数呼出しの戻り先の記録や式の評価などに使われる。先に入れたものから取り出す先入れ先出しの構造はキューである。

  出典：平成30年度 秋期 ITパスポート試験 問76（IPA）

• 先入れ先出し（First-In First-Out, FIFO）処理を行うのに適したキューと呼ばれるデータ構造に対して“8”，“1”，“6”，“3”の順に値を格…

  正解：1

  要点：キューは先入れ先出し、格納順にそのまま取り出される

  キューは先に入れたものから先に取り出される先入れ先出しのデータ構造である。8、1、6、3の順に格納したので、取出しは格納した順のまま8、1、6、3となる。したがって1回目に8、2回目に1が取り出される。後入れ先出しのスタックと取り違えないよう、構造の違いを押さえておきたい。

  出典：平成30年度 春期 ITパスポート試験 問96（IPA）