用JavaScript實現隊列
作為一個優秀的程序猿需要具有知識的廣度。首先是要了解你選擇的編程語言。
然而在熟悉了編程語言之后，你還必須了解如何根據任務輕松且有效地操縱數據。這就是數據結構的用武之地。
在本文中，我將描述隊列數據這個結構：它都有哪些操作以及在 JavaScript 中怎樣實現。
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 操作讀取隊首的項目，但是不改變隊列。
Peek 操作
上圖中 7 是隊首。peek 操作只需返回隊首 7 但是不修改隊列。
- queue.peek(); // => 7
2.4 length
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) 執行。
挑戰一下：改進 dequeue() 和 peek() 方法，當在空隊列上執行時會拋出錯誤。
