JavaScript實現隊列結構（Queue）

• 2020 年 3 月 6 日
• 筆記

JavaScript實現隊列結構（Queue）

一、隊列簡介

隊列是是一種受限的線性表，特點為先進先出（FIFO：first in first out）。

• 受限之處在於它只允許在表的前端（front）進行刪除操作；
• 在表的後端（rear）進行插入操作；

相當於排隊買票，先來的先買票，後來的後買票。

隊列的應用：

• 列印隊列：電腦列印多個文件的時候，需要排隊列印；
• 執行緒隊列：當開啟多執行緒時，當新開啟的執行緒所需的資源不足時就先放入執行緒隊列，等待CPU處理；

隊列類的實現：

隊列的實現和棧一樣，有兩種方案：

• 基於數組實現；
• 基於鏈表實現；

隊列的常見操作：

• enqueue（element）：向隊列尾部添加一個（或多個）新的項；
• dequeue（）：移除隊列的第一（即排在隊列最前面的）項，並返回被移除的元素；
• front（）：返回隊列中的第一個元素——最先被添加，也將是最先被移除的元素。隊列不做任何變動（不移除元素，只返回元素資訊與Stack類的peek方法非常類似）；
• isEmpty（）：如果隊列中不包含任何元素，返回true，否則返回false；
• size（）：返回隊列包含的元素個數，與數組的length屬性類似；
• toString（）：將隊列中的內容，轉成字元串形式；

二、封裝隊列類

2.1.程式碼實現

    // 基於數組封裝隊列類      function Queue() {      // 屬性        this.items = []        // 方法      // 1.enqueue():將元素加入到隊列中      Queue.prototype.enqueue = element => {        this.items.push(element)      }        // 2.dequeue():從隊列中刪除前端元素      Queue.prototype.dequeue = () => {        return this.items.shift()      }        // 3.front():查看前端的元素      Queue.prototype.front = () => {        return this.items[0]      }        // 4.isEmpty:查看隊列是否為空      Queue.prototype.isEmpty = () => {        return this.items.length == 0;      }        // 5.size():查看隊列中元素的個數      Queue.prototype.size = () => {        return this.items.length      }        // 6.toString():將隊列中元素以字元串形式輸出      Queue.prototype.toString = () => {        let resultString = ''          for (let i of this.items){            resultString += i + ' '          }          return resultString        }      }

測試程式碼：

    // 創建隊列      let queue = new  Queue()        // 將元素加入到隊列中      queue.enqueue('a')      queue.enqueue('b')      queue.enqueue('c')      queue.enqueue('d')      console.log(queue);                                             //58        // 從隊列中刪除元素      queue.dequeue()      console.log(queue);                                             //62      queue.dequeue()      console.log(queue);                                             //64        //front      console.log(queue.front());                                     //67        // 驗證其他方法      console.log(queue.isEmpty());                                   //70      console.log(queue.size());                                      //71      console.log(queue.toString());                                  //72

測試結果：

2.2.隊列的應用

使用隊列實現小遊戲：擊鼓傳花，傳入一組數據和設定的數字num，循環遍曆數組內元素，遍歷到的元素為指定數字num時將該元素刪除，直至數組剩下一個元素。

程式碼實現：

    // 隊列應用：面試題：擊鼓傳花      let passGame = (nameList, num) => {        //1.創建隊列結構        let queue = new Queue()          //2.將所有人依次加入隊列        // 這是ES6的for循環寫法，i相當於nameList[i]        for(let i of nameList){          queue.enqueue(i)        }            // 3.開始數數       while(queue.size() > 1){//隊列中只剩1個人就停止數數        // 不是num的時候，重新加入隊列末尾        // 是num的時候，將其從隊列中刪除        // 3.1.num數字之前的人重新放入隊列的末尾(把隊列前面刪除的加到隊列最後)        for(let i = 0; i< num-1; i++ ){          queue.enqueue(queue.dequeue())        }        // 3.2.num對應這個人，直接從隊列中刪除        /*          思路是這樣的，由於隊列沒有像數組一樣的下標值不能直接取到某一元素，所以採用，把num前面的num-1個元素先刪除後添加到隊列末尾，這樣第num個元素就排到了隊列的最前面，可以直接使用dequeue方法進行刪除        */        queue.dequeue()       }          //4.獲取剩下的那個人        console.log(queue.size());                                    //104        let endName = queue.front()        console.log('最終剩下的人：' + endName);                        //106          return nameList.indexOf(endName);      }        //5.測試擊鼓傳花      let names = ['lily', 'lucy', 'Tom', 'Lilei', 'Tony']      console.log(passGame(names, 3));                                //113

測試結果：

三、優先隊列

優先順序隊列主要考慮的問題為：

• 每個元素不再只是一個數據，還包含數據的優先順序；
• 在添加數據過程中，根據優先順序放入到正確位置；

3.1.優先順序隊列的實現

程式碼實現：

    // 封裝優先順序隊列      function PriorityQueue() {          //內部類：在類裡面再封裝一個類;表示帶優先順序的數據        function QueueElement(element, priority) {          this.element = element;          this.priority = priority;        }          // 封裝屬性        this.items = []          // 1.實現按照優先順序插入方法        PriorityQueue.prototype.enqueue = (element, priority) => {          // 1.1.創建QueueElement對象          let queueElement = new QueueElement(element, priority)            // 1.2.判斷隊列是否為空          if(this.items.length == 0){            this.items.push(queueElement)          }else{            // 定義一個變數記錄是否成功添加了新元素            let added = false            for(let i of this.items){              // 讓新插入的元素與原有元素進行優先順序比較(priority越小，優先順序越大)              if(queueElement.priority < i.priority){                this.items.splice(i, 0, queueElement)                added = true                // 新元素已經找到插入位置了可以使用break停止循環                break              }            }            // 新元素沒有成功插入，就把它放在隊列的最前面            if(!added){              this.items.push(queueElement)            }          }        }          // 2.dequeue():從隊列中刪除前端元素        PriorityQueue.prototype.dequeue = () => {          return this.items.shift()        }          // 3.front():查看前端的元素        PriorityQueue.prototype.front = () => {          return this.items[0]        }          // 4.isEmpty():查看隊列是否為空        PriorityQueue.prototype.isEmpty = () => {          return this.items.length == 0;        }          // 5.size():查看隊列中元素的個數        PriorityQueue.prototype.size = () => {          return this.items.length        }          // 6.toString():以字元串形式輸出隊列中的元素        PriorityQueue.prototype.toString = () => {          let resultString = ''            for (let i of this.items){              resultString += i.element + '-' + i.priority + ' '            }            return resultString          }      }

測試程式碼：

    // 測試程式碼      let pq = new PriorityQueue();      pq.enqueue('Tom',111);      pq.enqueue('Hellen',200);      pq.enqueue('Mary',30);      pq.enqueue('Gogo',27);      // 列印修改過後的優先隊列對象      console.log(pq);

測試結果：

3.2.注意點

關於數組方法splice用法：

• splice（1，0，’Tom’）：表示在索引為1的元素前面插入元素』Tom『（也可以理解為從索引為1的元素開始刪除，刪除0個元素，再在索引為1的元素前面添加元素’Tom’）；

• splice（1，1，’Tom’）：表示從索引為1的元素開始刪除（包括索引為1的元素），共刪除1個元素，並添加元素’Tom’。即把索引為1的元素替換為元素’Tom’。

數組的push方法在數組、棧和隊列中的形式：

• 數組：在數組[0，1，2]中，pop(3)，結果為[0，1，2，3]；
• 棧：執行pop(0)，pop(1)，pop(2)，pop(3)，從棧底到棧頂的元素分別為：0，1，2，3；如果看成數組，可寫為[0，1，2，3]，但是索引為3的元素3其實是棧頂元素；所以說棧的push方法是向棧頂添加元素（但在數組的視角下為向數組尾部添加元素）；
• 隊列：enqueue方法可以由數組的push方法實現，與數組相同，相當於在數組尾部添加元素。

可以這樣想：棧結構是頭朝下（索引值由下往上增大）的數組結構。