队列
2016-11-11 本文已影响0人
crf1028
队列（英语：Queue）Wiki
</br>
特点
- 是[先进先出]（FIFO, First-In-First-Out）的线性表。
- 队列只允许在后端（称为rear）进行插入操作，在前端（称为front）进行删除操作。
</br>
api及时间复杂度
| api | 作用 | 时间复杂度 |
|---|---|---|
| enqueue | 增加节点到尾端 | O(1) |
| dequeue | 删除并返回队列顶端节点数据 | O(n) |
| front | 返回队列顶端数据 | O(1) |
| len | 返回队列的长度 | O(1) |
| is_empty | 返回队列是否为空 | O(1) |
</br>
问题
- 直接删除顶端节点时间复杂度为O(n)
</br>
解决
- 不删除顶端节点，将其赋值为None
- 将Queue头尾相连以解决假满队问题
</br>
实现
- python: gist link
</br>
