JavaScript中如何實(shí)現(xiàn)隊(duì)列結(jié)構(gòu)

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

JavaScript可以做什么

1.可以使網(wǎng)頁(yè)具有交互性，例如響應(yīng)用戶點(diǎn)擊，給用戶提供更好的體驗(yàn)。 2.可以處理表單，檢驗(yàn)用戶的輸入，并提供及時(shí)反饋節(jié)省用戶時(shí)間。 3.可以根據(jù)用戶的操作，動(dòng)態(tài)的創(chuàng)建頁(yè)面。 4使用JavaScript可以通過(guò)設(shè)置cookie存儲(chǔ)在瀏覽器上的一些臨時(shí)信息。

1. 隊(duì)列數(shù)據(jù)結(jié)構(gòu)

隊(duì)列是一種“先入先出”（FIFO）數(shù)據(jù)結(jié)構(gòu)的類型。第一個(gè)入隊(duì)項(xiàng)目（輸入）是第一個(gè)出隊(duì)（輸出）。

隊(duì)列有2個(gè)指針：頭和尾。隊(duì)列中的最早排隊(duì)的項(xiàng)目是在頭部，而最新排隊(duì)的項(xiàng)目在隊(duì)列尾部。

隊(duì)列就像我們?cè)诘罔F排隊(duì)，靠近車門處的乘客位于隊(duì)伍的頭部，剛進(jìn)入隊(duì)伍的乘客位于隊(duì)伍的尾部。

從更高的角度來(lái)看，隊(duì)列是一種數(shù)據(jù)結(jié)構(gòu)，可以讓我們按照入庫(kù)的順序依次處理數(shù)據(jù)的每一項(xiàng)。

2. 隊(duì)列的操作

隊(duì)列支持 2 個(gè)主要操作：入隊(duì)（enqueue）和出隊(duì)（dequeue），另外還有 peek 和 length 操作。

2.1 入隊(duì)操作

入隊(duì)操作在隊(duì)列的尾部插入項(xiàng)目，使其成為隊(duì)列的隊(duì)尾。

上圖中的入隊(duì)操作在隊(duì)尾插入了 8，之后 8 成為隊(duì)列的隊(duì)尾。

queue.enqueue(8);

2.2 出隊(duì)操作

出隊(duì)操作取出隊(duì)列中第一個(gè)項(xiàng)目，此時(shí)隊(duì)列中的下一個(gè)項(xiàng)目成為隊(duì)首。

在上圖中，出隊(duì)操作返回項(xiàng)目7并從隊(duì)列中刪除。 出隊(duì)之后之后，項(xiàng)目 2 成為新的隊(duì)首。

queue.dequeue(); // => 7

2.3 Peek 操作

Peek 操作讀取隊(duì)首的項(xiàng)目，但是不改變隊(duì)列。

上圖中  7 是隊(duì)首。 peek 操作只需返回隊(duì)首 7 但是不修改隊(duì)列。

queue.peek(); // => 7

2.4 length

length 操作返回隊(duì)列中包含項(xiàng)目的數(shù)量。

上圖中的隊(duì)列有 4 項(xiàng)：4、6、2 和。7。結(jié)果隊(duì)列長(zhǎng)度為 4。

queue.length; // => 4

2.5 隊(duì)列操作的時(shí)間復(fù)雜度

關(guān)于隊(duì)列所有操作的重點(diǎn)：enqueue，dequeue，peek 和 length 必須以常數(shù)時(shí)間復(fù)雜度 O(1) 執(zhí)行。

常數(shù)時(shí)間復(fù)雜度 O(1) 意味著無(wú)論隊(duì)列大小如何（不管是有 10 個(gè)還是 100 萬(wàn)個(gè)項(xiàng)目），這些操作都必須在相對(duì)一致的時(shí)間內(nèi)執(zhí)行。

3. 用 JavaScript 實(shí)現(xiàn)隊(duì)列

來(lái)看一下怎樣在保證所有操作必須以常數(shù)時(shí)間復(fù)雜度O(1) 要求實(shí)現(xiàn)隊(duì)列這種數(shù)據(jù)結(jié)構(gòu)。

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)建隊(duì)列的實(shí)例。

queue.enqueue(7) 方法將 7 存入隊(duì)列中。

queue.dequeue() 從隊(duì)列中取出一個(gè)頭部項(xiàng)目，而 queue.peek() 只讀隊(duì)首項(xiàng)。

最后的 Queue.Length 顯示隊(duì)列中還有多少個(gè)項(xiàng)目。

關(guān)于實(shí)現(xiàn)：在 Queue 類中，普通對(duì)象  this.Items  將隊(duì)列的項(xiàng)目通過(guò)數(shù)值索引保持。 隊(duì)首項(xiàng)的索引由 Where.HeadInex 跟蹤，隊(duì)尾項(xiàng)由 this.tailIndex 跟蹤。

隊(duì)列方法的復(fù)雜度

在 Queue 的 queue()、 dequeue()、 peek() 和 length() 方法中存在：

• 屬性訪問(wèn)器（如:this.items[this.headIndex]），

• 執(zhí)行算數(shù)操作（如:this.headidex++）

這些方法的時(shí)間復(fù)雜度是恒定的時(shí)間 O(1)。

4. 總結(jié)

隊(duì)列是一種遵循先入先出（FIFO）規(guī)則的的數(shù)據(jù)結(jié)構(gòu)。

隊(duì)列有 2 個(gè)主要操作：入隊(duì)和出隊(duì)。 另外，隊(duì)列可以有輔助操作，例如 peek 和 length。

所有隊(duì)列操作都必須以常數(shù)時(shí)間 O(1) 執(zhí)行。

以上是“JavaScript中如何實(shí)現(xiàn)隊(duì)列結(jié)構(gòu)”這篇文章的所有內(nèi)容，感謝各位的閱讀！相信大家都有了一定的了解，希望分享的內(nèi)容對(duì)大家有所幫助，如果還想學(xué)習(xí)更多知識(shí)，歡迎關(guān)注億速云行業(yè)資訊頻道！