導(dǎo)語(yǔ)
上一章程序猿日志——數(shù)據(jù)結(jié)構(gòu)：棧中劫狠，介紹了棧是一種遵循后進(jìn)先出的受限集合题暖，本章探討一下線性表中另一種受限集合——隊(duì)列疏魏，隊(duì)列遵循的是先進(jìn)先出的原則。
目錄
1. 隊(duì)列
2. 優(yōu)先隊(duì)列
3. 循環(huán)隊(duì)列
1. 隊(duì)列
隊(duì)列既然遵從先進(jìn)先出的原則科贬，那么所有出隊(duì)操作都在最先進(jìn)入隊(duì)列的元素，所有入隊(duì)操作都發(fā)生在隊(duì)列最后一個(gè)元素后面鳖悠；
數(shù)據(jù)結(jié)構(gòu)：隊(duì)列
//創(chuàng)建一個(gè)隊(duì)列的類榜掌，隊(duì)列遵循FIFO原則
function Queue(){
//創(chuàng)建一個(gè)隊(duì)列
var items = []
//入隊(duì)操作，每次添加向隊(duì)列的最后一個(gè)元素后添加
this.enqueue = function(){
var elems = [].slice.call(arguments)
elems.map((elem)=>{
items.push(elem)
})
}
//出隊(duì)操作乘综，每次刪除元素憎账，都是刪除隊(duì)列的第一個(gè)元素
this.dequeue = function(){
return items.shift()
}
//返回隊(duì)列的首元素
this.front = function(){
return items[0]
}
//判斷是否為空隊(duì)列
this.isEmpty = function(){
return items.length === 0
}
//清空隊(duì)列
this.clear = function(){
items = []
}
//隊(duì)列元素個(gè)數(shù)
this.size = function(){
return items.length
}
//標(biāo)準(zhǔn)輸出
this.print = function(){
console.log(items)
}
}
var queue = new Queue()
queue.enqueue(1,2,3,4,5)
queue.print()//[1,2,3,4,5]
queue.dequeue()//2
queue.print()//[2,3,4,5]
console.log(queue.front())//2
console.log(queue.size())//4
2. 優(yōu)先隊(duì)列
有時(shí)候，我們一般在排隊(duì)時(shí)會(huì)遵循先到先得卡辰，但是當(dāng)類似"老弱病殘"等弱勢(shì)群體也在隊(duì)伍中時(shí)胞皱，那么他們的優(yōu)先級(jí)較高，即便是“后進(jìn)”也可以先得的九妈；
數(shù)據(jù)結(jié)構(gòu)：優(yōu)先隊(duì)列
//優(yōu)先隊(duì)列
//優(yōu)先隊(duì)列的每一個(gè)元素既包含值又包含優(yōu)先級(jí)
//根據(jù)元素的優(yōu)先級(jí)進(jìn)行排序反砌，優(yōu)先級(jí)高者排在前面
//如果優(yōu)先級(jí)的值較小的元素排在前面，叫做最小優(yōu)先隊(duì)列
//創(chuàng)建一個(gè)優(yōu)先隊(duì)列的類
function PriorityQueue(){
//創(chuàng)建一個(gè)優(yōu)先隊(duì)列
var items = []
//創(chuàng)建一個(gè)優(yōu)先隊(duì)列元素的類
function QueueElement(value,prior){
this.value = value
this.prior = prior
}
//入隊(duì)操作,給定入隊(duì)元素的的值和優(yōu)先級(jí)
this.enqueue = function(value,prior){
var queueElement = new QueueElement(value,prior)
//先判斷隊(duì)列是否為空允蚣，若是直接入隊(duì)
if(this.isEmpty()){
items.push(queueElement)
}else{
//如果隊(duì)列不為空于颖，則將該元素和隊(duì)列每一個(gè)元素進(jìn)行遍歷比較優(yōu)先級(jí)
//將該元素插入比起優(yōu)先級(jí)低一位的元素之前
//設(shè)置一個(gè)狀態(tài)鎖，表示元素是否入列
var added = false
for(var i = 0; i<items.length;i++){
if(queueElement.prior<items[i].prior){
items.splice(i,0,queueElement)
added = true
break
}
}
//如果遍歷之后發(fā)現(xiàn)優(yōu)先級(jí)是最低嚷兔，則直接push到隊(duì)列最后
if(!added){
items.push(queueElement)
}
}
}
//出隊(duì)操作森渐，一樣是隊(duì)列的首元素先出
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(){
items.forEach((item)=>{
console.log(`value: ${item.value},prior: ${item.prior}\n`)
})
// console.log(items)
}
}
var priorQueue = new PriorityQueue()
priorQueue.enqueue('foo',2)
priorQueue.enqueue('bar',1)
priorQueue.enqueue('baz',3)
priorQueue.print()
/*
value: bar, prior: 1
value: foo, prior: 2
value: baz, prior: 3
*/
循環(huán)隊(duì)列
循環(huán)隊(duì)列做入，可以看做是擊鼓傳花的游戲，就是給定時(shí)間同衣，傳花到下一個(gè)人手中竟块，時(shí)間停止拿到花的人淘汰；
數(shù)據(jù)結(jié)構(gòu)：循環(huán)隊(duì)列
//循環(huán)隊(duì)列（擊鼓傳花）
function hotPotato(elems,num){
var queue = new Queue()
//將給定的元素傳入隊(duì)列
elems.forEach((elem)=>{
queue.enqueue(elem)
})
var eliminated = ''
while(queue.size()>1){
//給定傳遞花的次數(shù)
for(var i=0; i<num;i++){
queue.enqueue(queue.dequeue())
}
eliminated = queue.dequeue()
console.log(`${eliminated}在擊鼓傳花游戲中被淘汰`)
}
//返回剩余最后一個(gè)元素
return queue.dequeue()
}
var elems = ['foo','bar','baz','hub']
var winner = hotPotato(elems,8)
console.log(`勝利者：${winner}`)
/*
foo在擊鼓傳花游戲中被淘汰
hub在擊鼓傳花游戲中被淘汰
bar在擊鼓傳花游戲中被淘汰
勝利者：baz
*/
function Queue(){
var items = []
//向隊(duì)列添加1個(gè)或多個(gè)元素耐齐，注意是在隊(duì)列尾部添加
this.enqueue = function(){
var elems = [].slice.call(arguments)
elems.map((item)=>{
items.push(item)
})
}
//刪除隊(duì)列第一個(gè)元素
this.dequeue = function(){
return items.shift()
}
//返回隊(duì)列的第一個(gè)元素
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)
}
}
- 本章節(jié)介紹了數(shù)據(jù)結(jié)構(gòu)中線性表的隊(duì)列結(jié)構(gòu)浪秘，隊(duì)列也是屬于一種受限的集合；
- 隊(duì)列的特點(diǎn)的遵循先進(jìn)先出的原則（FIFO）埠况，入隊(duì)操作只能在隊(duì)列尾部耸携，出隊(duì)操作只能在隊(duì)列頭部；
- 還介紹了隊(duì)列的兩種特殊情況辕翰，優(yōu)先隊(duì)列和循環(huán)隊(duì)列夺衍；
本章代碼push在小羊的github地址，如有需要喜命，可以copy;
