アルゴリズム ⏱ 7min 重要度 ★★★★★ 頻出 ★★★★★

スタック

まず結論

スタックはLIFO（Last In First Out）＝「最後に入れたものが最初に出てくる」データ構造。お皿を重ねるイメージで、push（上に積む）とpop（上から取り出す）の2操作が基本。関数呼び出しのコールスタック・Undo機能・括弧チェックなど実用例が多く、試験に頻出。

📚 スタックとは

スタック（Stack）は、データを一方向にしか出し入れできない線形データ構造です。「スタック」は英語で「積み重ね」を意味し、まさにお皿やトレーを重ねるような動作をします。

LIFO = Last In, First Out
最後に追加したデータが、最初に取り出せる。逆に、最初に追加したデータは最後にしか取り出せない。
push（プッシュ）

スタックの先頭（top）にデータを追加する操作。お皿を上に重ねるイメージ。

pop（ポップ）

スタックの先頭（top）からデータを取り出す操作。一番上のお皿を取るイメージ。

※ peek（top参照）：取り出さずに先頭の値だけ確認する操作もよく使われる。

🖼️ スタックの動き（図解）

push(A) → push(B) → push(C) → pop() の順番で操作したとき、スタックがどう変化するかを見てみましょう。

push(A)
A
← top
底
→
push(B)
B
A
← top
底
→
push(C)
C
B
A
← top
底
→
pop() → 「C」を取得
B
A
← top
底

最後に push した C が、pop で最初に取り出される（LIFO）

トレース表

操作取得値スタックの内容（底→top）
push(A)—[ A ]
push(B)—[ A, B ]
push(C)—[ A, B, C ]
pop()C[ A, B ]
pop()B[ A ]
pop()A[ 空 ]

💻 擬似コードでの実装

スタックは配列で実装できます。top という変数で「次にデータを入れる位置」を管理します。

// スタックの初期化
配列 stack[100]
top ← -1          // 空状態は -1

// push 操作：値を積む
手続き push(value):
    もし top ≥ 99 ならば
        エラー（スタックオーバーフロー）
    そうでなければ
        top ← top + 1
        stack[top] ← value

// pop 操作：値を取り出す
関数 pop():
    もし top < 0 ならば
        エラー（アンダーフロー）
    そうでなければ
        val ← stack[top]
        top ← top - 1
        返す val

🔧 実際の用途

1
関数呼び出しのコールスタック
プログラムが関数を呼び出すとき、戻り先のアドレスをスタックに積む。関数が終わるとスタックから取り出して元の場所に戻る。再帰呼び出しが深すぎると「スタックオーバーフロー」が発生。
2
Undo（元に戻す）操作
テキストエディタやグラフィックツールで「Ctrl+Z」で元に戻す機能。操作履歴をスタックに積み、Undoするたびにpopして一つ前の状態に戻す。
3
括弧の対応チェック
「( [ { } ] )」のような入れ子構造の括弧が正しく対応しているか検査するアルゴリズム。開き括弧をpush、閉じ括弧が来たらpopして種類が一致するか確認する。
4
ブラウザの「戻る」機能
訪問したURLをスタックに積み、「戻る」ボタンでpopする。まさにLIFOの動作。
スタックオーバーフローとは
スタックの容量上限を超えてpushしようとしたときに発生するエラー。無限再帰（終了条件のない再帰）で起こりやすい。

🎯 試験での出方

⚠️ よくある間違い

✍️ 確認クイズ

Q1. 空のスタックに対して push(X)・push(Y)・push(Z)・pop()・pop() の順に操作した後、スタックに残っている要素は何か？
push(X)→[X]、push(Y)→[X,Y]、push(Z)→[X,Y,Z]、pop()→Z取得[X,Y]、pop()→Y取得[X]。残るのは最初に積んだXのみ。LIFOなので後から積んだものから順に取り出される。
Q2. スタックの「push」と「pop」の操作に関する説明として正しいものはどれか？
スタックはtop（先頭）からのみ操作する。pushでtopに積み、popでtopから取り出す。底（bottom）は変わらない。両端から操作するのはデック（deque）という別の構造。
Q3. プログラムが関数を呼び出す際にスタックを使用するのはなぜか？最も適切な理由はどれか？
関数を呼び出すたびに戻りアドレス・引数・ローカル変数などをスタックフレームとしてpushし、関数が終わるとpopして呼び出し元に戻る。LIFOの性質が「最後に呼んだ関数から先に戻る」という動作と完全に一致する。
Q4. スタックを使って「()」「[]」「{}」の括弧の対応が正しいかチェックするアルゴリズムの説明として正しいものはどれか？
スタックによる括弧チェックはスタックの典型的な応用例です。開き括弧（(,[,{）をpushし、閉じ括弧（),],}）が来たらpopして対応する開き括弧と一致するか確認。文字列を全て処理した後にスタックが空なら全ての括弧が正しく対応しています。
Q5. スタックとキューの違いとして正しいものはどれか？
イが正解。スタック=LIFO（Last In First Out：後入れ先出し）。キュー=FIFO（First In First Out：先入れ先出し）。スタックは関数呼び出し・元に戻す（Undo）など、キューは印刷待ちキュー・BFS（幅優先探索）などに使われます。
← 連結リスト 一覧 キュー →

Sponsor Link