亲宝软件园·资讯

展开

JS队列数据结构

​ 一碗周​ 人气:0

写在前面:

在上一篇文章中介绍了这个数据结构,这篇文章介绍一下队列。

什么是队列?

队列是一种先进先出的数据结构,队列中允许两种基础操作,也就是插入删除,也就是入队出队;我们将队列中允许插入的一端称为队尾、允许删除的一端称为队头

如下图展示了栈这个数据结构:

JavaScript中的队列

JavaScript并没有队列这个数据类型,但是可以通过数组进行模拟,而且数组中提供的push()shift()选项,正好实现先入后出的的操作,

示例代码如下:

const queue = []

// 入队
stack.push(1)
stack.push(2)
// 出队
const v1 = stack.shift() // 1
const v2 = stack.shift() // 2

JavaScript中的应用场景

队列和栈一样,是算法和程序中最常用的辅助结构,其的应用十分广泛,比如以下场景:

最近的请求次数

现在我们来做一个力扣的题来熟悉一下队列这个数据结构,这个题是【933. 最近的请求次数】,主要题目描述是写一个 **** 类来计算特定时间范围内最近的请求。

解题思路如下:

实现代码如下:

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

补充

概念和结构:

队列的操作:队列有五种常用操作,分别为:

JS实现:

JS里面的队列结构也是通过数组(Array)来实现的。

function Queue(){
    //私有变量不被外界获取
    let queue = [];
    //入队
    this.enqueue = function(element){
        queue.push(element);
    }
    //出队
    this.dequeue = function(){
        return queue.shift();
    }
    //检查队头元素
    this.front = function(){
        return queue[0];
    }
    //检查队列是否为空
    this.isEmpty = function(){
        return queue.length === 0;
    }
    //获取队列长度
    this.size = function(){
        return queue.length;
    }
}

总结

文本介绍了什么是队列以及JavaScript中可以使用数组模拟队列,在最后还讲解一个力扣中的算法题目。

加载全部内容

相关教程
猜你喜欢
用户评论