如何在JavaScript中實現(xiàn)隊列

這篇文章將為大家詳細講解有關如何在JavaScript中實現(xiàn)隊列，小編覺得挺實用的，因此分享給大家做個參考，希望大家閱讀完這篇文章后可以有所收獲。

1. 隊列數(shù)據(jù)結構

• 隊列是一種“先入先出”（FIFO）數(shù)據(jù)結構的類型。第一個入隊項目（輸入）是第一個出隊（輸出）。

• 隊列有2個指針：頭和尾。隊列中的最早排隊的項目是在頭部，而最新排隊的項目在隊列尾部。

• 隊列就像我們在地鐵排隊，靠近車門處的乘客位于隊伍的頭部，剛進入隊伍的乘客位于隊伍的尾部。

從更高的角度來看，隊列是一種數(shù)據(jù)結構，可以讓我們按照入庫的順序依次處理數(shù)據(jù)的每一項。

2. 隊列上的操作

隊列支持2個主要操作：入隊和出隊。此外，您可能會發(fā)現(xiàn)執(zhí)行隊列的 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

• 隊列操作時間復雜度
  對于所有隊列操作（入隊，出隊，檢視和長度）重要的是，所有這些操作必須在固定時間內(nèi)執(zhí)行O(1)。

恒定的時間O(1)意味著無論隊列大小如何（它可以有10或100萬個項目）：入隊，出隊，窺視和長度操作都必須同時執(zhí)行。

3. 在JavaScript中實現(xiàn)隊列

讓我們看一下隊列數(shù)據(jù)結構的可能實現(xiàn)，同時保持所有操作必須在恒定時間內(nèi)執(zhí)行的要求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()是如何創(chuàng)建隊列的實例。

調(diào)用queue.enqueue(7)方法使該項目7進入隊列。

queue.dequeue()從隊列中取出一個頭項，而queue.peek()只是從頭檢視。

最后，queue.length顯示隊列中還有多少項目。

關于實現(xiàn)：在Queue類內(nèi)部，普通對象this.items通過數(shù)字索引保留隊列中的項目。頭項的索引由跟蹤this.headIndex，尾項由跟蹤this.tailIndex。

• 隊列方法的復雜性

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

屬性訪問（例如this.items[this.headIndex]），

或執(zhí)行算術操作（例如this.headIndex++）

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

4. 總結

隊列數(shù)據(jù)結構是“先入先出”（FIFO）的一種：最早入隊的項是最早出隊的項。

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

所有隊列操作必須在恒定時間內(nèi)執(zhí)行O(1)。

關于“如何在JavaScript中實現(xiàn)隊列”這篇文章就分享到這里了，希望以上內(nèi)容可以對大家有一定的幫助，使各位可以學到更多知識，如果覺得文章不錯，請把它分享出去讓更多的人看到。