佇列結構
一.認識佇列
- 受限的線性結構:
- 我們已經學習了一種受限的線性結構:堆疊結構.
- 并且已經知道這種受限的資料結構對于解決某些特定問題,會有特別的
效果. - 下面,我們再來學習另外一個受限的資料結構:佇列.
- 佇列(Queue)，它是一種受限的線性表,先進先出(FIFO First ln First Out)
- 受限之處在于它只允許在表的前端( front ）進行洗掉操作
- 而在表的后端(rear)進行插入操作
- 生活中類似的佇列結構
- 生活中類似佇列的場景就是非常多了
- 比如在電影院,商場,甚至是廁所排隊.
- 優先排隊的人,優先處理.(買票,結賬, WC)
二.佇列的應用
- 列印佇列:
- 有五份檔案需要列印,這些檔案會按照次序放入到列印佇列中.
- 列印機會依次從佇列中取出檔案,優先放入的檔案，優先被取出，并且對該檔案進行列印.
- 以此類推,直到佇列中不再有新的檔案.
- 執行緒佇列:
- 在開發中,為了讓任務可以并行處理,通常會開啟多個執行緒.
- 但是,我們不能讓大量的執行緒同時運行處理任務.(占用過多的資源)
- 這個時候,如果有需要開啟執行緒處理任務的情況,我們就會使用執行緒佇列.
- 執行緒佇列會依照次序來啟動執行緒,并且處理對應的任務.
- 佇列如何實作呢?
- 我們一起來研究一下佇列的實作.
三.佇列類的創建
- 佇列的實作和堆疊一樣,有兩種方案:
- 基于陣列實作
- 基于鏈表實作
function Queue() {
//屬性
this.items = []
}
四.佇列的常見操作
- 佇列有哪些常見的操作呢?
- enqueue(element):向佇列尾部添加一個(或多個)新的項，
- dequeue()∶移除佇列的第一(即排在佇列最前面的)項，并回傳被移除的元素，
- front():回傳佇列中第一個元素——最先被添加，也將是最先被移除的元素，佇列不做任何變動（不移除元素，只回傳元素資訊——與Stack類的peek方法非常類似)，
- isEmpty):如果佇列中不包含任何元素，回傳true，否則回傳false，
- size():回傳佇列包含的元素個數，與陣列的length屬性類似，
- toString():將佇列中的內容,轉成字串形式
- 現在，,我們來實作這些方法.
- 其實很堆疊中方法的實作非常相似.因為我們的佇列也是基于陣列的
//1.將元素加入到佇列中
Queue.prototype.enqueue = function (element) {
this.items.push(element)
}
//2.從佇列中洗掉前端元素
Queue.prototype.dequeue = function () {
return this.items.shift()
}
//3.查看前端元素
Queue.prototype.front = function () {
return this.items[0]
}
//4.查看佇列是否為空
Queue.prototype.isEmpty = function () {
return this.items.length === 0
}
//5.查看佇列中元素的個數
Queue.prototype.size = function () {
return this.items.length
}
//6.toString方法
Queue.prototype.toString = function () {
let resultString = ''
for (let i = 0; i < this.items.length; i++) {
resultString += this.items[i] + ''
}
return resultString
}
五.擊鼓傳花
-
擊鼓傳花是一個常見的面試演算法題.使用佇列可以非常方便的實作最終的結果.
-
原游戲規則:
- 班級中玩一個游戲，所有學生圍成一圈,從某位同學手里開始向旁邊的同學傳一束花.- 這個時候某個人(比如班長),在擊鼓,鼓聲停下的一顆,花落在誰手里,誰就出來表演節目.
-
修改游戲規則:
- 我們來修改一下這個游戲規則.
- 幾個朋友一起玩一個游戲,圍成一圈，開始數數,數到某個數字的人自動淘汰.
- 最后剩下的這個人會獲得勝利,請問最后剩下的是原來在哪一個位置上的人?
-
封裝一個基于佇列的函式
- 引數:所有參與人的姓名,基于的數字
- 結果:最終剩下的一人的姓名
//擊鼓傳花
function paseGame(nameList, num) {
//創建一個佇列
let queue = new Queue()
//將所有人依次加入佇列
for (let i = 0; i < nameList.length; i++) {
queue.enqueue(nameList[i])
}
//開始數數字
while (queue.size() > 1) {
//不是num的時候嗎，重新加入到佇列的末尾
//num數字之前的人重新放入到佇列的末尾
for (let i = 0; i < num - 1; i++) {
queue.enqueue(queue.dequeue())
}
//num對應的這個人直接從佇列中洗掉
queue.dequeue()
}
//獲取剩下的結果
let endName = queue.front()
console.log(endName);
return nameList.indexOf(endName)
}
paseGame(['lisi', 'zhangsan', 'fgbfd', 'tom', 'jack', 'lisa', 'ez', 'laoshu', 'jikdf', 'dsada', 'poru', 'fjds'], 6)//fgbfd
六.優先級佇列
優先級佇列的特點:
- 我們知道,普通的佇列插入一個元素,資料會被放在后端.并且需要前面所有的元素都處理完成后才會處理前面的資料.
- 但是優先級佇列,在插入一個元素的時候會考慮該數
據的優先級. - 和其他資料優先級進行比較.
- 比較完成后,可以得出這個元素在佇列中正確的位置
- 其他處理方式,和基本佇列的處理方式一樣.
優先級佇列主要考慮的問題:
- 每個元素不再只是一個資料,而且包含資料的優先級
- 在添加方式中,根據優先級放入正確的位置.
優先級佇列的應用:
- 一個現實的例子就是機場登機的順序
- 頭等艙和商務艙乘客的優先級要高于經濟艙乘客，
- 在有些國家，老年人和孕婦（或帶小孩的婦女）登機時也享有高于其他乘客的優先級，
- 另一個現實中的例子是醫院的（急診科)候診室，
- 醫生會優先處理病情比較嚴重的患者，
- 當然,一般情況下是按照排號的順序，
- 計算機中,我們也可以通過優先級佇列來重新排序佇列中任務的順序
- 比如每個執行緒處理的任務重要性不同,我們可以通過優先級的大小,來決定該執行緒在佇列中被處理的次序.
七.優先級佇列的實作
- 現優先級佇列相對佇列主要有兩方面需要考慮:
- 1)封裝元素和優先級放在一起(可以封裝一個新的建構式)
- 2)添加元素時,將新插入元素的優先級和佇列中已經存在的元素優先級進行比較,以獲得自己正確的位置.
//封裝優先級佇列
function PriorityQueue() {
//在PriorityQueue重新創建了一個類
function QueueElemnt(element, priority) {
this.element = element
this.priority = priority
}
//封裝屬性
this.items = []
//1.實作插入方法
PriorityQueue.prototype.enqueue = function (element, priority) {
//創建QueueElement物件
let queueElemnt = new QueueElemnt(element, priority)
//判斷佇列是否為空
if (this.items.length === 0) {
this.items.push(queueElemnt)
} else {
let added = false
for (let i = 0; i < this.items.length; i++) {
if (queueElemnt.priority < this.items[i].priority) {
this.items.splice(i, 0, queueElemnt)
added = true
break
}
}
if (!added) {
this.items.push(queueElemnt)
}
}
}
//2.從佇列中洗掉前端元素
PriorityQueue.prototype.dequeue = function () {
return this.items.shift()
}
//3.查看前端元素
PriorityQueue.prototype.front = function () {
return this.items[0]
}
//4.查看佇列是否為空
PriorityQueue.prototype.isEmpty = function () {
return this.items.length === 0
}
//5.查看佇列中元素的個數
PriorityQueue.prototype.size = function () {
return this.items.length
}
//6.toString方法
PriorityQueue.prototype.toString = function () {
let resultString = ''
for (let i = 0; i < this.items.length; i++) {
resultString += this.items[i] + ''
}
return resultString
}
}
// 測驗代碼
let pq = new PriorityQueue()
pq.enqueue('abc', 111)
pq.enqueue('cba', 151)
pq.enqueue('nba', 66)
pq.enqueue('wba', 856)
console.log(pq);
轉載請註明出處，本文鏈接：https://www.uj5u.com/qiye/528833.html
標籤：JavaScript