导语
上一章程序猿日志——数据结构：栈中，介绍了栈是一种遵循后进先出的受限集合，本章探讨一下线性表中另一种受限集合——队列，队列遵循的是先进先出的原则。
目录
1. 队列
2. 优先队列
3. 循环队列
1. 队列
队列既然遵从先进先出的原则，那么所有出队操作都在最先进入队列的元素，所有入队操作都发生在队列最后一个元素后面；
数据结构：队列
//创建一个队列的类，队列遵循FIFO原则
function Queue(){
//创建一个队列
var items = []
//入队操作，每次添加向队列的最后一个元素后添加
this.enqueue = function(){
var elems = [].slice.call(arguments)
elems.map((elem)=>{
items.push(elem)
})
}
//出队操作，每次删除元素，都是删除队列的第一个元素
this.dequeue = function(){
return items.shift()
}
//返回队列的首元素
this.front = function(){
return items[0]
}
//判断是否为空队列
this.isEmpty = function(){
return items.length === 0
}
//清空队列
this.clear = function(){
items = []
}
//队列元素个数
this.size = function(){
return items.length
}
//标准输出
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. 优先队列
有时候，我们一般在排队时会遵循先到先得，但是当类似"老弱病残"等弱势群体也在队伍中时，那么他们的优先级较高，即便是“后进”也可以先得的；
数据结构：优先队列
//优先队列
//优先队列的每一个元素既包含值又包含优先级
//根据元素的优先级进行排序，优先级高者排在前面
//如果优先级的值较小的元素排在前面，叫做最小优先队列
//创建一个优先队列的类
function PriorityQueue(){
//创建一个优先队列
var items = []
//创建一个优先队列元素的类
function QueueElement(value,prior){
this.value = value
this.prior = prior
}
//入队操作,给定入队元素的的值和优先级
this.enqueue = function(value,prior){
var queueElement = new QueueElement(value,prior)
//先判断队列是否为空，若是直接入队
if(this.isEmpty()){
items.push(queueElement)
}else{
//如果队列不为空，则将该元素和队列每一个元素进行遍历比较优先级
//将该元素插入比起优先级低一位的元素之前
//设置一个状态锁，表示元素是否入列
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
}
}
//如果遍历之后发现优先级是最低，则直接push到队列最后
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(){
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
*/
循环队列
循环队列，可以看做是击鼓传花的游戏，就是给定时间，传花到下一个人手中，时间停止拿到花的人淘汰；
数据结构：循环队列
//循环队列（击鼓传花）
function hotPotato(elems,num){
var queue = new Queue()
//将给定的元素传入队列
elems.forEach((elem)=>{
queue.enqueue(elem)
})
var eliminated = ''
while(queue.size()>1){
//给定传递花的次数
for(var i=0; i<num;i++){
queue.enqueue(queue.dequeue())
}
eliminated = queue.dequeue()
console.log(`${eliminated}在击鼓传花游戏中被淘汰`)
}
//返回剩余最后一个元素
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 = []
//向队列添加1个或多个元素，注意是在队列尾部添加
this.enqueue = function(){
var elems = [].slice.call(arguments)
elems.map((item)=>{
items.push(item)
})
}
//删除队列第一个元素
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)
}
}
- 本章节介绍了数据结构中线性表的队列结构，队列也是属于一种受限的集合；
- 队列的特点的遵循先进先出的原则（FIFO），入队操作只能在队列尾部，出队操作只能在队列头部；
- 还介绍了队列的两种特殊情况，优先队列和循环队列；
本章代码push在小羊的github地址，如有需要，可以copy;
网友评论