队列（Queue）
一句话说明
队列最核心的特征只有一个：先进先出，所以它天然适合“按到达顺序处理”的问题。
先把它和栈彻底分开
- 栈：后进先出，适合“回退 / 撤销 / 递归展开”
- 队列：先进先出，适合“排队 / 分层 / 时间推进”
很多题目一旦出现下面这些信号词，你就该想到队列：
- 一层一层扩散
- 最短步数
- 按时间顺序处理
- 最近一段请求
队列的本质操作
Push：元素从队尾进入Pop：元素从队头离开Front：看队头但不删除
队头 <- [1, 2, 3, 4] <- 队尾最早进来的 1，一定最先出去。
Go 代码：最直接的队列模板
如果只是做题，最常用的是切片模拟队列。
type Queue struct {
data []int
}
func (q *Queue) Push(x int) {
q.data = append(q.data, x)
}
func (q *Queue) Pop() int {
x := q.data[0]
q.data = q.data[1:]
return x
}
func (q *Queue) Front() int {
return q.data[0]
}
func (q *Queue) Empty() bool {
return len(q.data) == 0
}
func (q *Queue) Size() int {
return len(q.data)
}这个写法的优点是简单。
在大多数算法题里已经够用了。
如果你在意底层效率：循环队列
切片头部不断弹出，长期运行可能造成底层空间不够紧凑。
如果题目就是让你“设计队列”，更标准的写法是循环数组。
type CircularQueue struct {
data []int
head, tail int
size int
capacity int
}
func NewCircularQueue(k int) *CircularQueue {
return &CircularQueue{
data: make([]int, k),
capacity: k,
}
}
func (q *CircularQueue) EnQueue(x int) bool {
if q.size == q.capacity {
return false
}
q.data[q.tail] = x
q.tail = (q.tail + 1) % q.capacity
q.size++
return true
}
func (q *CircularQueue) DeQueue() bool {
if q.size == 0 {
return false
}
q.head = (q.head + 1) % q.capacity
q.size--
return true
}
func (q *CircularQueue) Front() int {
if q.size == 0 {
return -1
}
return q.data[q.head]
}
func (q *CircularQueue) Rear() int {
if q.size == 0 {
return -1
}
idx := (q.tail - 1 + q.capacity) % q.capacity
return q.data[idx]
}双端队列为什么也经常一起出现
双端队列（Deque）允许：
- 头部进出
- 尾部进出
它在算法题里特别常见，因为：
- BFS 会用普通队列
- 单调队列会用双端队列
- 0-1 BFS 也会用双端队列
Go 代码：二叉树层序遍历
看到“层序遍历”，脑子里直接绑定队列。
func levelOrder(root *TreeNode) [][]int {
if root == nil {
return nil
}
result := [][]int{}
queue := []*TreeNode{root}
for len(queue) > 0 {
size := len(queue)
level := make([]int, 0, size)
for i := 0; i < size; i++ {
node := queue[0]
queue = queue[1:]
level = append(level, node.Val)
if node.Left != nil {
queue = append(queue, node.Left)
}
if node.Right != nil {
queue = append(queue, node.Right)
}
}
result = append(result, level)
}
return result
}Go 代码：最近请求次数
这个题本质上也是队列，因为“过期元素永远从最前面离开”。
type RecentCounter struct {
q []int
}
func Constructor() RecentCounter {
return RecentCounter{}
}
func (rc *RecentCounter) Ping(t int) int {
rc.q = append(rc.q, t)
for len(rc.q) > 0 && rc.q[0] < t-3000 {
rc.q = rc.q[1:]
}
return len(rc.q)
}单调队列和普通队列的区别
普通队列只维护“先来后到”。
单调队列还额外维护“值的单调性”。
所以滑动窗口最大值里，队列里通常存的是下标而不是值：
- 队头永远是当前窗口最优答案
- 队尾负责清理掉“不可能再成为答案”的元素
这个主题详见 单调栈与单调队列。
什么时候优先想到队列
- BFS
- 层序遍历
- 最短步数
- 时间窗口
- 先到先处理
如果题目变成“只需要维护最大值 / 最小值优先出队”，那优先想到 堆，不是普通队列。
易错点
队列题最容易错的地方
- BFS 里不要一边遍历队列一边直接用
len(queue)动态变化，层数统计要先记当前层大小。- 循环队列判断空和满时，最好单独维护
size。- 单调队列里存下标通常比存值更稳，因为要判断元素是否过期。
经典题目
- 设计循环队列 - LeetCode 622
- 二叉树的层序遍历 - LeetCode 102
- 最近的请求次数 - LeetCode 933
- 滑动窗口最大值 - LeetCode 239
- 完全平方数 - LeetCode 279