用JavaScript實(shí)現(xiàn)隊(duì)列
作為一個(gè)優(yōu)秀的程序猿需要具有知識(shí)的廣度。首先是要了解你選擇的編程語言。
然而在熟悉了編程語言之后，你還必須了解如何根據(jù)任務(wù)輕松且有效地操縱數(shù)據(jù)。這就是數(shù)據(jù)結(jié)構(gòu)的用武之地。
在本文中，我將描述隊(duì)列數(shù)據(jù)這個(gè)結(jié)構(gòu)：它都有哪些操作以及在 JavaScript 中怎樣實(shí)現(xià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ì)列長度為 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)目)，這些操作都必須在相對一致的時(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 類中，普通對象 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)。
4. 總結(jié)
隊(duì)列是一種遵循先入先出(FIFO)規(guī)則的的數(shù)據(jù)結(jié)構(gòu)。
隊(duì)列有 2 個(gè)主要操作：入隊(duì)和出隊(duì)。另外，隊(duì)列可以有輔助操作，例如 peek 和 length。
所有隊(duì)列操作都必須以常數(shù)時(shí)間 O(1) 執(zhí)行。
挑戰(zhàn)一下：改進(jìn) dequeue() 和 peek() 方法，當(dāng)在空隊(duì)列上執(zhí)行時(shí)會(huì)拋出錯(cuò)誤。
