前端常见数据结构与算法整理--队列

概念：

1. 队列是先进先出的数据结构，与栈相反。
2. JavaScript中没有自带队列这个数据结构，但可以用数组模拟

概念代码实现：

//数组模拟队列

const queue = []

queue.push(1)
//入队

queue.shift()
//出队

队列常见用途：

1. 所有需要用到先进先出特性的地方
2. JavaScript中的event loop

leetcode相关算法题：

t933. 最近的请求次数：

写一个 RecentCounter 类来计算特定时间范围内最近的请求。 请你实现 RecentCounter 类： RecentCounter() 初始化计数器，请求数为 0 。 int ping(int t) 在时间 t 添加一个新请求，其中 t 表示以毫秒为单位的某个时间，并返回过去 3000 毫秒内发生的所有请求数（包括新请求）。确切地说，返回在 [t-3000, t] 内发生的请求数。 保证 每次对 ping 的调用都使用比之前更大的 t 值。

示例：

输入： ["RecentCounter", "ping", "ping", "ping", "ping"] [[], [1], [100], [3001], [3002]]

输出： [null, 1, 2, 3, 3]

来源：力扣（LeetCode） 链接：leetcode-cn.com/problems/nu… 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路：

由于只需要取到3000ms内发送的请求，所以可以把所有数据存在队列中，让已经超过3000ms的出队，队列内只保留3000ms内的请求，即不断向空队列中推入时间t，并且每次推入计算当前t与队首的t相差是否超过3000，超过就将队首出队，最后返回这个队列的长度。

代码实现：

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
};

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