栈 是一个 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 — 记住返回的位置。
为什么这很重要
栈对
