什么是栈，它的用途是什么？

Question

什么是栈，它的用途是什么？

IT Interview Practice · Accepted Answer

**栈** 是一个 **LIFO**（后进先出）集合：最后被推入的元素首先被弹出。您只能访问 **顶部** 元素。

## Operations

```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)**。

| Operation | Time |
|---|---|
| push | O(1) |
| pop | O(1) |
| peek | O(1) |

## 常见用途

- **函数调用栈** — 追踪活跃的调用和局部变量。
- **撤销/重做** — 推入每个动作；弹出来撤销。
- **表达式求值 / 解析** — 匹配括号、将中缀转换为后缀。
- **回溯 & DFS** — 记住返回的位置。

## 为什么这很重要

栈对

Operations