JavaScript队列数据结构详解
作者:??一碗周? 时间:2024-05-02 16:19:39
写在前面:
在上一篇文章中介绍了栈这个数据结构,这篇文章介绍一下队列。
什么是队列?
队列是一种先进先出的数据结构,队列中允许两种基础操作,也就是插入和删除,也就是入队和出队;我们将队列中允许插入的一端称为队尾、允许删除的一端称为队头;
如下图展示了栈这个数据结构:
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. 最近的请求次数】,主要题目描述是写一个 **** 类来计算特定时间范围内最近的请求。
解题思路如下:
在类中创建一个队列,用于保存最近请求;
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()
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;
}
}
来源:https://juejin.cn/user/3350967174838701/posts
![](/images/zang.png)
![](/images/jiucuo.png)
猜你喜欢
14 个Python小游戏 源码分享
![](https://img.aspxhome.com/file/2023/9/76079_0s.gif)
详解Python中的装饰器、闭包和functools的教程
MySql忘记密码修改方式适应5.7以上版本
去掉CSS赘余代码,CSS可以更简洁
浅谈GO中的Channel以及死锁的造成
![](https://img.aspxhome.com/file/2023/4/134364_0s.jpg)
Spark中的数据读取保存和累加器实例详解
Python运算符重载的简单实例代码
用openCV和Python 实现图片对比,并标识出不同点的方式
![](https://img.aspxhome.com/file/2023/2/89352_0s.jpg)
C++/Php/Python/Shell 程序按行读取文件或者控制台的实现
PHP curl get post 请求的封装函数示例【get、post、put、delete等请求类型】
pytorch中图像的数据格式实例
Gradio机器学习模型快速部署工具应用分享
![](https://img.aspxhome.com/file/2023/6/62846_0s.jpg)
SQL中distinct的用法(四种示例分析)
![](https://img.aspxhome.com/file/2023/8/125688_0s.png)
pytorch finetuning 自己的图片进行训练操作
![](https://img.aspxhome.com/file/2023/2/67792_0s.png)
selenium与xpath之获取指定位置的元素的实现
![](https://img.aspxhome.com/file/2023/8/134528_0s.jpg)
初探TensorFLow从文件读取图片的四种方式
Python 中 Meta Classes详解
详解Python NumPy中矩阵和通用函数的使用
![](https://img.aspxhome.com/file/2023/0/86200_0s.png)
用python建立两个Y轴的XY曲线图方法
![](https://img.aspxhome.com/file/2023/0/100850_0s.jpg)