前一章學到了 "後進先出" (Stack)，今天要來看 "先進先出" 的資料結構 Queue

什麼是佇列(Queue)？

佇列(Queue) 是一種 先進先出 (FIFO: First In First out) 的資料結構。 以日常生活例子就是排隊，先來的會在前面，後來的會在後面。

Queue 的特性就是新增元素時發生在 Back後端，刪除元素時發生在 Front 前端。不像 Stack 新增刪除都是發生在頂端
在平常寫 javaScript 其實也都有用到 Queue 概念，例如 Event Loop (這篇鐵人賽作者也有提到)

建立 Queue

我們用 js 的 Array 來實作 Queue。需要方法如下

enqueue(ele):  從後面插入一個元素
dequeue(): 從前面移除元素
front():  return 最前面的值
clear(): 清空 Queue 裡的所有元素
size(): return 長度

class Queue {
  constructor () {
    this.list = []
  }
  // 插入一個元素
  enqueue( ele ){
    this.list.push(ele)
  }
  // 從頭移除元素
  dequeue(){
    this.list.shift();
  }
  // 總共幾個
  size(){
    return this.list.length;
  }
  // 回傳最前面的 ele
  front(){
    return this.list[0]
  }
	// 清掉全部
  clear(){
    this.list = []
  }
}

let queueAnimals = new Queue()
queueAnimals.enqueue('duck')
queueAnimals.enqueue('deer')
queueAnimals.enqueue('bear')
console.log(queueAnimals.size())

優先級佇列 Priority Queue

優先級最高的會最提早獲得服務，例如：VIP 會員可以優先排隊進場、救護車優先於其他車輛等等

以上圖來說，獅子跟大象也來排隊，以正常 Queue 來說他們應該要排在最後。但他們吵著說他們是森林之王所以應該享有優先權。只好把它們兩個排到最前面

下列就來改寫 Queue

• 假如是 Priority Queue 就加第二個參數給他代表優先順序
• 判斷是不是 Priority Queue， 是的話插入最前

// primary have a number, 1 is in the front, 2 is behind
class Queue {
    constructor () {
      this.list = []
    }
    // 插入一個元素
    enqueue( ele, primary ){
        if(primary){
            this.list.splice(primary-1, 0, ele)
            
        }else{
          this.list.push(ele)
        }
        
    }
    // 從頭移除元素
    dequeue(){
      this.list.shift();
    }
    // 總共幾個
    size(){
      return this.list.length;
    }
    // 回傳最前面的 ele
    front(){
      return this.list[0]
    }
    // 清掉全部
    clear(){
      this.list = []
    }
    // 列出所有的 list
    print(){
      return this.list;
    }
  }
  
  let queueAnimal = new Queue()
  queueAnimal.enqueue('duck')
  queueAnimal.enqueue('deer')
  queueAnimal.enqueue('beer')
  queueAnimal.enqueue('elephant', 1)
  queueAnimal.enqueue('lion', 2)

  console.log(queueAnimal .print())

鐵人賽終於到一半了，下一篇要介紹最後一個資料結構: Linked List

如有錯誤或需要改進的地方，拜託跟我說。
我會以最快速度修改，感謝您

歡迎追蹤我的部落格，除了技術文也會分享一些在矽谷工作的甘苦。