栈（Stack）
栈最重要的不是
push / pop，而是“最近进入的信息最先参与决策”，所以它天然适合括号匹配、撤销操作和单调结构。
核心思路
栈是一种**后进先出（LIFO - Last In First Out）**的线性数据结构。只能在栈顶进行插入（push）和删除（pop）操作。
栈顶 → ┌─────┐
│ 3 │ ← 最后进入
├─────┤
│ 2 │
├─────┤
│ 1 │ ← 最先进入
└─────┘
核心特点
- 后进先出（LIFO）：最后压入的元素最先弹出
- 单端操作：只能在栈顶进行操作
- 受限的线性表：限制了插入和删除的位置
基本操作
时间复杂度
| 操作 | 时间复杂度 | 说明 |
|---|---|---|
| push（入栈） | O(1) | 在栈顶添加元素 |
| pop（出栈） | O(1) | 弹出栈顶元素 |
| peek/top（查看栈顶） | O(1) | 查看但不删除 |
| isEmpty（判空） | O(1) | 检查栈是否为空 |
| size（获取大小） | O(1) | 返回栈中元素个数 |
空间复杂度
- O(n)：n 为栈中元素个数
Go 代码
基于切片实现
type Stack struct {
items []int
}
func (s *Stack) Push(val int) {
s.items = append(s.items, val)
}
func (s *Stack) Pop() (int, error) {
if s.IsEmpty() {
return 0, errors.New("stack is empty")
}
index := len(s.items) - 1
val := s.items[index]
s.items = s.items[:index]
return val, nil
}
func (s *Stack) Peek() (int, error) {
if s.IsEmpty() {
return 0, errors.New("stack is empty")
}
return s.items[len(s.items)-1], nil
}
func (s *Stack) IsEmpty() bool {
return len(s.items) == 0
}
func (s *Stack) Size() int {
return len(s.items)
}单调栈模板
func dailyTemperatures(temperatures []int) []int {
n := len(temperatures)
res := make([]int, n)
stack := []int{}
for i := 0; i < n; i++ {
for len(stack) > 0 && temperatures[i] > temperatures[stack[len(stack)-1]] {
j := stack[len(stack)-1]
stack = stack[:len(stack)-1]
res[j] = i - j
}
stack = append(stack, i)
}
return res
}怎么识别栈题
- 题目涉及最近匹配关系。
- 需要处理括号、表达式、撤销。
- 需要找“下一个更大元素 / 更小元素”。
- 处理顺序天然带有“后来的先结算”。
常用场景与技巧
经典题目
括号匹配类
表达式求值
单调栈
- 每日温度 - LeetCode 739
- 下一个更大元素 I - LeetCode 496
- 下一个更大元素 II - LeetCode 503
- 柱状图中最大的矩形 - LeetCode 84
- 接雨水 - LeetCode 42
栈的设计
其他应用
单调栈详解
单调栈是一种特殊的栈，栈内元素保持单调性（递增或递减）。
应用场景
- 寻找下一个更大/更小元素
- 区间最大/最小值问题
- 矩形面积问题
易错点
栈题最容易错的地方，通常不是思想，而是出栈条件写错一个等号。
- 先判断空栈，再访问栈顶。
- 单调栈要想清楚维护的是“下标”还是“值”，大多数题维护下标更稳。
- 出栈条件要分清严格大于还是大于等于，这会直接影响重复元素处理。
- 用切片模拟栈时，回退长度就是出栈，不要保留脏数据引用。
优缺点
优点
- ✅ 操作简单，时间复杂度 O(1)
- ✅ 自动管理内存（函数调用栈）
- ✅ 实现简单
缺点
- ❌ 只能访问栈顶元素
- ❌ 功能受限
- ❌ 可能栈溢出
应用场景
- 函数调用：函数调用栈
- 表达式求值：中缀、后缀表达式
- 括号匹配：编译器语法检查
- 撤销操作：编辑器的 Undo/Redo
- 浏览器历史：前进/后退
- 深度优先搜索（DFS）：图的遍历