文章详情

短信预约-IT技能 免费直播动态提醒

请输入下面的图形验证码

提交验证

短信预约提醒成功

javascript中如何实现队列数据结构

2023-06-14 22:21

关注

这篇文章主要介绍javascript中如何实现队列数据结构,文中介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们一定要看完!

javascript是一种什么语言

javascript是一种动态类型、弱类型的语言,基于对象和事件驱动并具有相对安全性并广泛用于客户端网页开发的脚本语言,同时也是一种广泛用于客户端Web开发的脚本语言。它主要用来给HTML网页添加动态功能,现在JavaScript也可被用于网络服务器,如Node.js。

1. 队列数据结构

如果你喜欢四处旅行,肯定在火车站经历过检票这道手续。如果有很多人要坐火车,那么很自然地会形成一个队列。刚进入车站的人加入队列。另一边刚刚通过检票的人从队列中走出。这就是队列的一个例子,与队列数据结构的操作方式相同。

队列是一种遵循先入先出(FIFO)规则的数据结构。第一个进入队列中的项目(输入)是第一个出队(输出)的。

队列有2个指针:队首和队尾。最先进入队列进行排队的项目位于队首,而最后进入队列的项目位于队尾

回顾车站的例子,第一个检票的是在队列的队首。刚进入队列的人在队尾。

javascript中如何实现队列数据结构

从更高的层面来看,队列是一种允许你按照先后顺序处理项目的数据结构。

2. 队列的操作

队列支持 2 个主要操作:入队(enqueue)出队(dequeue),另外还有 peek 和 length 操作。

2.1 入队操作

入队操作在队列的尾部插入项目,使其成为队列的队尾。

javascript中如何实现队列数据结构

上图中的入队操作在队尾插入了 8,之后 8 成为队列的队尾。

queue.enqueue(8);

2.2 出队操作

出队操作取出队列中第一个项目,此时队列中的下一个项目成为队首。

javascript中如何实现队列数据结构

在上图中,出队操作返回项目7并从队列中删除。 出队之后之后,项目 2 成为新的队首。

queue.dequeue(); // => 7

2.3 Peek 操作

Peek 操作读取队首的项目,但是不改变队列。

javascript中如何实现队列数据结构

上图中  7 是队首。 peek 操作只需返回队首 7 但是不修改队列。

queue.peek(); // => 7

2.4 length

length 操作返回队列中包含项目的数量。

javascript中如何实现队列数据结构

上图中的队列有 4 项:462 和。7。结果队列长度为 4

queue.length; // => 4

2.5 队列操作的时间复杂度

关于队列所有操作的重点:enqueue,dequeue,peek 和 length 必须以常数时间复杂度 O(1) 执行。

常数时间复杂度 O(1) 意味着无论队列大小如何(不管是有 10 个还是 100 万个项目),这些操作都必须在相对一致的时间内执行。

3. 用 JavaScript 实现队列

来看一下怎样在保证所有操作必须以常数时间复杂度O(1) 要求实现队列这种数据结构。

class Queue {  constructor() {    this.items = {};    this.headIndex = 0;    this.tailIndex = 0;  }  enqueue(item) {    this.items[this.tailIndex] = item;    this.tailIndex++;  }  dequeue() {    const item = this.items[this.headIndex];    delete this.items[this.headIndex];    this.headIndex++;    return item;  }  peek() {    return this.items[this.headIndex];  }  get length() {    return this.tailIndex - this.headIndex;  }}const queue = new Queue();queue.enqueue(7);queue.enqueue(2);queue.enqueue(6);queue.enqueue(4);queue.dequeue(); // => 7queue.peek();    // => 2queue.length;    // => 3

const queue = new Queue() 是创建队列的实例。

queue.enqueue(7) 方法将 7 存入队列中。

queue.dequeue() 从队列中取出一个头部项目,而 queue.peek() 只读队首项。

最后的 Queue.Length 显示队列中还有多少个项目。

关于实现:在 Queue 类中,普通对象  this.Items  将队列的项目通过数值索引保持。 队首项的索引由 Where.HeadInex 跟踪,队尾项由 this.tailIndex 跟踪。

队列方法的复杂度

Queuequeue()dequeue()peek()length() 方法中存在:

这些方法的时间复杂度是恒定的时间 O(1)

以上是“javascript中如何实现队列数据结构”这篇文章的所有内容,感谢各位的阅读!希望分享的内容对大家有帮助,更多相关知识,欢迎关注编程网行业资讯频道!

阅读原文内容投诉

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

软考中级精品资料免费领

  • 历年真题答案解析
  • 备考技巧名师总结
  • 高频考点精准押题
  • 2024年上半年信息系统项目管理师第二批次真题及答案解析(完整版)

    难度     813人已做
    查看
  • 【考后总结】2024年5月26日信息系统项目管理师第2批次考情分析

    难度     354人已做
    查看
  • 【考后总结】2024年5月25日信息系统项目管理师第1批次考情分析

    难度     318人已做
    查看
  • 2024年上半年软考高项第一、二批次真题考点汇总(完整版)

    难度     435人已做
    查看
  • 2024年上半年系统架构设计师考试综合知识真题

    难度     224人已做
    查看

相关文章

发现更多好内容

猜你喜欢

AI推送时光机
位置:首页-资讯-后端开发
咦!没有更多了?去看看其它编程学习网 内容吧
首页课程
资料下载
问答资讯