JavaScript如何實現一個隊列數據結構

本文小編為大家詳細介紹“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如何實現一個隊列數據結構”文章已經介紹完畢，想要掌握這篇文章的知識點還需要大家自己動手實踐使用過才能領會，如果想了解更多相關內容的文章，歡迎關注億速云行業資訊頻道。