JavaScript # 17 — 佇列(Queue)
回想上一篇所介紹的堆疊(Stack) 那這篇我們再來說說 佇列(Queue)。
佇列 (Queue)
一樣我們先以生活中的例子來說明，就好像去 7–11 排隊結帳時先排隊先結帳，或者是去郵局辨理事務抽號碼牌會依序號碼辨理(插隊打爆 😅)，但不是去菜市場買菜的方式喔！
概念與堆疊 (Stack)不同的事，會以 先進先出 ( FIFO, First-In-First-Out ) 方式運作，意思就是 先進來的資料會優先取得，並且新增與移除資料不是在同一端而是新增資料在後端，移除資料在前端，以陣列的運作方法中可以使用 push() 與 shift() 來實作。
以下是使用陣列方式來實作功能 ：
let array = []console.log(array.push("a")) //1console.log(array) //Array(1) ["a"]console.log(array.push("b")) //2console.log(array) //Array(2) ["a", "b"]console.log(array.push("c")) //3console.log(array) //Array(3) ["a", "b", "c"]
先使用 push() 特性將資料以右至左方式新增陣列中。
let array = ["a", "b", "c"]console.log(array.shift()) //aconsole.log(array) //Array(2) ["b", "c"]console.log(array.shift()) //bconsole.log(array) //Array(1) ["c"]console.log(array.shift()) //cconsole.log(array) //Array(0) []
再使用 shift() 方法，將資料從陣列索引數為 0 先移除，以上方式為 先進先出 ( FIFO, First-In-First-Out ) 運作模式。參考 ： JavaScript Array (陣列)-學習筆記一
以下圖示來說明 ：
佇列 (Queue) 的運作方式為 新增資料會發生於後端，移除資料時會發生於前端，此為 先進先出 ( FIFO, First-In-First-Out ) 的運作方式。
要記得 佇列 (Queue) 並不同於 堆疊 (Stack) 的 後進先出（LIFO, Last In First Out）的運作方式。
佇列範例實作
接下來實作 佇列 (Queue) 的程式碼，先建立一個建構式函式 Queue() ，在函式中新增 temp 的陣列用來暫存佇列的資料結構，但與 堆疊 (Stack)似類但新增與移除是不同端 。
function Queue() {
this.temp = []
}接下來我們需要實作的方法有以下幾種 ：
- enqueue(element) : 於佇列後端新增一個或多個資料。
- dequeue() : 於佇列前端(頭部、第一個)移除資料，並將被移除的資料回傳。
- front() : 呈現佇列前端(頭部、第一個)資料名稱。
- size() : 回傳佇列裡共有幾筆資料數值。
- isEmpty : 回傳佇列內部裡是否還有資料，如佇列為空值回傳
true，否則回傳false。 - clear() : 清空佇列裡的所有資料。
1. enqueue() & dequeue()
在函式中使用 temp 的陣列方式來暫存所需的資料結構，因此我們也使用陣列中 push() 與 shift() 來實作 先進先出 ( FIFO, First-In-First-Out ) 的運作模式。
//於佇列後端新增一個或多個資料，陣列 push 剛好有此特性。
Queue.prototype.enqueue = function (element) {
this.temp.push(element)
}//於佇列前端移除資料，並將被移除的資料回傳，陣列 shift 特性也是如此。Queue.prototype.dequeue = function () {
return this.temp.shift()
}
使用原型物件來建立共用屬性。參考 ： JavaScript # 11 — 基本型別包裹器 (Primitive Wrapper) 、建構式 (Constructor)
2. front()
如要知道佇列中第一個的資料(陣列索引數為 0)並回傳，我們可以實作此方法。
//呈現佇列前端(頭部、第一個)資料名稱
Queue.prototype.front = function () {
return this.temp[0]
}3. size()
如要了解佇列中的個數可使用此方法取得，即為陣列中 length。
//回傳佇列裡共有幾筆資料數值
Queue.prototype.size = function () {
return this.temp.length
}4.isEmpty()
此方法能判斷佇列中不包含任何資料時為 true，否則為false。
//回傳佇列內部裡是否還有資料
Queue.prototype.isEmpty = function () {
return this.temp.length === 0
}5. clear()
如果想要清空所有佇列中的資料時可以使用此方法。
//清空佇列裡的所有資料
Queue.prototype.clear = function () {
return this.temp = []
}完整程式碼
function Queue() {
this.temp = []
}//於佇列後端新增一個或多個資料。
Queue.prototype.enqueue = function (element) {
this.temp.push(element)
}//於佇列前端(頭部、第一個)移除資料，並將被移除的資料回傳。
Queue.prototype.dequeue = function () {
return this.temp.shift()
}//呈現佇列前端(頭部、第一個)資料名稱
Queue.prototype.front = function () {
return this.temp[0]
}//回傳佇列裡共有幾筆資料數值
Queue.prototype.size = function () {
return this.temp.length
}//回傳佇列內部裡是否還有資料
Queue.prototype.isEmpty = function () {
return this.temp.length === 0
}//清空佇列裡的所有資料
Queue.prototype.clear = function () {
return this.temp = []
}
以上已經建立好 Queue 建構式之後就可以直接使用。
let data = new Queue()
以上所在建構式建立的 prototype 屬性可透過 __proto__ 往原型物件中取得。
//判斷佇列裡資料是否為空值
console.log(data.isEmpty()) //true//新增資料
data.enqueue("a")
data.enqueue("b")
data.enqueue("c")//移除前端資料並回傳被移除資料值
console.log(data.dequeue()) //a//取得前端(第一個)資料並回傳資料值
console.log(data.front()) //b//回傳佇列中目前數量值
console.log(data.size()) //2//判斷佇列裡資料是否為空值
console.log(data.isEmpty()) //false//清空佇列中所有資料
data.clear()console.log(data) //Queue {temp: Array(0)}
優先級佇列 Priority Queue
如字面上的意思，優先級最高的可以優先取得，如會員制是 VIP 或救護車優先其他車輛一樣，可以取得第一順位優先權。
我們用圖來說明比較清楚點 ：
優先級佇列 (Priority Queue) 並不會遵守 佇列 (Queue) 的特性 先進先出 ( FIFO, First-In-First-Out ) 的方式，則其優先級最高就會獲得優先的順序，但優先級相同就看排列順序。
優先級佇列範例
我們來將上述的範例再修改 ：
function PriorityQueue() {
this.temp = []
}一樣先建立建構式函式 PriorityQueue() 與temp 的陣列用來暫存優先級佇列的資料結構。
//新增優先級佇列中的資料暫存器
PriorityQueue.prototype.tempElement = function (element, priority) {
this.element = element
this.priority = priority
}//於優先級佇列後端新增一個或多個資料。
PriorityQueue.prototype.enqueue = function (element, priority) {
//建立新建構式物件，暫存優先級佇列中新增資料未來比對用途
let newElement = new this.tempElement(element, priority)
//判斷優先級佇列 temp 暫存器是否為空陣列
if (this.isEmpty()) {
this.temp.push(newElement)
} else {
let add = false
for (let i = 0, len = this.temp.length; i < len; i++) {
//比對 newElement.priority 與 temp.priority 數值
if (newElement.priority < this.temp[i].priority) {
this.temp.splice(i, 0, newElement)
add = true
break
}
}
//如比對不成立時則將 newElement 資料加入 temp 中
if (!add) this.temp.push(newElement)
}
}//於優先級佇列前端(頭部、第一個)移除資料，並將被移除的資料回傳。
PriorityQueue.prototype.dequeue = function () {
return this.temp.shift()
}//呈現優先級佇列前端(頭部、第一個)資料名稱
PriorityQueue.prototype.front = function () {
return this.temp[0]
}//回傳優先級佇列裡共有幾筆資料數值
PriorityQueue.prototype.size = function () {
return this.temp.length
}//回傳優先級佇列內部裡是否還有資料
PriorityQueue.prototype.isEmpty = function () {
return this.temp.length === 0
}//清空優先級佇列裡的所有資料
PriorityQueue.prototype.clear = function () {
return (this.temp = [])
}//列出優先級佇列裡的所有資料
PriorityQueue.prototype.print = function () {
//因為 newElement 是物件所以須將物件型態轉為 JSON 格式輸出
return JSON.stringify(this.temp)
}
執行優先級佇列功能 ：
let data = new PriorityQueue()
//新增資料
data.enqueue("a", 5)
data.enqueue("b", 6)
data.enqueue("c", 4)
data.enqueue("e", 2)
data.enqueue("d", 1)console.log(data.print()) //列出優先級佇列裡的所有資料
//移除前端資料並回傳被移除資料值
//PriorityQueue.tempElement {element: "d", priority: 1}
console.log(data.dequeue())//取得前端(第一個)資料並回傳資料值
//PriorityQueue.tempElement {element: "e", priority: 2}
console.log(data.front())//回傳優先級佇列中目前數量值
console.log(data.size()) //4//判斷優先級佇列裡資料是否為空值
console.log(data.isEmpty()) //false//列出優先級佇列裡的所有資料
console.log(data.print()) //[]//清空優先級佇列中所有資料
data.clear()
…
參考： 佇列 、優先佇列 、佇列 Queue以上是我對 JavaScript # 17 — 佇列(Queue) 的學習筆記 😉。
***如果有任何想法，也歡迎留言與我分享~***
