主题
第三章 栈、队列、双端队列与递归
1. 受限线性结构的思想
数组和链表都允许比较自由地访问和修改元素，而栈与队列进一步对操作位置加了限制。表面上看，这是“功能受限”；实际上，这种受限恰恰对应了一类非常稳定的问题模式。
- 栈描述“最后进入，最先处理”。
- 队列描述“先进入，先处理”。
- 双端队列描述“两端都可进入与移出”。
很多系统行为，例如函数调用、任务调度、请求排队、广度优先搜索，都天然符合这种访问规则。因此，受限线性结构是对问题规律的刻意匹配，而不是能力缩水。
2. 栈：后进先出
2.1 结构语义
栈（Stack）只允许在一端插入和删除，该端称为栈顶，遵循 LIFO, Last In First Out。
2.2 典型应用
- 函数调用栈。
- 括号匹配。
- 表达式求值。
- 深度优先搜索。
- 撤销操作和回溯。
2.3 Go 实现一个整数栈
go
package stack
import "fmt"
type Stack struct {
data []int
}
func (s *Stack) Push(v int) {
s.data = append(s.data, v)
}
func (s *Stack) Pop() (int, error) {
if len(s.data) == 0 {
return 0, fmt.Errorf("stack is empty")
}
idx := len(s.data) - 1
v := s.data[idx]
s.data = s.data[:idx]
return v, nil
}
func (s *Stack) Peek() (int, error) {
if len(s.data) == 0 {
return 0, fmt.Errorf("stack is empty")
}
return s.data[len(s.data)-1], nil
}
func (s *Stack) Len() int {
return len(s.data)
}这个实现的关键在于：只在切片尾部操作，因此 Push 和 Pop 通常都是均摊 O(1)。如果你反过来把栈顶设计在切片头部，每次弹出都要搬移元素，结构语义虽然没错，但实现就退化了。
3. 用栈解决括号匹配
下面这个例子很典型，它体现了“后进先出”为什么天然适合嵌套结构。
go
package stack
func IsBalanced(expr string) bool {
st := make([]rune, 0, len(expr))
pairs := map[rune]rune{
')': '(',
']': '[',
'}': '{',
}
for _, ch := range expr {
switch ch {
case '(', '[', '{':
st = append(st, ch)
case ')', ']', '}':
if len(st) == 0 || st[len(st)-1] != pairs[ch] {
return false
}
st = st[:len(st)-1]
}
}
return len(st) == 0
}为什么不用队列？因为右括号出现时，必须和“最近尚未匹配”的左括号配对，这正是后进先出的规律。
4. 队列：先进先出
4.1 结构语义
队列（Queue）通常在尾部入队，在头部出队，遵循 FIFO, First In First Out。
4.2 队列的典型应用
- 打印任务排队。
- 网络请求缓冲。
- 广度优先搜索。
- 消息中间件消费模型。
4.3 为什么不能直接用切片头删做高性能队列
若每次 pop front 都把 data = data[1:]，语义上可行，但长时间运行会带来底层数组无法及时收缩、头部空洞不可复用等问题。更稳健的做法是用循环队列。
5. Go 实现循环队列
go
package queue
import "fmt"
type RingQueue struct {
data []int
head, tail int
size int
}
func NewRingQueue(capacity int) *RingQueue {
if capacity < 1 {
capacity = 1
}
return &RingQueue{
data: make([]int, capacity),
}
}
func (q *RingQueue) Len() int {
return q.size
}
func (q *RingQueue) Enqueue(v int) {
if q.size == len(q.data) {
q.grow()
}
q.data[q.tail] = v
q.tail = (q.tail + 1) % len(q.data)
q.size++
}
func (q *RingQueue) Dequeue() (int, error) {
if q.size == 0 {
return 0, fmt.Errorf("queue is empty")
}
v := q.data[q.head]
q.data[q.head] = 0
q.head = (q.head + 1) % len(q.data)
q.size--
return v, nil
}
func (q *RingQueue) grow() {
next := make([]int, len(q.data)*2)
for i := 0; i < q.size; i++ {
next[i] = q.data[(q.head+i)%len(q.data)]
}
q.data = next
q.head = 0
q.tail = q.size
}循环队列的关键思想在于：物理位置可以回绕，只要逻辑顺序不乱即可。这是数据结构设计中非常重要的一类思想，即“逻辑顺序”和“物理布局”不必完全一致。
6. 双端队列：允许两端操作
双端队列（Deque）允许在头尾两端插入和删除。它比普通队列更灵活，可用于：
- 滑动窗口最值。
- 回文检查。
- 某些调度系统。
- 0-1 BFS。
双端队列可以看成对循环队列的进一步推广。如果一个问题既需要 FIFO 语义，又偶尔需要在头部或尾部补偿性操作，Deque 往往比单纯栈或队列更合适。
7. 递归和栈的关系
很多人把递归当成语法技巧，但在数据结构课程里，递归首先是一种“隐式使用栈”的执行模型。每进行一次函数调用，系统都会保存：
- 返回地址。
- 参数。
- 局部变量。
- 当前执行现场。
这就是为什么递归本质上离不开栈。
7.1 一个简单的递归例子
go
func factorial(n int) int {
if n <= 1 {
return 1
}
return n * factorial(n-1)
}这段代码虽然短，但每一层调用都会压栈。递归优雅，不代表没有代价。分析递归时必须同时思考：
- 递归树有多深。
- 每层做多少工作。
- 是否存在重复子问题。
8. BFS 为什么天然依赖队列
广度优先搜索要求“先发现的节点，先扩展它的邻居”，这本质上就是 FIFO 规则。
go
func BFS(graph map[int][]int, start int) []int {
order := make([]int, 0)
visited := map[int]bool{start: true}
q := []int{start}
for len(q) > 0 {
cur := q[0]
q = q[1:]
order = append(order, cur)
for _, next := range graph[cur] {
if visited[next] {
continue
}
visited[next] = true
q = append(q, next)
}
}
return order
}这个版本为了直观，直接用了切片模拟队列。教学阶段可以接受；若长期高频运行，则更推荐前面的循环队列实现。
9. 栈与队列的比较
| 结构 | 规则 | 典型用途 | 常见实现 |
|---|---|---|---|
| 栈 | LIFO | 递归、回溯、括号匹配 | 切片尾部、链表头部 |
| 队列 | FIFO | 调度、缓冲、BFS | 循环数组、链表 |
| 双端队列 | 两端可进出 | 滑窗、双向调度 | 循环数组 |
真正重要的不是记住表格，而是识别问题规律。例如：
- 最近进入的状态最先回退，用栈。
- 最先到来的任务最先处理，用队列。
- 两端都可能成为决策边界，用双端队列。
10. 本章小结
本章的主线不是“又多了几个容器”，而是：
- 操作限制本身可以表达问题规律。
- 栈、队列、Deque 都是在线性结构上进一步施加约束。
- 递归不是魔法，而是系统调用栈的直接表现。
- 好的实现必须让抽象语义和底层代价一致。
下一章进入树结构时，这种“不只看接口，还要看不变量和代价”的思维会继续深化。