JS数据结构与算法入门(三) - 数据结构之“队列”

小鱼儿 2022-11-29 13:28 214阅读 0赞

## 1. 队列是什么? ##

一个先进先出的数据结构  
JS中没有队列这种数据结构, 但可以用数组实现队列的所有功能  
队列常用操作: push, shift, array\[index\]  
![队列][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4NDQ2NTQy_size_16_color_FFFFFF_t_70_pic_center]

const quene = [];
    quene.push(1);
    quene.push(2);
    const item1 = quene.shift();
    const item2 = quene.shift();

--------------------

## 2. 什么场景下用队列? ##

需要先进先出的场景  
比如: 食堂排队打饭(先进先出, 保证次序), JS异步中的任务队列(JS单线程, 无法同时处理异步中的并发任务), 算法题`计算最近请求次数`

**题号933 最近的请求次数**

解题步骤:

1.  有新请求入队, 3000ms前发生的请求出队
2.  队列的长度就是最近请求次数

文字版:  
//新建一个队列, 该队列需要在ping方法里被访问,  
//而且需要保证先后多次调用ping方法它们访问的队列都是同一个队列,  
//只需要在构造函数里面把队列挂载到this上  
//如此一来就可以在所有的类方法,也包括ping方法里访问这个队列,  
//而且可以保证它们访问的都是同一个队列, 接下来可以执行入队和出队操作.  
//每发起一次请求先要把请求入队,  
//然后把不在该时间范围内的请求踢出队 , 用while循环判断一下队头是否小于t-3000  
//假如小于t-3000, 那自然就不在范围内, 那就用shift方法踢出去  
//这样就可以把所有不在范围内的请求踢出, 然后返回队列的长度就是最终的结果

该代码里面有while循环体,所以时间复杂度是O(n), n是需要被踢出队的请求个数.  
为了计算最近请求次数, 新建了一个队列, 这个队列是个数组, 所以空间复杂度是O(n), n是队列的长度, 长度也就是最近的请求次数

代码版:

--------------------

## 3. JS异步中的任务队列? ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4NDQ2NTQy_size_16_color_FFFFFF_t_70_pic_center 1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4NDQ2NTQy_size_16_color_FFFFFF_t_70_pic_center]: /images/20221124/40e1456e4ad14dd3ba6482b554daa0b9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4NDQ2NTQy_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221124/31605f857c2748b4b5d397bf46901c57.png