實例圖文詳解在JavaScript中實作佇列

相關推薦：javascript教學

1. 佇列資料結構佇列

• 是一種「先入先出」（FIFO）資料結構的型別。第一個入隊項目（輸入）是第一個出隊（輸出）。
• 隊列有2個指針：頭和尾。隊列中的最早排隊的項目是在頭部，而最新排隊的項目在隊列尾部。
• 隊列就像我們在地鐵排隊，靠近車門處的乘客位於隊伍的頭部，剛進入隊伍的乘客位於隊伍的尾部。

從更高的角度來看，佇列是一種資料結構，可以讓我們按照入庫的順序依序處理資料的每一項。

2. 佇列上的操作

隊列支援2個主要操作：入隊和出隊。此外，您可能會發現執行佇列的peek 和length 操作很有用。

• 入隊操作<br/> 入隊操作是在佇列尾部插入一個項目，插入的項目成為佇列的尾部。

上圖中的入隊操作將項目8 插入到尾部，8成為佇列的尾部。

queue.enqueue(8);

• 出隊操作<br/> 出隊操作是在佇列的開頭提取項目，佇列中的下一個項目成為頭部項目。

在上圖中，出隊操作返回並7 從佇列中刪除該項目，出隊後，項目2成為新的頭部項目。

queue.dequeue(); // => 7

• 檢視操作<br/> 檢視操作讀取佇列的開頭，而不會變更佇列。

項目7是上圖中的佇列的開頭，檢視操作僅傳回標頭（項目）7，而無需修改佇列。

queue.peek(); // => 7

• 佇列長度長度操作計算佇列包含多少個項目。

圖中的隊列中有4項：4，6，2，和7，結果，隊列長度為4。

queue.length; // => 4

• 佇列操作時間複雜度對於所有佇列操作（入隊，出隊，檢視和長度）重要的是，所有這些操作必須在固定時間內執行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透過數位索引保留佇列中的項目。頭項的索引由追蹤this.headIndex，尾項由追蹤this.tailIndex。

• 隊列方法的複雜性

類別Queue 的方法queue()，dequeue()，peek()和length() 僅使用了：

屬性存取（例如this.items[this.headIndex]），

或執行算術運算（例如this.headIndex++）

因此，這些方法的時間複雜度是恆定時間O(1)。

4. 總結

隊列資料結構是「先入先出」（FIFO）的一種：最早入隊的項是最早出隊的項。

隊列有2個主要操作：入隊和出隊。另外，佇列可以具有輔助操作，例如檢視和長度。

所有佇列操作必須在恆定時間內執行O(1)。

相關推薦：javascript學習教學

以上就是實例圖文詳解在JavaScript中實作佇列的詳細內容，更多請關注php中文網其它相關文章！