前端中的数据结构——队列篇

队列是数据结构中的一种,它与实际生活中的排队相似:在一条队伍中,先来的人总是能够先得到服务,后来的人只能排在队伍末尾等候。队列也是一样,它符合先进先出 FIFO(First Input First Out)的顺序。

那队列在我们的代码中有什么样的作用呢?还是以排队为例,当我们需要做一个排队系统时,就可以用到了,具体如下:

某个商品销售异常火爆,为了保证系统的稳定,所以限制购买的用户同时最多只能有100人,每当一个用户购买成功,下一个用户才可以进入购买者的队伍。这样既保证系统稳定,又提高了用户的购买体验(在等待期间可以提醒用户前面还有多少人)。

那队列在前端中有哪些可以使用到的地方呢?这个我们最后再说,先来看队列的 js 实现。

队列的类型

队列有两种类型:一种是和日常排队类似的队列,叫做普通队列;另一种叫做环形队列。

对于一个队列来说,有队头和队尾,以及容量。

从上图可以看出来,普通队列的队头和队尾是分开的,当队头的元素离开队列后,下一个元素就会成为队头,而新加入的元素会跟随在原本的队尾之后,成为新的队尾。

而对于环形队列来说,当只有一个元素时,队头队尾是同一个元素;当队列容量已满时,队头和队尾是连接在一起的;当队头的元素离开后,下一个元素会成为队头,而新的元素则会插入原本队头的位置成为新的队尾。

在容量确定的情况下,普通队列前面的元素离开后,对应的内存就会被空置,而在环形队列中,前面的元素离开,新的元素就会占据原来的内存。相比之下,就容量而言,环形队列具有更高的内存利用率,可以减小内存的开支消耗。

实现一个环形队列环形队列具有的属性

首先,在上文中提到的队头、队尾以及容量这三个属性是必不可少的;除此之外,还需要:

队列长度的属性,因为队列的实际长度可能并不会达到队列容量的大小

队列中用来存放元素的数组(为什么是?如果说队列与 JS 中的哪一种数据类型最相似的话,那数组肯定是最好的答案)

环形队列具有的方法

将元素插入队尾的方法

将队头移出队列的方法

清空队列的方法

判断队列是否已满(如果已满,则不能再插入元素)

判断队列是否为空(如果为空,则不能移除元素)

遍历所有元素的方法

……(你还可以根据你的实际需要增加方法,如定时从队列中执行任务、增加任务等)

代码实现

Demo on github

队列在前端中的应用

我们知道前端中的任务执行就是通过队列的方式进行的,那队列在前端中还能用来干嘛呢?下面就是一个实际的例子:

通过一个专门用来存放请求的队列,实现请求发起的前后顺序(先进入的先发起)及当前页面中同时发起请求的数量(进入队列的队列在发起的同时移出,请求结束后向队列中添加下一个请求),甚至可以通过队列实现请求的自动发起(这就需要对 demo 中的代码进行修改从而实现想要的功能)。

至于队列的其他应用,就需要我们在实际工作中去发掘啦!

  • 发表于:
  • 原文链接:http://kuaibao.qq.com/s/20180107G0JGE900?refer=cp_1026

扫码关注云+社区