JavaScript队列数据结构详解

前言部分

继上一篇关于栈数据结构的介绍之后，本文将重点探讨队列这一数据结构。

队列的基本概念

队列遵循先进先出（FIFO）原则，支持插入和删除两种基本操作，分别称为入队和出队。允许插入数据的一端被称为队尾，而允许删除数据的一端则被称为队头。

相关示意图展示了队列的结构，具体可见下方插图。

JavaScript中的队列实现

JavaScript原生并未提供专门的队列类型，但可以利用数组进行模拟。数组提供的push()和shift()方法，恰好能够配合实现先入后出的逻辑，从而构建队列功能。

相关示例代码如下：

const queue = []

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

JavaScript中的应用场景

与栈类似，队列是算法和程序设计中极为常用的辅助结构，应用范围广泛。以下是几个典型的应用场景：

• 现实生活中的排队现象，例如食堂打饭，先到者先服务，体现了先进先出的原则。
• 银行或营业厅的叫号系统，用户需在取号机排队，随后按顺序等待叫号处理。
• JavaScript中的异步任务队列，这是队列应用的典型代表，用于管理异步操作的执行顺序。

力扣933题实战：最近的请求次数

为了深入理解队列，我们通过力扣题目【933. 最近的请求次数】进行练习。该题要求实现一个类，用于计算特定时间范围内最近的请求数量。

解题思路如下：

• 在类内部初始化一个队列，用于存储最近的请求记录。
• 每次调用ping方法时，将当前请求时间存入队列。
• 检查队头元素的时间是否早于t-3000，若符合条件则执行出队操作并继续判断；否则直接返回当前队列的长度。

具体实现代码如下：

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

补充知识

概念与结构定义：

• 队列是一种遵循先进先出（FIFO）规则的数据结构。
• 队列中第一个元素所在的位置定义为队头，最后一个元素所在的位置定义为队尾。
• 若队列中没有任何元素，则称为空队列。

队列的常用操作包括以下五种：

• 入队 enqueue(element)
• 出队 dequeue()
• 获取队头元素 front()
• 判断队列是否为空 isEmpty()
• 获取队列长度 size()

JavaScript代码实现

在JavaScript中，队列结构通常基于数组（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中通过数组模拟的实现方式，并通过力扣算法题目进行了实战演练。

关于JavaScript队列数据结构的介绍到此结束，更多相关内容欢迎查阅本站历史文章或继续阅读后续文章，感谢支持！