作为一个优秀的程序猿需要具有知识的广度。首先是要了解你选择的编程语言。
然而在熟悉了编程语言之后,你还必须了解如何根据任务轻松且有效地操纵数据。这就是数据结构的用武之地。
在本文中,我将描述队列数据这个结构:它都有哪些操作以及在 JavaScript 中怎样实现。
如果你喜欢四处旅行,肯定在火车站经历过检票这道手续。如果有很多人要坐火车,那么很自然地会形成一个队列。刚进入车站的人加入队列。另一边刚刚通过检票的人从队列中走出。这就是队列的一个例子,与队列数据结构的操作方式相同。
队列是一种遵循先入先出(FIFO)规则的数据结构。第一个进入队列中的项目(输入)是第一个出队(输出)的。
队列有2个指针:队首和队尾。最先进入队列进行排队的项目位于队首,而最后进入队列的项目位于队尾。
回顾车站的例子,第一个检票的是在队列的队首。刚进入队列的人在队尾。
队列数据结构
从更高的层面来看,队列是一种允许你按照先后顺序处理项目的数据结构。
队列支持 2 个主要操作:入队(enqueue)和出队(dequeue),另外还有 peek 和 length 操作。
入队操作在队列的尾部插入项目,使其成为队列的队尾。
入队操作
上图中的入队操作在队尾插入了 8,之后 8 成为队列的队尾。
- queue.enqueue(8);
出队操作取出队列中第一个项目,此时队列中的下一个项目成为队首。
出队操作
在上图中,出队操作返回项目7并从队列中删除。出队之后之后,项目 2 成为新的队首。
- queue.dequeue(); // => 7
Peek 操作读取队首的项目,但是不改变队列。
Peek 操作
上图中 7 是队首。peek 操作只需返回队首 7 但是不修改队列。
- queue.peek(); // => 7
length 操作返回队列中包含项目的数量。
Length 操作
上图中的队列有 4 项:4、6、2 和。7。结果队列长度为 4。
- queue.length; // => 4
关于队列所有操作的重点:enqueue,dequeue,peek 和 length 必须以常数时间复杂度 O(1) 执行。
常数时间复杂度 O(1) 意味着无论队列大小如何(不管是有 10 个还是 100 万个项目),这些操作都必须在相对一致的时间内执行。
来看一下怎样在保证所有操作必须以常数时间复杂度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(); // => 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() 方法中存在:
这些方法的时间复杂度是恒定的时间 O(1)。
队列是一种遵循先入先出(FIFO)规则的的数据结构。
队列有 2 个主要操作:入队和出队。另外,队列可以有辅助操作,例如 peek 和 length。
所有队列操作都必须以常数时间 O(1) 执行。
挑战一下:改进 dequeue() 和 peek() 方法,当在空队列上执行时会抛出错误。
在任何数据科学应用中,观察偏差和亚组差异很容易产生统计悖论。因此,忽略这些...
1.我对着同桌大喊我同桌是猪他对我大喊你同桌才是猪 2.上课时间就像南孚电池,...
在家学解决方案基于阿里云平台 可同时支撑海量学生同时线上授课 满足各省中小学...
数据量的增长,让人类文明步入大数据时代。大数据,顾名思义,大量的数据。从数...
时间回到2009年 那年 刚刚成立的阿里云正处于风口浪尖 在其他互联网大佬口中 要...
目录 一、分支规约 二、版本号规约 2.1 主版本号 首位版本号 2.2 次版本号 迭代...
你是否曾经被大量的python模块压垮过?你是否曾经在为一个特定的项目挑选一个时陷...
作者 齐木 用关系型数据库一定多多少少会用到 Join 操作。常见的 Join 有 Nested...
搞数据的都知道,阿里发明了数据中台,然后中台这个概念就马上成为了国内大多数...
作为近年来最受关注的新零售行业独角兽 KK集团已完成一期门店系统上云 记者日前...