範例圖文詳解在JavaScript中實現佇列

本篇文章給大家帶來了關於的相關知識，其中主要介紹了JavaScript實現佇列的相關問題，描述佇列資料結構，其具有的操作以及展示JavaScript中的佇列實現，希望對大家有幫助。

1. 佇列資料結構

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

在這裡插入圖片描述

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

2. 佇列上的操作

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

入隊操作
入隊操作是在佇列尾部插入一個專案，插入的專案成為佇列的尾部。

在這裡插入圖片描述

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

queue.enqueue(8);

出隊操作
出隊操作是在佇列的開頭提取專案，佇列中的下一個專案成為頭部專案。

在這裡插入圖片描述

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

queue.dequeue(); // => 7

檢視操作
檢視操作讀取佇列的開頭，而不會更改佇列。

在這裡插入圖片描述

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