JavaScript中如何實現隊列結構

小編給大家分享一下JavaScript中如何實現隊列結構，相信大部分人都還不怎么了解，因此分享這篇文章給大家參考一下，希望大家閱讀完這篇文章后大有收獲，下面讓我們一起去了解一下吧！

JavaScript可以做什么

1.可以使網頁具有交互性，例如響應用戶點擊，給用戶提供更好的體驗。 2.可以處理表單，檢驗用戶的輸入，并提供及時反饋節省用戶時間。 3.可以根據用戶的操作，動態的創建頁面。 4使用JavaScript可以通過設置cookie存儲在瀏覽器上的一些臨時信息。

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) 執行。

以上是“JavaScript中如何實現隊列結構”這篇文章的所有內容，感謝各位的閱讀！相信大家都有了一定的了解，希望分享的內容對大家有所幫助，如果還想學習更多知識，歡迎關注億速云行業資訊頻道！