队列是数据结构中的一种，它与实际生活中的排队相似：在一条队伍中，先来的人总是能够先得到服务，后来的人只能排在队伍末尾等候。队列也是一样，它符合先进先出 FIFO（First Input First Out）的顺序。
那队列在我们的代码中有什么样的作用呢？还是以排队为例，当我们需要做一个排队系统时，就可以用到了，具体如下：
某个商品销售异常火爆，为了保证系统的稳定，所以限制购买的用户同时最多只能有100人，每当一个用户购买成功，下一个用户才可以进入购买者的队伍。这样既保证系统稳定，又提高了用户的购买体验（在等待期间可以提醒用户前面还有多少人）。
那队列在前端中有哪些可以使用到的地方呢？这个我们最后再说，先来看队列的 js 实现。
队列的类型
队列有两种类型：一种是和日常排队类似的队列，叫做普通队列；另一种叫做环形队列。
对于一个队列来说，有队头和队尾，以及容量。
从上图可以看出来，普通队列的队头和队尾是分开的，当队头的元素离开队列后，下一个元素就会成为队头，而新加入的元素会跟随在原本的队尾之后，成为新的队尾。
而对于环形队列来说，当只有一个元素时，队头队尾是同一个元素；当队列容量已满时，队头和队尾是连接在一起的；当队头的元素离开后，下一个元素会成为队头，而新的元素则会插入原本队头的位置成为新的队尾。
在容量确定的情况下，普通队列前面的元素离开后，对应的内存就会被空置，而在环形队列中，前面的元素离开，新的元素就会占据原来的内存。相比之下，就容量而言，环形队列具有更高的内存利用率，可以减小内存的开支消耗。
实现一个环形队列
环形队列具有的属性
首先，在上文中提到的队头、队尾以及容量这三个属性是必不可少的；除此之外，还需要：
- 队列长度的属性，因为队列的实际长度可能并不会达到队列容量的大小
- 队列中用来存放元素的数组（为什么是？如果说队列与 JS 中的哪一种数据类型最相似的话，那数组肯定是最好的答案）
环形队列具有的方法
- 将元素插入队尾的方法
- 将队头移出队列的方法
- 清空队列的方法
- 判断队列是否已满（如果已满，则不能再插入元素）
- 判断队列是否为空（如果为空，则不能移除元素）
- 遍历所有元素的方法
- ……（你还可以根据你的实际需要增加方法，如定时从队列中执行任务、增加任务等）
代码实现
// 环形队列
class CircleQueue {
constructor (capacity = 0) {
this.capacity = capacity // 容量
this.clean()
}
// 清空队列
clean () {
this.head = 0 // 队头
this.tail = 0 // 队尾
this.length = 0 // 队列长度
this.queue = []
}
// 将元素添加到队尾
push (element) {
// 判断队列是否已满
// 如果已满则返回 false
if (this.isFull()) return false
// 将元素添加进队尾
this.queue[this.tail] = element
this.length++
// 修改队尾
// 先将原队尾+1并对容量取余，防止队尾超出数组长度，实现环形队列的队尾
this.tail = ++this.tail % this.capacity
return this.length
}
// 将元素移出队列
shift () {
// 判断队列是否为空
// 如果为空则返回
if (this.isEmpty()) return
// 获取对头并将队头移除(置空)
let temp = this.queue[this.head]
this.queue[this.head] = null
this.length--
// 修改队头
// 先将原队头+1并对容量取余，防止队头超出数组长度，实现环形队列的队头
this.head = ++this.head % this.capacity
return temp
}
// 判断是否已满
isFull () {
if (this.length === this.capacity) return true
return false
}
// 判断是否为空
isEmpty () {
if (this.length === 0) return true
return false
}
// 遍历所有元素
travel (cb) {
for (let i = this.head; i < this.length + this.head; i++) {
cb && cb(this.queue[i % this.capacity])
}
}
}
队列在前端中的应用
我们知道前端中的任务执行就是通过队列的方式进行的，那队列在前端中还能用来干嘛呢？下面就是一个实际的例子：
通过一个专门用来存放请求的队列，实现请求发起的前后顺序（先进入的先发起）及当前页面中同时发起请求的数量（进入队列的队列在发起的同时移出，请求结束后向队列中添加下一个请求），甚至可以通过队列实现请求的自动发起（这就需要对 demo 中的代码进行修改从而实现想要的功能）。
至于队列的其他应用，就需要我们在实际工作中去发掘啦！
扫码关注微信公众号【前端程序员的斜杠青年进化录】
微信扫码，给我赞赏一下~
网友评论