スタックとは？

詳細解説

スタック（Stack）は、データの追加（push）と取り出し（pop）をデータ構造の「最上部（トップ）」のみで行う後入れ先出し（LIFO: Last In, First Out）のデータ構造です。実生活では「皿の積み重ね」に例えられます。最後に積んだ皿から先に取り出す構造と同じです。プログラムの動作においてはとくに重要で、関数呼び出しのたびに「スタックフレーム」（戻りアドレス・ローカル変数）が積まれ、関数が返ると消去される「コールスタック」として機能します。再帰処理の深さが深すぎると「スタックオーバーフロー」が発生するのはこの仕組みによります。また、数式の後置記法（逆ポーランド記法）の計算、ブラウザの「戻る」機能、テキストエディタのUndo（取り消し）機能などに使われます。FE試験では「スタックへの操作のトレース（push/pop後のトップ要素を問う）」「コールスタックの動作（再帰処理での積み重ね）」が頻出です。実装上は配列またはリンクリストで実現できます。

FE試験での出題ポイント

• 1LIFO（後入れ先出し）の原則・push/pop操作のトレース
• 2コールスタック：関数呼び出しのたびにスタックフレームが積まれる
• 3逆ポーランド記法の計算処理でスタックを使う
• 4再帰の深さ超過→スタックオーバーフロー

関連用語