如何在JavaScript中實現隊列數據結構
在了解編程語言的基礎上，你還必須了解如何組織數據，以便根據任務輕松有效地操作數據。這就是數據結構的作用。
在這篇文章中，我將描述隊列數據結構，其具有的操作以及向您展示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) 中執行。
原文：https://dmitripavlutin.com/javascript-queue/
作者：Dmitri Pavlutin
