主题
第三章 栈、队列、双端队列与递归
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)。如果你反过来把栈顶设计在切片头部，每次弹出都要搬移元素，结构语义虽然没错，但实现就退化了。