队列结构

[conan1992]

队列结构

队列(Queue)，它是一种运算受限的线性表,先进先出(FIFO First In First Out)

• 队列是一种受限的线性结构
• 受限之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作

代码实现

操作方法

• enqueue(element)：向队列尾部添加一个（或多个）新的项。
• dequeue()：移除队列的第一（即排在队列最前面的）项，并返回被移除的元素。
• front()：返回队列中第一个元素——最先被添加，也将是最先被移除的元素。队列不做任何变动（不移除元素，只返回元素信息——与Stack类的peek方法非常类似）。
• isEmpty()：如果队列中不包含任何元素，返回true，否则返回false。
• size()：返回队列包含的元素个数，与数组的length属性类似。

代码实现

function Queue(){
	var 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
	}
}

优先级队列

• 普通的队列插入一个元素, 数据会被放在后端. 并且需要前面所有的元素都处理完成后才会处理前面的数据.
• 但是优先级队列, 在插入一个元素的时候会考虑该数据的优先级.(和其他数据优先级进行比较)
• 比较完成后, 可以得出这个元素正确的队列中的位置. 其他处理方式, 和队列的处理方式一样.
• 也就是说, 如果我们要实现优先级队列, 最主要是要修改添加方法. (当然, 还需要以某种方式来保存元素的优先级)

代码实现

• 装元素和优先级放在一起(可以封装一个新的构造函数)
• 添加元素时, 将当前的优先级和队列中已经存在的元素优先级进行比较, 以获得自己正确的位置

function PriorityQueue(){
	var items = [];
	var QueueElement = function(element, priority){
		this.element = element;
		this.priority = priority;
	}
	this.enqueue = function(element, priority){
		var queueElement = new QueueElement(element, priority)
		if(this.isEmpty()){
			items.push(queueElement)
		}else{
			var flag = false;
			for(var i=0;i<this.size();i++){
				if(queueElement.priority<items[i].priority){
					items.splice(i, 0, queueElement);
					flag = true;
					break
				}
			}
			if(!flag){
				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
	}
}

应用

击鼓传花的规则
原游戏规则:
班级中玩一个游戏, 所有学生围成一圈, 从某位同学手里开始向旁边的同学传一束花.
这个时候某个人(比如班长), 在击鼓, 鼓声停下的一颗, 花落在谁手里, 谁就出来表演节目.
修改游戏规则:
我们来修改一下这个游戏规则.
几个朋友一起玩一个游戏, 围成一圈, 开始数数, 数到某个数字的人自动淘汰.
最后剩下的这个人会获得胜利, 请问最后剩下的是原来在哪一个位置上的人?

function Queue(){
	var 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
	}
}
//实现击鼓传花的函数
function passGame(nameList, num) {
    var queue = new Queue();
    for(var i=0;i<nameList.length;i++){
    	queue.enqueue(nameList[i])
    }
    
    while(queue.size>1){
    	for(var i=1;i<num;i++){
    		queue.enqueue(queue.dequeue())
    	}
    	queue.dequeue()
    }
    return queue.front() + " 所处位置： "+ (nameList.indexOf(queue.front())+1)
}
//验证结果
var names = ['John','Jack','Camila','Ingrid','Carl'];
var index = passGame(names, 8) // 数到8的人淘汰
console.log( index)

参考链接

• 数据结构(四)之队列结构