要成为一名优良的开发人员,须要来自多个学科的常识。
然而,在理解编程语言的根底上,你还必须理解如何组织数据,以便依据工作轻松无效地操作数据。这就是数据结构的作用。
在这篇文章中,我将形容队列数据结构,其具备的操作以及向您展现 JavaScript 中的队列实现。
1. 队列数据结构
如果你喜爱旅行(像我一样),很可能你在机场通过了办理登机手续。如果有很多旅客违心办理登机手续,天然就会在值机柜台前排起长龙。
刚进入机场并想要办理登机手续的旅客将排队进入队列,而刚刚在服务台办理了登机手续的旅客则能够来到队列。
这是队列的实在示例—队列数据结构以雷同的形式工作。
队列是一种“先入先出”(FIFO)数据结构的类型。入队(输出)的第一项是要出队(输入)的第一项。
从构造上说,一个队列有 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 队列长度
长度操作计算队列蕴含多少个我的项目。
图片中的队列有 4 个我的项目:4
、6
、2
和 7
。因而,队列长度为 4
。
queue.length; // => 4
2.5 队列操作工夫复杂度
对于所有的队列操作 –enqueue、dequeue、peek 和 length——重要的是,所有这些操作必须在恒定的工夫内 O(1)
执行。
恒定的工夫 O(1)
意味着无论队列的大小 (它能够有 10 个或 100 万个我的项目):enqueue、dequeue、peek 和 length 操作必须在绝对雷同的工夫内执行。
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(); // => 7
queue.peek(); // => 2
queue.length; // => 3
Try the demo.
const queue = new Queue()
是创立队列实例的形式。
调用 queue.enqueue(7)
办法会将我的项目 7 排队到队列中。
queue.dequeue()
从队列中去队列一个头部的我的项目,而 queue.peek()
只是 Peek 头部的我的项目。
最初,queue.length
显示队列中还有多少我的项目。
队列办法的复杂性
Queue 类的 queue()
、dequeue()
、peek()
和 length()
办法仅应用:
- 属性拜访器(例如
this.items[this.headIndex]
), - 或执行算术操作(例如
this.headIndex++
)
因而,这些办法的工夫复杂度是恒定工夫 O(1)
。
总结
队列数据结构是“先入先出”(FIFO)的一种:最早入队的项是最早出队的项。
队列有 2 个次要操作:入队和出队。另外,队列能够具备辅助操作,例如 Peek 和长度。
所有队列操作必须在恒定工夫 O(1)
中执行。