Thinkers'Studio
JavaとC言語の自習ツール
スタック

スタックの要点

 スタック(stack)は、複数のデータを取り扱うときのデータ構造のひとつです。
 次のような特徴を持ちます。
  • データの出入口がひとつしかない
     データをどんどん上に重ねて入れ、取り出すときは上から取るというイメージです(よく下の図のように表わされます)。
  • データをスタックに入れる操作はプッシュ(push)、取り出す操作はポップ(pop)という
  • 最後に入れた先頭のデータだけが取り出しの対象になる
     下敷きになっているデータを取り出すことはできません。下の図の状態で B や A は取り出せません。C を取り出した後は、B が先頭になるので B を取り出せます。
    スタックのイメージ
    データの出入口がひとつだけで、データを押し込んだり(push)、ポンと取り出す(pop)感じが分かりやすいですね。
  • このような方式は、次のように呼ばれる
     先に入れたデータを後で取り出す -- 「先入れ後出し」(FILO : First In Last Out)
     後に入れたデータが先に取り出される --「後入れ先出し」(LIFO : Last In First Out)
     どちらも同じことを言っています。

 スタックはデータ構造ですから、プログラムの処理内容に合わせて効率的にデータを持つことが、それを使う目的です。
 上のような特徴を持つスタックを使うと扱い易いときに、プログラムで実装することを考えます(別の機会に、C言語での使用例を紹介します)。

スタックの例(スタック領域)

 スタックの例としてよく挙げられるのが、プログラムのローカル変数や関数呼び出しの情報が格納されるスタック領域です。 まさにこのスタックの構造を使って実装されています。

スタック領域はたとえば ・・・
 関数(1) を呼び出すとき、スタックには関数(1) の引数と関数(1) のローカル変数領域が割り当てられます。
 関数(1) で関数(2) が呼び出されると、スタックに関数(2) の引数と関数(2) のローカル変数領域がのっかります。
 関数(2) を抜けて関数(1) に戻ったときには、関数(1) は関数(2) を呼び出す前と同じように変数を参照できます。

基本情報試験のスタック関連の問題

 スタックは基本情報技術者試験の午前の出題範囲に含まれており、スタック関連の問題が頻繁に出題されています。
 下に、基本情報の過去問を 2問用意しました。 力試しにやってみてください。

  (平成22年秋期 基本情報技術者試験 午前問5)
FEスタック問題1

  (平成23年秋期 基本情報技術者試験 午前問5)
FEスタック問題2