詳解佇列資料結構，js中怎麼實作？

身為優秀的程式猿需要具有知識的廣度。首先是要了解你選擇的程式語言。如果你正在閱讀這篇文章，最有可能使用 JavaScript。

然而在熟悉了程式語言之後，你還必須了解如何根據任務輕鬆且有效地操縱資料。這就是資料結構的用武之地。

在本文中，我將描述佇列資料這個結構：它都有哪些操作以及在 JavaScript 中如何實作。

1. 隊列資料結構

如果你喜歡四處旅行，肯定在火車站經歷過檢票這道手續。如果有很多人要坐火車，那麼很自然地會形成一個隊列。剛進入車站的人加入隊列。另一邊剛剛通過檢票的人從隊列中走出。這就是佇列的一個例子，與佇列資料結構的操作方式相同。

佇列是一種遵循先入先出（FIFO）規則的資料結構。第一個進入佇列中的項目（輸入）是第一個出隊（輸出）的。

隊列有2個指針：隊首和隊尾。最先進入隊列進行排隊的項目位於隊首，而最後進入隊列的項目位於隊尾。

回顧車站的例子，第一個檢票的是在隊列的隊首。剛進入隊列的人在隊尾。

從更高的層次來看，佇列是一種允許你按照先後順序處理專案的資料結構。

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 length

length 操作傳回佇列中包含項目的數量。

上圖中的佇列有 4 項：4、6、2 和。 7。結果佇列長度為 4。

queue.length; // => 4

2.5 佇列操作的時間複雜度

關於佇列所有操作的重點：enqueue，dequeue，peek 和length 必須以常數時間複雜度O (1) 執行。

常數時間複雜度O(1) 意味著無論佇列大小如何（不管是有10 個還是100 萬個項目），這些操作都必須在相對一致的時間內執行。

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

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() 方法中存在：

• 屬性存取器（如:this.items[this.headIndex ]），
• 執行算數運算（如:this.headidex ）

##這些方法的時間複雜度是恆定的時間

O(1)。

4. 總結

佇列是一種遵循先入先出（FIFO）規則的資料結構。

隊列有 2 個主要操作：入隊和出隊。另外，佇列可以有輔助操作，例如 peek 和 length。

所有佇列運算都必須以常數時間 O(1) 執行。

挑戰：改進 dequeue() 和 peek() 方法，當在空隊列上執行時會拋出錯誤。

更多程式相關知識，請造訪：程式設計影片！ ！

以上是詳解佇列資料結構，js中怎麼實作？的詳細內容。更多資訊請關注PHP中文網其他相關文章！