スタックとは何ですか。また何に使われますか？

Question

IT Interview Practice · Accepted Answer

**スタック**は**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に変換します。

操作

例

関連する質問

一般的な用途

なぜ重要なのか