队列(英语: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>
网友评论