本篇文章可以收获的知识：

  • 什么是队列
  • 队列的常用操作
  • 队列的使用场景
  • 一道LeetCode算法题巩固队列
  • 如何分析时间复杂度和空间复杂度

什么是队列

队列是一个先进先出的数据结构，JavaScirpt中没有队列，但可以使用Array实现队列的所有功能。

队列的常用操作

const queue = [] // 队列
queue.push(1) // 入队（enqueue）
queue.shift() // 出队（dequeue）

队列的使用场景

  • 食堂排队打饭

    食堂排队打饭都不陌生，先排队的学生可以先打到饭，符合队列的特点。

  • JavaScript异步任务队列

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

  • 计算最近请求次数

    一个请求队列[[], [1], [100], [3001], [3002]],计算[t-3000, t]的请求次数，首先新请求t先入队，不在这个区间的出队。后面也会通过一道LeetCode算法题巩固队列的知识。

遇到这些相似的问题，都可以优先考虑使用队列来解决问题。

LeetCode算法题：题号933，最近的请求次数

解题思路：

  • 越早发出的请求，越靠前
  • 符合先进先出的特点，考虑使用队列。

解题步骤：

  • 新请求，入队
  • 不在[t - 3000, t]区间内的成员出队
  • 最后队列的长度就是最近的请求次数

代码实现：

var RecentCounter = function() {
  this.q = [];
};

/** 
 * @param {number} t
 * @return {number}
 */
RecentCounter.prototype.ping = function(t) {
  this.q.push(t);
  while(t - 3000 > this.q[0]) {
    this.q.shift();
  }
  return this.q.length;
};

/**
 * Your RecentCounter object will be instantiated and called as such:
 * var obj = new RecentCounter()
 * var param_1 = obj.ping(t)
 */

分析时间复杂度和空间复杂度

因为代码中有个while循环体，循环的次数最大是ping的次数，所以时间复杂度是O(n)，n是ping的次数。

因为代码中用到了队列，最大的长度是3000，所以空间复杂度是O(n)，n最大是3000。

最后，希望读者可以通过本篇文章对队列有一定的认识和觉悟。。。。。。