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

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

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

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

隊(duì)列是一種遵循先入先出(FIFO)規(guī)則的數(shù)據(jù)結(jié)構(gòu)。第一個(gè)進(jìn)入隊(duì)列中的項(xiàng)目(輸入)是第一個(gè)出隊(duì)(輸出)的。

隊(duì)列有2個(gè)指針：隊(duì)首和隊(duì)尾。最先進(jìn)入隊(duì)列進(jìn)行排隊(duì)的項(xiàng)目位于隊(duì)首，而最后進(jìn)入隊(duì)列的項(xiàng)目位于隊(duì)尾。

回顧車站的例子，第一個(gè)檢票的是在隊(duì)列的隊(duì)首。剛進(jìn)入隊(duì)列的人在隊(duì)尾。

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

從更高的層面來看，隊(duì)列是一種允許你按照先后順序處理項(xiàng)目的數(shù)據(jù)結(jié)構(gòu)。

2. 隊(duì)列的操作

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

2.1 入隊(duì)操作

入隊(duì)操作在隊(duì)列的尾部插入項(xiàng)目，使其成為隊(duì)列的隊(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ì)操作

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

queue.dequeue(); // => 7

2.3 Peek 操作

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

Peek 操作

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

queue.peek(); // => 7

2.4 length

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

Length 操作

上圖中的隊(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) 意味著無論隊(duì)列大小如何(不管是有 10 個(gè)還是 100 萬個(gè)項(xiàng)目)，這些操作都必須在相對(duì)一致的時(shí)間內(nèi)執(zhí)行。

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

來看一下怎樣在保證所有操作必須以常數(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)目通過數(shù)值索引保持。隊(duì)首項(xiàng)的索引由 Where.HeadInex 跟蹤，隊(duì)尾項(xiàng)由  this.tailIndex 跟蹤。

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

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

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

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

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

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

網(wǎng)站欄目：JavaScript中怎么實(shí)現(xiàn)一個(gè)隊(duì)列
標(biāo)題路徑：http://chinadenli.net/article26/gehocg.html

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

廣告

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