• 是一个先进先出的数据结构。
  • javascript中没有队列这个数据结构，但是可以用Array实现队列的所有功能。
  1. const queue = [];
  2. queue.push(1);
  3. queue.push(2);
  4. const item1 = queue.shift();
  5. const item2 = queue.shift();

什么场景使用队列？

  • 需要先进先出的场景。
  • 比如：食堂排队打饭，JS异步任务中的任务队列、计算最近请求次数。

JS异步任务中的任务队列

  • JS是单线程，无法同时处理异步中的并发任务。
  • 使用任务队列先后处理异步任务。

队列 - 图1

异步面试题

  1. setTimeout(()=> console.log(1),0);
  2. console.log(2)

如果有异步任务，异步任务会丢给WebAPIs执行，WebAPIs中的异步任务执行完后的回调函数的js代码放到callback queue。任务队列中前面的事件执行完了，那么这个新的js代码会继续放到js引擎中执行。如果回调函数还有异步任务就继续循环执行。

面试题解析：
刚执行的时候，会有一个主事件放到任务队列中，然后js引擎会从任务队列中拿到这个主事件执行，执行到setTimeout时，发现这是一个异步任务，就将其交给webAPIs执行，它会继续执行后面的代码。webAPIs在0ms执行完之后的回调函数放到任务队列中，但是发现还有任务队列中还有一个事件未执行完，等console.log(2)打印完之后再执行console.log(1)。

计算最近请求次数

  1. 输入：inputs = [[],[1],[100],[3001],[3002]]
  2. 输出：[null,1,2,3,3]
  • 有新请求就入队，3000ms前发出的请求出队。
  • 队列的长度就是最近请求次数。

leetcode: 933 最近的请求次数.
解题思路：

  • 越早发出的请求越早不在最近3000ms内的请求里。
  • 满足先进先出，考虑使用队列。

解题步骤：

  • 有新请求就入队，3000ms前发出的请求出队。
  • 队列长度就是最近请求次数。 ```javascript var RecentCounter = function() { //创建一个队列 this.q = []; }

RecentCounter.prototype.ping = function(t) { //请求入队 this.q.push(t);

  1.   //3000ms前发出的请求出队。要大于t-3000的差值，才符合在3000ms内，否则出队。
  2. while(this.q[0] < t - 3000) {
  3.     this.q.shift()
  4. }
  6.   // 最近请求次数
  7. return this.q.length;

} ``` 时间复杂度：O(n)
空间复杂度： O(n)

这里的 t 就是一个单纯的数字，不是数组或其他格式
题目的实际意思，就是说 [[],[1],[100],[3001],[3002]] 中的数字，代表发送请求的时间节点，这里的每个数字都会调用一次 ping 函数，用来返回包括当前在内的前 3000 毫秒中总共有几个请求（也就是数组元素的个数）。比如 3001 之前有 1 和 100，所以返回值就是 3，3002 之前有 100 和 3001，也返回 3。仅此而已。用队列保留差距在 3000 以内的数组元素，即可得出总数。

链接：https://leetcode-cn.com/problems/number-of-recent-calls/solution/shuo-shi-hua-ti-hen-jian-dan-dan-miao-shu-tai-nan-/

总结

  1. 队列是一个先进先出的数据结构。
  2. javascript中没有队列这个数据结构，但是可以用Array实现队列的所有功能。
  3. 队列常用操作：push、shift、queue[0]

素因子的定义：对于一个数n来说，将它的因子拆到若干个素数相乘，这些素数被称为n的素因子。
比如 12可以被拆为2 6
6不是质数，可以继续拆为2*3
所以最后12的素因子就是 2, 3（不计重复元素）