JavaScript中怎么實現(xiàn)一個隊列

JavaScript中怎么實現(xiàn)一個隊列，相信很多沒有經(jīng)驗的人對此束手無策，為此本文總結了問題出現(xiàn)的原因和解決方法，通過這篇文章希望你能解決這個問題。

創(chuàng)新互聯(lián)是一家專業(yè)提供丹寨企業(yè)網(wǎng)站建設,專注與成都做網(wǎng)站、成都網(wǎng)站建設、H5場景定制、小程序制作等業(yè)務。10年已為丹寨眾多企業(yè)、政府機構等服務。創(chuàng)新互聯(lián)專業(yè)網(wǎng)站建設公司優(yōu)惠進行中。

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

如果你喜歡四處旅行，肯定在火車站經(jīng)歷過檢票這道手續(xù)。如果有很多人要坐火車，那么很自然地會形成一個隊列。剛進入車站的人加入隊列。另一邊剛剛通過檢票的人從隊列中走出。這就是隊列的一個例子，與隊列數(shù)據(jù)結構的操作方式相同。

隊列是一種遵循先入先出(FIFO)規(guī)則的數(shù)據(jù)結構。第一個進入隊列中的項目(輸入)是第一個出隊(輸出)的。

隊列有2個指針：隊首和隊尾。最先進入隊列進行排隊的項目位于隊首，而最后進入隊列的項目位于隊尾。

回顧車站的例子，第一個檢票的是在隊列的隊首。剛進入隊列的人在隊尾。

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

從更高的層面來看，隊列是一種允許你按照先后順序處理項目的數(shù)據(jù)結構。

2. 隊列的操作

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

2.1 入隊操作

入隊操作在隊列的尾部插入項目，使其成為隊列的隊尾。

入隊操作

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

queue.enqueue(8);

2.2 出隊操作

出隊操作取出隊列中第一個項目，此時隊列中的下一個項目成為隊首。

出隊操作

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

queue.dequeue(); // => 7

2.3 Peek 操作

Peek 操作讀取隊首的項目，但是不改變隊列。

Peek 操作

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

queue.peek(); // => 7

2.4 length

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

Length 操作

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

queue.length; // => 4

2.5 隊列操作的時間復雜度

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

常數(shù)時間復雜度 O(1) 意味著無論隊列大小如何(不管是有 10 個還是 100 萬個項目)，這些操作都必須在相對一致的時間內執(zhí)行。

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

來看一下怎樣在保證所有操作必須以常數(shù)時間復雜度O(1) 要求實現(xiàn)隊列這種數(shù)據(jù)結構。

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)建隊列的實例。

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

queue.dequeue() 從隊列中取出一個頭部項目，而 queue.peek() 只讀隊首項。

最后的 Queue.Length 顯示隊列中還有多少個項目。

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

隊列方法的復雜度

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

• 屬性訪問器(如:this.items[this.headIndex])，

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

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

看完上述內容，你們掌握JavaScript中怎么實現(xiàn)一個隊列的方法了嗎？如果還想學到更多技能或想了解更多相關內容，歡迎關注創(chuàng)新互聯(lián)行業(yè)資訊頻道，感謝各位的閱讀！

網(wǎng)站欄目：JavaScript中怎么實現(xiàn)一個隊列
標題路徑：http://muchs.cn/article26/gehocg.html

成都網(wǎng)站建設公司_創(chuàng)新互聯(lián)，為您提供動態(tài)網(wǎng)站、網(wǎng)站維護、虛擬主機、搜索引擎優(yōu)化、、域名注冊

廣告

聲明：本網(wǎng)站發(fā)布的內容（圖片、視頻和文字）以用戶投稿、用戶轉載內容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內容未經(jīng)允許不得轉載，或轉載時需注明來源： 創(chuàng)新互聯(lián)