JavaScript隊列結(jié)構(gòu)Queue實現(xiàn)過程解析

更新時間：2020年03月07日 10:41:00 作者：AhuntSun

這篇文章主要介紹了JavaScript隊列結(jié)構(gòu)Queue實現(xiàn)過程解析,文中通過示例代碼介紹的非常詳細，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友可以參考下

一、隊列簡介

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

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

相當(dāng)于排隊買票，先來的先買票，后來的后買票。

隊列的應(yīng)用：

打印隊列：計算機打印多個文件的時候，需要排隊打??；線程隊列：當(dāng)開啟多線程時，當(dāng)新開啟的線程所需的資源不足時就先放入線程隊列，等待CPU處理；

隊列類的實現(xiàn)：

隊列的實現(xiàn)和棧一樣，有兩種方案：

基于數(shù)組實現(xiàn)；基于鏈表實現(xiàn)；

隊列的常見操作：

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

二、封裝隊列類

2.1.代碼實現(xiàn)

  // 基于數(shù)組封裝隊列類
  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():查看隊列中元素的個數(shù)
  Queue.prototype.size = () => {
   return this.items.length
  }

  // 6.toString():將隊列中元素以字符串形式輸出
  Queue.prototype.toString = () => {
   let resultString = ''
    for (let i of this.items){
     resultString += i + ' '
    }
    return resultString
   }
  }

測試代碼：

  // 創(chuàng)建隊列
  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

測試結(jié)果：

2.2.隊列的應(yīng)用

使用隊列實現(xiàn)小游戲：擊鼓傳花，傳入一組數(shù)據(jù)和設(shè)定的數(shù)字num，循環(huán)遍歷數(shù)組內(nèi)元素，遍歷到的元素為指定數(shù)字num時將該元素刪除，直至數(shù)組剩下一個元素。

代碼實現(xiàn)：

  // 隊列應(yīng)用：面試題：擊鼓傳花
  let passGame = (nameList, num) => {
   //1.創(chuàng)建隊列結(jié)構(gòu)
   let queue = new Queue()

   //2.將所有人依次加入隊列
   // 這是ES6的for循環(huán)寫法，i相當(dāng)于nameList[i]
   for(let i of nameList){
    queue.enqueue(i)
   }
   

   // 3.開始數(shù)數(shù)
   while(queue.size() > 1){//隊列中只剩1個人就停止數(shù)數(shù)
   // 不是num的時候，重新加入隊列末尾
   // 是num的時候，將其從隊列中刪除
   // 3.1.num數(shù)字之前的人重新放入隊列的末尾(把隊列前面刪除的加到隊列最后)
   for(let i = 0; i< num-1; i++ ){
    queue.enqueue(queue.dequeue())
   }
   // 3.2.num對應(yīng)這個人，直接從隊列中刪除
   /*
    思路是這樣的，由于隊列沒有像數(shù)組一樣的下標(biāo)值不能直接取到某一元素，所以采用，把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

測試結(jié)果：

三、優(yōu)先隊列

優(yōu)先級隊列主要考慮的問題為：

每個元素不再只是一個數(shù)據(jù)，還包含數(shù)據(jù)的優(yōu)先級；在添加數(shù)據(jù)過程中，根據(jù)優(yōu)先級放入到正確位置；3.1.優(yōu)先級隊列的實現(xiàn)

代碼實現(xiàn)：

  // 封裝優(yōu)先級隊列
  function PriorityQueue() {

   //內(nèi)部類：在類里面再封裝一個類;表示帶優(yōu)先級的數(shù)據(jù)
   function QueueElement(element, priority) {
    this.element = element;
    this.priority = priority;
   } 

   // 封裝屬性
   this.items = []

   // 1.實現(xiàn)按照優(yōu)先級插入方法
   PriorityQueue.prototype.enqueue = (element, priority) => {
    // 1.1.創(chuàng)建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){
      // 讓新插入的元素與原有元素進行優(yōu)先級比較(priority越小，優(yōu)先級越大)
      if(queueElement.priority < i.priority){
       this.items.splice(i, 0, queueElement)
       added = true
       // 新元素已經(jīng)找到插入位置了可以使用break停止循環(huán)
       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():查看隊列中元素的個數(shù)
   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);
  // 打印修改過后的優(yōu)先隊列對象
  console.log(pq);

測試結(jié)果：

3.2.注意點

關(guān)于數(shù)組方法splice用法：

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

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

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

數(shù)組：在數(shù)組[0，1，2]中，pop(3)，結(jié)果為[0，1，2，3]；
棧：執(zhí)行pop(0)，pop(1)，pop(2)，pop(3)，從棧底到棧頂?shù)脑胤謩e為：0，1，2，3；如果看成數(shù)組，可寫為[0，1，2，3]，但是索引為3的元素3其實是棧頂元素；所以說棧的push方法是向棧頂添加元素（但在數(shù)組的視角下為向數(shù)組尾部添加元素）；
隊列：enqueue方法可以由數(shù)組的push方法實現(xiàn)，與數(shù)組相同，相當(dāng)于在數(shù)組尾部添加元素。

可以這樣想：棧結(jié)構(gòu)是頭朝下（索引值由下往上增大）的數(shù)組結(jié)構(gòu)。