JavaScript队列和双端队列
web前端开发
共 3684字,需浏览 8分钟
· 2021-03-11
队列
创建队列
class Queue {
constructor() {
this.count = 0;
this.lowestCount = 0;//追踪队列的第一个元素
this.items = {};
}
向队列添加元素
enqueue(element) {
this.items[this.count] = element;
this.count++;
}
细节就是要注意到队列只能在尾部添加元素
检查队列是否为空并获取它的长度
size() {
return this.count - this.lowestCount;
};
isEmpty() {
return this.size() === 0;
};
从队列移除元素
dequeue() {
//判断是否为空
if (this.isEmpty()) {
return undefined;
}
const result = this.items[this.lowestCount];
delete this.items[this.lowestCount];
this.lowestCount++;
return result;
}
查看队列头元素
peek() {
if (this.isEmpty()) {
return undefined;
}
return this.items[this.lowestCount];
}
清空队列
clear() {
this.items = {};
this.count = 0;
this.lowestCount = 0;
}
创建toString方法
toString() {
if (this.isEmpty()) {
return '';
}
let objstring = `${this.items[this.lowestCount]}`;
for (let i = this.lowestCount + 1; i < this.count; i++) {
objstring = `${objString},${this.items[i]}`;
}
return objString;
}
好的,我们的队列到此就创建完毕了。但是,有些小伙伴就有疑问了,还是排队情景,假如我已经离开售票厅了,但是我还想再问些简单问题,直接到前台询问,这就是队首添加元素了,还有队尾的人突然有事离开了,这也是删除元素操作呀,那这个用队列怎么实现。
恩 ,我们的前辈就提出了双端队列,允许用户在队首进行添加和删除元素的操作,队尾也是一样。
双端队列
创建双端队列
class Deque {
constructor() {
this.count = 0;
this.lowestCount = 0;
this.items = {};
}
添加操作
队首添加元素
addFront(element) {
if (this.isEmpty()) {//空队列
this.addBack(element);
} else if (this.lowestCount > 0) {//之前被删除,重新添加
this.lowestCount--;
this.items[this.lowestCount] = element;
} else {
for (let i = this.count; i > 0; i--) {
this.items[i] = this.items[i - 1];
}
this.count++;
this.items[0] = element;
}
}
队尾添加元素
addBack(element) {
this.items[this.count] = element;
this.count++;
}
删除操作
队首删除元素
removeFront() {
if (this.isEmpty()) {
return undefined;
}
const result = this.items[this.lowestCount];
delete this.items[this.lowestCount];
this.lowestCount++;
return result;
}
队尾删除元素
removeBack() {
if (this.isEmpty()) {
return undefined;
}
this.count--;
const result = this.items[this.count];
delete this.items[this.count];
return result;
}
查询操作
返回队首元素
peekFront() {
if (this.isEmpty()) {
return undefined;
}
return this.items[this.lowestCount];
}
返回队尾元素
peekBack() {
if (this.isEmpty()) {
return undefined;
}
return this.items[this.count - 1];
}
队列的实践
模拟击鼓传花游戏
情景:孩子们围城一圈,把花传递给身边的人,某一时刻停止,花在谁手上,谁就推出。重复这个操作,剩下的最后一个人就是胜利者。
代码实现:
function hotPotato(elementsList, num) {
const queue = new Queue();
const elimitatedList = [];
for (let i = 0; i < elementsList.length; i++) {
queue.enqueue(elementsList[i]);
}
while (queue.size() > 1) {
for (let i = 0; i < num; i++) {
queue.enqueue(queue.dequeue());
}
elimitatedList.push(queue.dequeue());
}
return {
eliminated: elimitatedList,
winner: queue.dequeue()
};
}
回文检查器
检查一个词组挥着字符串是否为回文。
代码实现:
function palindromeChecker(aString) {
if (
aString === undefined
|| aString === null
|| (aString !== null && aString.length === 0)
) {
return false;
}
const deque = new Deque();
const lowerString = aString.toLocaleLowerCase().split(' ').join('');
let firstChar;
let lastChar;
for (let i = 0; i < lowerString.length; i++) {
deque.addBack(lowerString.charAt(i));
}
while (deque.size() > 1) {
firstChar = deque.removeFront();
lastChar = deque.removeBack();
if (firstChar !== lastChar) {
return false;
}
}
return true;
};
本文完〜
评论
人工智能周刊#18:微软发布手机端大模型、Llama 3 中文模型列表、苹果开源新项目、
主打尊重隐私的搜索引擎 duckduckgo,也推出了 ai chat 服务,可以使用 chatgpt 或者 claude机器学习周刊:关注 Python、机器学习、深度学习、大模型等硬核技术本期目录:1、Qwen1.5-110B:Qwen1.5 系列的首个千亿参数开源模型2、苹果开源
机器学习算法与Python实战
0
JavaScript 可视化:Promise执行彻底搞懂
深入探讨了 JavaScript 中 Promise 的内部机制,解释了它们如何使异步任务以非阻塞方式执行,并展示了 Promise 的创建、状态变化以及与事件循环的关系。正文从这开始~~JavaScript 中的 Promise 一开始可能会让人感到有些难以理解,但是如果我们能够理解其内部的工作原
高级前端进阶
0
Open-Sora全面开源升级:支持16s视频生成和720p分辨率
机器之心发布 机器之心编辑部Open-Sora 在开源社区悄悄更新了,现在单镜头支持长达16秒的视频生成,分辨率最高可达720p,并且可以处理任何宽高比的文本到图像、文本到视频、图像到视频、视频到视频和无限长视频的生成需求。我们来试试效果。生成个横屏圣诞雪景,发b站再生成个竖屏,发抖音还能
机器学习算法与Python实战
0
聊一聊我最关注的9个CV、SLAM、自动驾驶和AI圈子!
随着计算机视觉(2D/3D)、SLAM、自动驾驶、AI技术的快速迭代更新,可落地的技术也成为人们争先学习的重点。这使得从业者对于最前沿技术的获取能力变得至关重要。微信公众号便是一个非常有效的前沿信息分享平台。这里给大家推荐9个最常打开的计算机视觉、自动驾驶、SLAM、机器学习和AI方向的优质公众号平
3D视觉工坊
0
文本嵌入、文本分类和语义搜索
在实践中使用大型语言模型(LLM)中,RAG 的一个关键部分是使用文本嵌入从知识库中自动检索相关信息。在这里,我将更深入地讨论文本嵌入,并分享两个简单(但功能强大)的应用:文本分类和语义搜索。ChatGPT 吸引了全世界对人工智能及其潜力的想象。ChatGPT 的聊天界面是这一影响的关键因素,它使人
大邓和他的Python
0
一站式解决方案:基于 Arthas 实现服务发现和权限控制
来源:juejin.cn/post/7281849496983994383👉 欢迎加入小哈的星球 ,你将获得: 专属的项目实战 / Java 学习路线 / 一对一提问 / 学习打卡 / 赠书福利全栈前后端分离博客项目 2.0 版本完结啦, 演示链接
小哈学Java
0
JavaScript 可视化:Promise执行彻底搞懂
大厂技术 高级前端 Node进阶点击上方 程序员成长指北,关注公众号回复1,加入高级Node交流群深入探讨了 JavaScript 中 Promise 的内部机制,解释了它们如何使异步任务以非阻塞方式执行,并展示了 Promise 的创建、状态变
程序员成长指北
2
互联网晚报 | 大麦网已退款凤凰传奇演唱会“柱子票”;钟薛高再成被执行人;iPhone 16或取消实体音量键和电源键
大麦网回应凤凰传奇演唱会买到“柱子票”:已退票退款据报道,凤凰传奇2024巡回演唱会常州站演出结束的第二天,有网友称自己在大麦网买到“柱子票”,因为观看效果不佳,要求退款被拒。23日,记者从涉事网友处了解到,大麦方面给出了退款建议,但被其拒绝,“我希望平台退款加赔偿,并重视屡次出现的‘柱子票’问题。
产品刘
0