Queue
Queue(队列)
基本特性
- FIFO原则：最先添加的元素最先被移除
- 两个主要操作端
- 队尾(rear/back)：添加元素的位置
- 队头(front/head)：移除元素的位置
- 约束：只能在两端操作，不能在中间插入或删除
逻辑结构
┌─────────────────────────────────────────┐
│ Queue │
├──────────┬──────┬──────┬──────┬─────────┤
│ Front │ │ │ │ Rear │
│ (Head) │ │ │ │ (Tail) │
├──────────┴──────┴──────┴──────┴─────────┤
│ ^ 出队方向 入队方向 ^ │
│ <──────────────────────────────────── │
└─────────────────────────────────────────┘
状态演变
初始状态（空队列）:
┌───┬───┬───┬───┬───┬───┐
│ │ │ │ │ │ │
└───┴───┴───┴───┴───┴───┘
^
front = rear = 0
入队元素 A:
┌───┬───┬───┬───┬───┬───┐
│ A │ │ │ │ │ │
└───┴───┴───┴───┴───┴───┘
↑ ^
front rear
入队元素 B, C:
┌───┬───┬───┬───┬───┬───┐
│ A │ B │ C │ │ │ │
└───┴───┴───┴───┴───┴───┘
^ ^
front rear
出队元素 A:
┌───┬───┬───┬───┬───┬───┐
│ │ B │ C │ │ │ │
└───┴───┴───┴───┴───┴───┘
^ ^
front rear
操作
- 入队(enqueue)
- 在队尾添加元素，时间复杂度O(1)
- 出队(dequeue)
- 从队头移除并返回元素，时间复杂度O(1)
- 查看队头元素，不移除(peek)
- 时间复杂度：O(1)
- 检查队列是否为空
- 返回队列中元素数量
实现
基本队列(Naive Queue)
基于数组的实现
这是一种很直观的做法，但是非常不推荐\
实现方式
- 用数组
arr[N]存储元素 front指向队头，rear指向队尾- 入队：
arr[rear++] = x - 出队：返回
arr[front++]
操作很简单，但是会造成以下问题
- 空间浪费
- 出队操作后，
front会不断右移 - 数组前面的空间空了，但无法复用
- 例如：容量10,入队10个，出队5个，数组前半部分空了，但
rear还在10 -> 后续最多只能再放0个元素
- 出队操作后，
- 低效的解决方式
- 可以每次出队后，把数组前半部分的元素整体向左移动
- 代价高：
O(n)每次出队 -> 很慢
这种做法仅适用于理解队列状态变化
工业级基于数组的实现是Circular Queue
基于链表的实现
这是正统的做法
特点
- enqueue：O(1)
- dequeue：O(1)
- 不需要扩容
head -> [A] -> [B] -> [C] -> null
双端队列(Deque)
Deque(Double Ended Queue)，可以在队头和队尾进行插入和删除操作的数据结构
| 操作 | 含义 | 时间复杂度 |
|---|---|---|
push_front | 从头部插入 | O(1) |
push_back | 从尾部插入 | O(1) |
pop_front | 从头部删除 | O(1) |
pop_back | 从尾部删除 | O(1) |
逻辑结构
┌─────────────────────────────────────────┐
│ Deque │
├───────┬─────────┬─────────┬─────────────┤
│ Front │ │ │ Rear │
│ (Head)│ │ │ (Tail) │
├───────┴─────────┴─────────┴─────────────┤
│ ← 出/入队方向 出/入队方向 → │
└─────────────────────────────────────────┘
状态演变
初始状态:
┌───┬───┬───┬───┬───┐
│ │ │ │ │ │
└───┴───┴───┴───┴───┘
从前端添加 X，从后端添加 Y:
┌───┬───┬───┬───┬───┐
│ X │ │ │ │ Y │
└───┴───┴───┴───┴───┘
↑ ↑
front rear
继续从前端添加 A，从后端添加 B:
┌───┬───┬───┬───┬───┐
│ A │ X │ │ Y │ B │
└───┴───┴───┴───┴───┘
↑ ↑
front rear
实现
双向链表实现
结构
node <-> node <-> node
优点
- 实现简单
- 任意长度
- 插入删除绝对O(1)
缺点
- 每个节点两个指针 -> 内存大
- cache miss 非常严重
- 实际性能差
高性能场景不会使用这个版本
循环数组
这是最常见的手写实现
核心思想
用一个数组 + 两个索引
[ _ _ A B C D _ _ ]
↑ ↑
head tail
索引取模
next = (i + 1) % capacity;
结构
buffer[]
head index
tail index
size
优点
- 连续内存
- cache 极友好
- 实现简单
- 实际工程最常用
缺点
- 需要扩容
- 扩容需要整体搬移
STL风格分段数组
这是std::deque的真实实现方式
结构类似这样
[block][block][block][block]
↓ ↓
[64] [64]
本质是指针数组 -> 每个指针指向一个小块连续内存
优点
- 两端扩容不用整体搬迁
- 连续块 + 灵活
- 综合性能最强
缺点
- 实现复杂
- 手写成本高
使用场景
Deque的接口简单，底层实现高度工程化
适合用于两端高频操作的场景
Deque是系统级最重要的数据结构之一
简单程度像队列，工程价值像内存管理器
算法领域Deque是万金油
不该使用Deque的场景
- 只尾部push/pop -> vector
- 只FIFO -> queue
- 需要随机访问 -> vector
- 任意位置插删 -> list
- 按优先级 -> priority_queue
一旦开始用Deque的中间索引访问元素，说明选错结构了
优先队列(Priority Queue)
循环队列(Circular Queue)
阻塞队列(Blocking Queue)
应用场景
- BFS
- 生产者/消费者模型
- 任务调度/消息系统
- 单调队列