跳到主要内容

Queue | 队列

什么是队列,用生活中的例子,比如高速上,单行道上汽车进出隧道,过程中只能有且仅容纳一辆车行驶而过

那么进队列就像是进隧道

进队列

那么出队列就像是出隧道

出队列

什么是队列

所以队列(queue)是一种 线性的逻辑结构, 队列中的元素只能先进先出 FIFO(first in first out). 队列的 队头 叫 front, 队列的 队尾 叫 rear

队列的入队和出队

数组举个例子

这是一个队列
const queue = []
// [1,2,3,4,5]

入队(enqueue)

// 入队列
queue.push() // queue.push(6)
// [1,2,3,4,5,6]

出队(dequeue)

// 出队列
queue.shift()
// [2,3,4,5,6]

队列的应用

队列的输出顺序和输入顺序相同,所以队列通常用于对“历史”的回放,也就 是按照“历史”顺序,把“历史”重演一遍。

例如在多线程中,争夺公平锁的等待队列,就是按照访问顺序来决定线程在队列中的次序的。

再如网络爬虫实现网站抓取时,也是把待抓取的网站URL存入队列中,再按照存入队列的顺序来依次抓取和解析的。

参考

漫画算法:小灰的算法之旅