队列

1. 是什么？

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

js 代码实现

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

2. 使用场景

js 异步中的任务队列

计算最近请求次数

3. 计算最近请求次数实现 leetcode 933

请你实现 RecentCounter 类：

RecentCounter() 初始化计数器，请求数为 0 。
int ping(int t) 在时间 t 添加一个新请求，其中 t 表示以毫秒为单位的某个时间，并返回过去 3000 毫秒内发生的所有请求数（包括新请求）。确切地说，返回在 [t-3000, t] 内发生的请求数。

比如：
输入: [[], [1], [100], [3001], [3002]]
输入：[null, 1, 2, 3, 3]

第一个因为我们传了一个空数组，所以没有对应的请求数，第二个是1也就是 [1-3000, 1]，里面只有一个1，第三个[100-3000, 100]有一个1和100，第三个 [3001-3000, 3001]有1、100、3001，第四个[3002-3000, 3002]有200、3001、3002

解题思路：

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

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

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

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

因为有个while 循环所以时间复杂度是 O(n)，空间复杂度，声明了一个队列，队列的长度就是参数的长度所以也是O(n)

4. 优先队列

4.1. 是什么

• 最大优先队列，无论入队顺序如何，都是当前最大的元素优先出队
• 最小优先队列，无论入队顺序如何，都是当前最小的元素优先出队

例如有一个最大优先队列，其中的最大元素是8，那么虽然8并不是队头元素，但出队时仍然让元素8首先出队。

4.2. 实现

我们可以用最大堆来实现最大优先队列，这样，每一次入队操作就是堆的插入操作，每一次出队操作就是删除堆顶节点。

入队操作具体步骤如下：

1. 插入新节点5。

   
   

2. 新节点5“上浮”到合适位置。

出队操作具体步骤如下：

1. 让原堆顶节点10出队。

2. 把最后一个节点1替换到堆顶位置。

   
   

3. 节点1“下沉”，节点9成为新堆顶。

   
   

优先队列的入队和出队操作时间复杂度都是 O(logn)

class PriorityQueue {
  size = 0
  array = Array.from({length: 32}).fill(true)
  enQueue(key) {
    if (this.size >= this.array.length) {
      this.resize();
    }
    this.array[this.size] = key;
    this.size += 1;
    this.upAdjust();
  }
  /**出队 */
  deQueue() {
    if (this.size <= 0)  {
      throw new Error('队列为空')
    }
    // 获取堆顶元素
    let head = this.array[0];
    // 让最后一个元素移动到堆顶
    this.array[0] = this.array[this.array.length -1];
    this.downAdjust();
    return head;
  }
  /**上浮 */
  upAdjust() {
    let childIndex = this.size - 1;
    let parentIndex = Math.ceil((childIndex - 1) / 2);
    let temp = this.array[childIndex];
    // 如果当前入队的节点的索引大于0并且值大于父节点就交换位置
    while (childIndex > 0 && temp > this.array[parentIndex]) {
      this.array[childIndex] = this.array[parentIndex];
      childIndex = parentIndex;
      parentIndex = Math.floor(parentIndex / 2);
    }
    this.array[childIndex] = temp;
  }
  downAdjust() {
    let parentIndex = 0;
    let temp = this.array[parentIndex];
    let childIndex = 1;
    while (childIndex < this.size) {
      if (childIndex + 1 < this.size && this.array[childIndex + 1] > this.array[childIndex]) {
        childIndex += 1;
      }
      if (temp >= this.array[childIndex]) break;
      this.array[parentIndex] = this.array[childIndex];
      parentIndex = childIndex;
      childIndex = 2 * childIndex + 1;
    }
    this.array[parentIndex] = temp;
  }
  resize() {
    this.array = [...this.array, Array.from({length: this.size}).fill(true)]
  }
}

var priorityQueue = new PriorityQueue();
priorityQueue.enQueue(3);
console.log(priorityQueue.array)
priorityQueue.enQueue(5);
console.log(priorityQueue.array)
priorityQueue.enQueue(10);
console.log(priorityQueue.array)
priorityQueue.enQueue(2);
console.log(priorityQueue.array)
priorityQueue.enQueue(7);