队列

简介

• 一个先进先出的数据结构

• JavaScript 中没有队列，但可以用 Array 实现队列的所有功能。

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

应用场景

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

最近的请求次数

LeetCode：933. 最近的请求次数

• 解题思路

越早发出的请求越早不在最近 3000ms 内的请求里

满足先进先出，考虑用队列

• 解题步骤

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

js

/*
 * @lc app=leetcode.cn id=933 lang=javascript
 *
 * [933] 最近的请求次数
 */

// @lc code=start

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

/**
 * @param {number} t
 * @return {number}
 */
RecentCounter.prototype.ping = function (t) {
  // 先进先出 用队列！
  this.q.push(t)
  //    3000ms前的请求出队
  while (this.q[0] < t - 3000) {
    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)
 */
// @lc code=end

ts

/*
 * @lc app=leetcode.cn id=933 lang=typescript
 *
 * [933] 最近的请求次数
 */

// @lc code=start
class RecentCounter {
  public q: Array<number> = []
  constructor() {}

  ping(t: number): number {
    // 先进先出 用队列
    this.q.push(t)
    //    3000ms前的请求出队
    while (this.q[0] < t - 3000) {
      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)
 */
// @lc code=end

前端与队列：js 异步中的任务队列

事件循环与任务队列

!