JS資料結構學習：佇列
摘要：
佇列的定義
佇列是遵循先進先出原則的一組有序的項，與棧的不同的是，棧不管是入棧還是出棧操作都是在棧頂操作，佇列則是在隊尾新增元素，隊頂移除，用一個圖來表示大概是這樣事的：
用一個更形象的例子就是：排隊服務，總是先排隊的人會先接受服務，當然不考慮插隊的情況
佇列的建立
...
佇列的定義
佇列是遵循先進先出原則的一組有序的項，與棧的不同的是，棧不管是入棧還是出棧操作都是在棧頂操作，佇列則是在隊尾新增元素，隊頂移除，用一個圖來表示大概是這樣事的：
用一個更形象的例子就是：排隊服務，總是先排隊的人會先接受服務，當然不考慮插隊的情況
佇列的建立
與棧的建立類似，首先建立一個表示佇列的函式，然後定義一個數組用來儲存佇列裡的元素：
function Queue() {
let items = []
}
建立佇列後需要為其定義一些方法，一般來說佇列包含以下方法：
- enqueue(element)：向隊的尾部新增一個新的項
- dequeue()：移除佇列第一項，並返回被移除的元素
- front()：返回佇列第一項，佇列不做任何變動
- isEmpty()：如果佇列中沒有任何元素返回true，否則返回false
- size()：返回佇列包含的元素個數
具體實現：
function Queue() {
let items = []
// 向佇列的尾部新增新元素
this.enqueue = function (element) {
items.push(element)
}
// 遵循先進先出原則，從佇列的頭部移除元素
this.dequeue = function () {
return items.shift()
}
// 返回佇列最前面的項
this.front = function () {
return items[0]
}
// 返回佇列是否為空
this.isEmpty = function () {
return items.length === 0
}
// 返回佇列的長度
this.size = function () {
return items.length
}
// 列印佇列，方便觀察
this.print = function () {
console.log(items.toString())
}
}
佇列的使用
接下來讓我們看看佇列的使用：
let queue = new Queue()
queue.enqueue('a')
queue.enqueue('b')
queue.enqueue('c')
queue.dequeue()
queue.print()
首先向佇列中新增三個元素：a,b,c,然後移除佇列中的一個元素，最後列印現有佇列，讓我們一起圖解這個過程：
es6實現Queue
和實現Stack類一樣，也可以用es6的class語法實現Queue類，用WeakMap儲存私用屬性items，並用閉包返回Queue類，來看具體實現：
let Queue = (function () {
let items = new WeakMap
class Queue {
constructor () {
items.set(this, [])
}
enqueue (element) {
let q = items.get(this)
q.push(element)
}
dequeue () {
let q = items.get(this)
return q.shift()
}
front () {
let q = items.get(this)
return q[0]
}
isEmpty () {
let q = items.get(this)
return q.length === 0
}
size () {
let q = items.get(this)
return q.length
}
print () {
let q = items.get(this)
console.log(q.toString())
}
}
return Queue
})()
let queue = new Queue()
queue.enqueue('a')
queue.enqueue('b')
queue.enqueue('c')
queue.dequeue()
queue.print()
優先佇列
優先佇列顧名思義就是：佇列中的每個元素都會有各自的優先順序，在插入的時候會根據優先順序的高低順序進行插入操作，和前面佇列實現有點不太一樣的地方，佇列中的元素多了有先級的屬性，下面來看具體程式碼：
function PriorityQueue() {
let items = []
// 佇列元素，多定義一個優先順序變數
function QueueElement(element, priority) {
this.element = element
this.priority = priority
}
this.enqueue = function (element, priority) {
let queueElement = new QueueElement(element, priority)
let added = false
for (let i = 0; i < items.length; i++) {
//數字越小優先順序越高
if (queueElement.priority < items[i].priority) {
items.splice(i, 0, queueElement)
added = true
break
}
}
if (!added) {
items.push(queueElement)
}
}
this.dequeue = function () {
return items.shift()
}
this.front = function () {
return items[0]
}
this.isEmpty = function () {
return items.length === 0
}
this.size = function () {
return items.length
}
this.print = function () {
for (let i = 0; i < items.length; i++) {
console.log(`${items[i].priority}-${items[i].element}`)
}
}
}
let priorityQueue = new PriorityQueue()
priorityQueue.enqueue('a', 3)
priorityQueue.enqueue('b', 2)
priorityQueue.enqueue('c', 1)
priorityQueue.dequeue()
priorityQueue.print()
入隊時如果佇列為空直接加入佇列，否則進行比較，priority小的優先順序高，優先順序越高放在佇列的越前面，下面用一個圖來看呼叫過程：
迴圈佇列
迴圈佇列顧名思義就是：給定一個數，然後迭代佇列，從佇列開頭移除一項，然後再將其加到佇列末尾，當迴圈到給定數字時跳出迴圈，從隊首移除一項，直至剩餘一個元素，下面來看具體程式碼：
unction Queue() {
let items = []
this.enqueue = function (element) {
items.push(element)
}
this.dequeue = function () {
return items.shift()
}
this.front = function () {
return items[0]
}
this.isEmpty = function () {
return items.length === 0
}
this.size = function () {
return items.length
}
this.print = function () {
console.log(items.toString())
}
}
function loopQueue(list, num) {
let queue = new Queue()
for (let i = 0; i<list.length; i++) {
queue.enqueue(list[i])
}
while (queue.size() > 1) {
for (let j = 0; j<num; j++) {
queue.enqueue(queue.dequeue())
}
let out = queue.dequeue()
console.log('出佇列：' + out)
}
return queue.dequeue()
}
console.log('last：' + loopQueue(['a', 'b', 'c', 'd', 'e'], 3))
總結
這篇文章主要對佇列做了簡單介紹，對佇列以及相關應用做了簡單實現。如果有錯誤或不嚴謹的地方，歡迎批評指正，如果喜歡，歡迎點贊。