一、隊列簡介
創(chuàng)新互聯(lián)主要從事成都網(wǎng)站制作、成都網(wǎng)站設(shè)計、網(wǎng)頁設(shè)計、企業(yè)做網(wǎng)站、公司建網(wǎng)站等業(yè)務(wù)。立足成都服務(wù)兗州,十載網(wǎng)站建設(shè)經(jīng)驗,價格優(yōu)惠、服務(wù)專業(yè),歡迎來電咨詢建站服務(wù):18980820575
隊列是是一種受限的線性表，特點(diǎn)為先進(jìn)先出（FIFO：first in first out）。
受限之處在于它只允許在表的前端（front）進(jìn)行刪除操作；在表的后端（rear）進(jìn)行插入操作；
相當(dāng)于排隊買票，先來的先買票，后來的后買票。
隊列的應(yīng)用：
打印隊列：計算機(jī)打印多個文件的時候，需要排隊打?。痪€程隊列：當(dāng)開啟多線程時，當(dāng)新開啟的線程所需的資源不足時就先放入線程隊列，等待CPU處理；
隊列類的實現(xiàn)：
隊列的實現(xiàn)和棧一樣，有兩種方案：
基于數(shù)組實現(xiàn)；基于鏈表實現(xià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方法進(jìn)行刪除
*/
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){
// 讓新插入的元素與原有元素進(jìn)行優(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.注意點(diǎn)
關(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ù)組、棧和隊列中的形式：
可以這樣想：棧結(jié)構(gòu)是頭朝下（索引值由下往上增大）的數(shù)組結(jié)構(gòu)。
以上就是本文的全部內(nèi)容，希望對大家的學(xué)習(xí)有所幫助，也希望大家多多支持創(chuàng)新互聯(lián)。
