JavaScript中如何实现队列结构
小编给大家分享一下JavaScript中如何实现队列结构,相信大部分人都还不怎么了解,因此分享这篇文章给大家参考一下,希望大家阅读完这篇文章后大有收获,下面让我们一起去了解一下吧!
JavaScript可以做什么
1.可以使网页具有交互性,例如响应用户点击,给用户提供更好的体验。 2.可以处理表单,检验用户的输入,并提供及时反馈节省用户时间。 3.可以根据用户的操作,动态的创建页面。 4使用JavaScript可以通过设置cookie存储在浏览器上的一些临时信息。
1. 队列数据结构
队列是一种“先入先出”(FIFO)数据结构的类型。第一个入队项目(输入)是第一个出队(输出)。
队列有2个指针:头和尾。队列中的最早排队的项目是在头部,而最新排队的项目在队列尾部。
队列就像我们在地铁排队,靠近车门处的乘客位于队伍的头部,刚进入队伍的乘客位于队伍的尾部。
从更高的角度来看,队列是一种数据结构,可以让我们按照入库的顺序依次处理数据的每一项。
2. 队列的操作
队列支持 2 个主要操作:入队(enqueue)和出队(dequeue),另外还有 peek 和 length 操作。
2.1 入队操作
入队操作在队列的尾部插入项目,使其成为队列的队尾。
上图中的入队操作在队尾插入了 8
,之后 8
成为队列的队尾。
queue.enqueue(8);
2.2 出队操作
出队操作取出队列中第一个项目,此时队列中的下一个项目成为队首。
在上图中,出队操作返回项目7
并从队列中删除。 出队之后之后,项目 2
成为新的队首。
queue.dequeue();//=>7
2.3 Peek 操作
Peek 操作读取队首的项目,但是不改变队列。
上图中 7
是队首。 peek 操作只需返回队首 7
但是不修改队列。
queue.peek();//=>7
2.4 length
length 操作返回队列中包含项目的数量。
上图中的队列有 4 项:4
、6
、2
和。7
。结果队列长度为 4
。
queue.length;//=>4
2.5 队列操作的时间复杂度
关于队列所有操作的重点:enqueue,dequeue,peek 和 length 必须以常数时间复杂度 O(1)
执行。
常数时间复杂度 O(1)
意味着无论队列大小如何(不管是有 10 个还是 100 万个项目),这些操作都必须在相对一致的时间内执行。
3. 用 JavaScript 实现队列
来看一下怎样在保证所有操作必须以常数时间复杂度O(1)
要求实现队列这种数据结构。
classQueue{ constructor(){ this.items={}; this.headIndex=0; this.tailIndex=0; } enqueue(item){ this.items[this.tailIndex]=item; this.tailIndex++; } dequeue(){ constitem=this.items[this.headIndex]; deletethis.items[this.headIndex]; this.headIndex++; returnitem; } peek(){ returnthis.items[this.headIndex]; } getlength(){ returnthis.tailIndex-this.headIndex; } } constqueue=newQueue(); queue.enqueue(7); queue.enqueue(2); queue.enqueue(6); queue.enqueue(4); queue.dequeue();//=>7 queue.peek();//=>2 queue.length;//=>3
const queue = new Queue()
是创建队列的实例。
queue.enqueue(7)
方法将 7
存入队列中。
queue.dequeue()
从队列中取出一个头部项目,而 queue.peek()
只读队首项。
最后的 Queue.Length
显示队列中还有多少个项目。
关于实现:在 Queue
类中,普通对象 this.Items
将队列的项目通过数值索引保持。 队首项的索引由 Where.HeadInex
跟踪,队尾项由 this.tailIndex
跟踪。
队列方法的复杂度
在 Queue
的 queue()
、 dequeue()
、 peek()
和 length()
方法中存在:
属性访问器(如:
this.items[this.headIndex]
),执行算数操作(如:
this.headidex++
)
这些方法的时间复杂度是恒定的时间 O(1)
。
4. 总结
队列是一种遵循先入先出(FIFO)规则的的数据结构。
队列有 2 个主要操作:入队和出队。 另外,队列可以有辅助操作,例如 peek 和 length。
所有队列操作都必须以常数时间 O(1)
执行。
以上是“JavaScript中如何实现队列结构”这篇文章的所有内容,感谢各位的阅读!相信大家都有了一定的了解,希望分享的内容对大家有所帮助,如果还想学习更多知识,欢迎关注恰卡编程网行业资讯频道!
推荐阅读
-
WebStorm 与 VS Code 对比:JavaScript 开发该如何选择 IDE?
-
WebStorm 与 VS Code 对比:JavaScript 开发工具选型分析
-
JavaScript闭包用多会造成内存泄露吗
JavaScript闭包用多会造成内存泄露吗今天小编给大家分享一下...
-
javascript中文乱码如何解决
javascript中文乱码如何解决本篇内容介绍了“javascr...
-
PHP学习第十五天——JavaScript入门DOM对象:二
-
Node.js基本内容和知识点
简单的说node.js就是运行在服务端的JavaScript,起初段定位是后端开发语言,由于技术的不够成熟,一般小型项目...
-
PHP与Node.js:一个史诗般开发者的分享
-
JavaScript 中 find() 和 filter() 方法的区别
JavaScript在ES6上有很多数组方法,每种方法都有独特的用途和好处。在开发应用程序时,大多使用数组方法来获...
-
js怎么跟php结合使用
-
简单说说Node.js和JavaScript
Node.js是一个开源和跨平台的JavaScript运行时环境,在浏览器之外运行V8JavaScript引擎(...