スタックはLIFO（Last-In, First-Out）コレクションです。最後に挿入された要素が最初に取り出されます。常にトップのみに触れます。
操作
text
push(3) push(7) pop()->7 peek()->3
[ 3 ] [ 7 ] [ 3 ] [ 3 ]
[ 3 ] top
top
例
python
stack = []
stack.append('a') # push
stack.append('b') # push
top = stack[-1] # peek -> 'b'
stack.pop() # pop -> 'b'
動的配列またはリンクリストで支援される場合、すべての操作は**O(1)**です。
| 操作 | 時間 |
|---|---|
| push | O(1) |
| pop | O(1) |
| peek | O(1) |
一般的な用途
- 関数呼び出しスタック — アクティブな呼び出しとローカル変数を追跡します。
- 取り消し/やり直し — 各アクションをプッシュ。取り消すためにポップします。
- 式評価 / パース — 括弧のマッチング、中置から後置への変換。
- バックトラッキングとDFS — 戻る場所を記憶します。
なぜ重要なのか
スタックは「最も最近のことを最初に行う」というモデルを表現し、再帰からブラウザの戻るボタンまであらゆる場所に現れます。
LIFOパターンを認識することは即座にスタックを提案し、複雑な問題をしばしば数行のきれいなpush/popに変換します。