スタックとは？

スタックの意味

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

スタックの具体例

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

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

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

スタックと関連する用語

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

スタックが出た過去問

• A, B, C, Dの順に到着するデータに対して、一つのスタックだけを用いて出力可能なデータ列はどれか。

  正解：C, B, D, A

  要点：スタックは後入れ先出し。上に残った要素を飛び越して出せない

  スタックは後入れ先出しなので、到着順に押し込みつつ任意のタイミングで取り出せるが、一度下に埋まった要素より先に上の要素を出さねばならない。C,B,D,Aは A,B,Cを積んでC,Bを取り出し、次にDを積んで取り出し、最後にAを取り出す手順で実現できる。他の3つは、まだスタックに残っている上位要素を飛び越して下位要素を出す必要が生じるため不可能である。

  出典：平成29年度 秋期 基本情報技術者試験 午前 問5（IPA）

• 再帰呼出しの説明はどれか。

  正解：関数の中で自分自身を用いた処理を行うこと

  要点：再帰呼出しは関数が自分自身を呼ぶこと。終了条件が必須

  再帰呼出しとは、ある関数の処理の中でその関数自身を呼び出すことをいう。階乗やハノイの塔、木構造の探索のように、同じ形のより小さい問題に帰着できる処理を簡潔に書ける。呼出しごとにスタックへ戻り番地と局所変数が積まれるため、終了条件を必ず用意する必要がある。

  出典：平成29年度 秋期 基本情報技術者試験 午前 問6（IPA）

• 次の二つのスタック操作を定義する。PUSH n：スタックにデータ（整数値n）をプッシュする。POP：スタックからデータをポップする。空のスタックに対して、次の順…

  正解：上から 3, 7, 1

  要点：スタックは後入れ先出し。POPは直前にPUSHした値を取り除く

  スタックは後入れ先出しなので、POPは常に直前にPUSHした値を取り除く。順に追うと、1と5を積んでPOPで5が消え残りは1。7,6,4を積んで下から1,7,6,4となり、POPで4、続くPOPで6が消えて1,7が残る。最後に3を積むので、上から順に3,7,1となる。

  出典：平成30年度 春期 基本情報技術者試験 午前 問5（IPA）

• A, C, K, S, Tの順に文字が入力される。スタックを利用して、S, T, A, C, Kという順に文字を出力するために、最小限必要となるスタックは何個か…

  正解：3

  要点：同じ順序で出したい文字数だけスタックが要る（LIFOは逆順のみ）

  スタックは後入れ先出しなので、同じスタックに積んだ複数の文字は積んだ順と逆順にしか出せない。出力の後半で A、C、K をこの順に出す必要があるが、この3文字は入力順も A、C、K なので、1つのスタックに積むと取り出しは K、C、A と逆になってしまう。よって A、C、K は別々のスタックに保持しておく必要があり、最低3個が要る。S と T は入力直後にそのまま出力できるので追加のスタックは不要である。

  出典：令和1年度 秋期 基本情報技術者試験 午前 問8（IPA）

• 三つのスタックA, B, Cのいずれの初期状態も[1, 2, 3]であるとき、再帰的に定義された関数f()を呼び出して終了した後のBの状態はどれか。ここで、スタ…

  正解：[1, 2, 3, 1, 2, 3]

  要点：スタックを2回経由すると順序は元に戻る

  この関数はAから取り出した値を一度Cに積み、再帰から戻る際にCから取り出してBへ移す。Aはスタックなので取り出す順は3,2,1で、Cには3,2,1の順に積まれる。再帰の最も深い所から戻りながらCをpopすると1,2,3の順に出てくるため、Bには元の[1,2,3]の上に1,2,3が積まれる。

  出典：令和1年度 春期 基本情報技術者試験 午前 問6（IPA）