队列

什么是队列

一个先进先出的数据结构,和栈很像

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

什么场景用队列

• 所有先进先出的场景，如： 食堂排队打饭，JS异步中的任务队列，计算最近请求次数

计算最近请求次数

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

• 时间复杂度: O(n)
• 空间复杂度: O(n)

JS异步中的任务队列

// 2, 1
setTimeout(()=>{
    console.log(1)
},0)
console.log(2)