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)。

關于JavaScript中怎么實現一個隊列數據結構就分享到這里了，希望以上內容可以對大家有一定的幫助，可以學到更多知識。如果覺得文章不錯，可以把它分享出去讓更多的人看到。