总结
术语对照表
| 中文术语 | 英文术语 | 说明 |
|---|---|---|
| 队列 | Queue | 先进先出的线性表 |
| 队头 | Front | 允许删除的一端 |
| 队尾 | Rear | 允许插入的一端 |
| 入队 | Enqueue | 向队尾插入元素 |
| 出队 | Dequeue | 删除队头元素 |
| 循环队列 | Circular Queue | 数组首尾相连的队列 |
| 链式队列 | Linked Queue | 用链表实现的队列 |
| 双端队列 | Deque | 两端都可插入删除的队列 |
| 优先级队列 | Priority Queue | 按优先级出队的队列 |
| 先进先出 | FIFO | First In First Out |
| 假溢出 | False Overflow | 普通顺序队列的空间浪费问题 |
核心要点
- 队列的所有操作（入队、出队、取队头）时间复杂度均为
- 循环队列解决了普通顺序队列的假溢出问题
- 循环队列队满条件：
(rear + 1) % MaxSize == front（牺牲一个空间） - 循环队列元素个数：
(rear - front + MaxSize) % MaxSize - 链式队列出队最后一个元素时，需要更新rear指针
- 双端队列结合了栈和队列的特点，非常灵活
- 优先级队列通常用堆实现，时间复杂度