スタックの要点

　スタック（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）

　　（平成23年秋期 基本情報技術者試験 午前問5）