1.队列的实现

  • 队列是一种遵从先进先出原则的有序集合
  • 添加新元素的一端称为队尾，另一端称为队首
  • JavaScript中没有队列，但可以用 Array 实现队列的所有功能

基于数组：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Queue {
  constructor() {
    // 用于存储队列数据
    this.queue = [];
    this.count = 0;
  }
  // 入队方法
  enQueue(item) {
    this.queue[this.count++] = item;
  }
  // 出队方法
  deQueue() {
    if (this.isEmpty()) {
      return;
    }
    // 删除 queue 的第一个元素，会有空值占位
    // delete this.queue[0]
    // 利用 shift() 移除数组的第一个元素
    this.count--;
    return this.queue.shift();
  }
  isEmpty() {
    return this.count === 0;
  }
  // 获取队首元素值
  top() {
    if (this.isEmpty()) {
      return;
    }
    return this.queue[0];
  }
  size() {
    return this.count;
  }
  clear() {
    // this.queue = []
    this.length = 0;
    this.count = 0;
  }
}

const q = new Queue();

基于对象：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Queue {
  constructor() {
    this.queue = {};
    this.count = 0;
    // 用于记录队首的键
    this.head = 0;
  }
  // 入队方法
  enQueue(item) {
    this.queue[this.count++] = item;
  }
  // 出队方法
  deQueue() {
    if (this.isEmpty()) {
      return;
    }
    const headData = this.queue[this.head];
    delete this.queue[this.head];
    this.head++;
    this.count--;
    return headData;
  }
  isEmpty() {
    return this.count === 0;
  }
  clear() {
    this.queue = {};
    this.count = 0;
    this.head = 0;
  }
}

const q = new Queue();

2.什么场景用队列

需要先进先出的场景

  • 食堂排队打饭、JS异步中的任务队列、计算最近请求次数

场景一：食堂排队打饭

  • 食堂只留一个窗口，学生排队打饭似春运
  • 先进先出，保证有序

场景二:JS异步中的任务队列

image

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

场景三：计算最近请求次数

image

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

3.最近的请求次数

解题思路：

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

解题步骤：

  • 有新请求就入队，3000ms前发出的请求出队
  • 队列的长度就是最近请求次数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
var RecentCounter = function() {
    this.q = [];
};

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