スタックとは？
スタック（Stack）は後入れ先出し（LIFO、Last In First Out）の原則に従うデータ構造です。最後に入れたデータが最初に取り出されます。
お皿を積み重ねることを想像してください。新しいお皿は一番上に置き、使うときも一番上から取ります。これがまさにスタックの動作原理です。
なぜ重要か？
スタックはプログラミングの最も基本的なデータ構造であり、驚くほど多くの場所で使われています。
- •関数コールスタック: プログラムの関数呼び出しと復帰がスタックで管理される
- •DFS実装: 深さ優先探索を反復で実装する際にスタックを使用
- •コーディングテスト必須: 括弧検査、ヒストグラム最大長方形、株価問題など
主要操作
| 操作 | 説明 | 時間計算量 |
|---|---|---|
| push(item) | スタックの一番上に要素を追加 | O(1) |
| pop() | 一番上の要素を削除して返却 | O(1) |
| peek() / top() | 一番上の要素を確認（削除しない） | O(1) |
| isEmpty() | スタックが空かどうか確認 | O(1) |
すべての操作がO(1)です。常に一番上（top）でのみ作業するためです。
実践活用例
1. 括弧検査
プログラミングで最も一般的なスタックの活用です。開き括弧に出会ったらpush、閉じ括弧に出会ったらpopしてペアが合うか確認します。
- •
(),[],{}— 正しい括弧 - •
([)]— 正しくない括弧
2. ブラウザの戻る・進む
戻るスタックと進むスタックの2つを使用します。新しいページ訪問時に現在のページを戻るスタックにpushし、戻る時に進むスタックにpushします。
3. 元に戻す（Undo）
テキストエディタのCtrl+Zがスタックです。すべての操作をスタックにpushし、取り消す時にpopします。
4. DFS（深さ優先探索）
再帰の代わりに明示的なスタックを使ってDFSを実装できます。スタックからノードを取り出し、隣接ノードをpushする方式です。
スタック vs キュー
| 比較 | スタック | キュー |
|---|---|---|
| 原理 | LIFO（後入れ先出し） | FIFO（先入れ先出し） |
| 例え | お皿の積み重ね | 行列に並ぶ |
| 追加 | push（一番上） | enqueue（一番後ろ） |
| 削除 | pop（一番上） | dequeue（一番前） |
| 活用 | DFS、括弧検査、Undo | BFS、プリンタキュー、キャッシュ |
コーディングテストでよく出るスタック問題パターン
単調スタック — スタックの要素を単調増加・単調減少順に維持しながら、O(n)で「次に大きい要素」や「前の小さい要素」を見つけるテクニックです。
- •株価問題：価格が下がらなかった期間を計算
- •ヒストグラム：最大長方形の面積
- •次に大きい数：各要素の右側で最初に大きい数を見つける
よくあるミス
- •空のスタックでpopやpeekを呼び出してエラー発生 → isEmpty確認必須
- •括弧問題で開き括弧だけ残っているのに確認せず通過処理
- •単調スタックでpush/pop条件を逆に設定
AlgoNoteで直接確認しましょう
push、pop操作が実行された時にスタックがどう変化するか、AlgoNoteで一段階ずつ視覚的に確認できます。さまざまな操作シーケンスを直接入力して実験してみてください。