队列

队列是一个先进先出的数据结构。

JS模拟队列

虽然JavaScript中没有队列，但是我们可以用数组来实现队列的功能。

	// 用数组来模拟队列
	const queue = [];
	// 入队
	queue.push(0);
	queue.push(1);
	queue.push(2);
	// 出队
	const item0 = queue.shift();
	const item1 = queue.shift();
	const item2 = queue.shift();

入队出队过程

入队过程

执行第4行代码，将0入队。

执行第5行代码，将1入队。

执行第6行代码，将2入队。

出队过程

执行第8行代码，将0出栈。

执行第9行代码，将1出栈。 执行第10行代码，将2出栈。

队列的应用

有先进先出特点的问题，都可以尝试用队列来解决。

例：计算最近请求次数（leetcode:933）

思路

有新请求就入队，超时就出队；

最后队列的长度就是最近的请求次数；

代码

var RecentCounter = function() {
    // 在构造函数中将队列挂载到this上
    this.q = [];
};

RecentCounter.prototype.ping = function(t) {
    // 将新请求入队
    this.q.push(t);
    // 超时出队
    while(this.q[0] < t - 3000){
        this.q.shift();
    }
    return this.q.length;
};