队列-js实现

队列是遵循FIFO（First In First Out）原则的一组有序的项（也称为先来先服务）。队列在尾部添加新元素，从顶部移除元素。最新添加的元素总是在队尾。

申明一个队列的类：

function Queue(){
	var items = [];
}

和栈类似，用存储队列的数据结构采用数组。

需要实现的方法列表：

• inQueue(element(s))：向队列尾部添加一个或多个项。
• outQueue()：移除队列顶部的一个元素，并返回这个元素。
• front()：返回队列里面最前面的一个元素，也就是队列顶部的元素。
• isEmpty()：判断队列是否为空，并返回true或false。
• size()：返回队列包含的元素个数，同数组的length类似。

普通队列

inQueue方法，进队

inQueue方法，将元素进队，这里进入的是队列的尾部。用数组的push方法。

this.inQueue = function(element) {
	items.push(element);
};

outQueue方法，出队

outQueue方法为出队，按照先进先出的规则，出队的是最先添加的，也就是队列顶部的元素，用数组的shift方法。

this.outQueue = function() {
	return items.shift();
};

front\isEmpty\size\clear\print，辅助方法

front方法用来告诉用户队列的顶部的元素是啥。

this.front = function() {
	return items[0];
};

isEmpty判断队列是否为空。

this.isEmpty = function() {
	return items.length == 0;
}

size返回队列的长度。

this.size = function() {
	return items.length;
}

clear清空队列。

this.clear = function() {
	items = [];
};

print打印队列。

this.print = function() {
	return items.toString();
};

队列类的总览：

function Quene(){

	var items = [];
	
	this.inQueue = function(element) {
		items.push(element);
	};

	this.outQueue = function() {
		return items.shift();
	};

	this.front = function() {
		return items[0];
	};

	this.isEmpty = function() {
		return items.length == 0;
	};

	this.size = function() {
		return items.length;
	};

	this.clear = function() {
		items = [];
	};

	this.print = function() {
		console.log(items);
	};

}

实例：

var people = ['tony', 'michael', 'jack', 'jenny'];
var queue = new Quene();
people.map(function(item) {
	queue.inQueue(item);
});
queue.print(); // [ 'tony', 'michael', 'jack', 'jenny' ]
queue.outQueue();
queue.print(); // [ 'michael', 'jack', 'jenny' ]

特殊队列

优先队列

实现一个优先队列，有两种方式：设置优先级，然后在正确的位置添加元素；或者用入列操作添加元素，然后按照优先级移除他们。

通过改写队列的入队方法，使队列变换为优先队列：

// 带优先级的队列
function QueueElement(element, priority) {
	this.element = element;
	this.priority = priority;
}

this.inQueue = function(element, priority) {
	var queueElement = new QueueElement(element, priority);
	if (this.isEmpty()) {
		items.push(queueElement);
	} else {
		var added = false;
		for (var i = 0; i < items.length; i++) {
			if (queueElement.priority < items[i].priority) {
				items.splice(i, 0, queueElement);
				added = true;
				break;
			}
		}
		if (!added) {
			items.push(queueElement);
		}
	}
}

核心思想：将队列的数据结构由一维的数组变换为对象数组，每个对象除了本身的值之外，添加一个权重（priority），优先级高的插队到前面。否则就排到队尾。
例如：

var people = [
	{
		element: 'tony',
		priority: 3,
	},
	{
		element: 'michael',
		priority: 2,
	},
	{
		element: 'jack',
		priority: 4,
	},
	{
		element: 'jenny',
		priority: 1,
	},
];
var queue = new Quene();
people.map(function(item) {
	queue.inQueue(item.element, item.priority);
})
queue.print();
// 输出结果为：
[ QueueElement { element: 'jenny', priority: 1 },
  QueueElement { element: 'michael', priority: 2 },
  QueueElement { element: 'tony', priority: 3 },
  QueueElement { element: 'jack', priority: 4 } ]

循环队列，击鼓传花

游戏规则是，有限的人数围成一个圈，把花传给另一个人，某一个时刻，传递停止，花在谁手谁就退出游戏，循环操作，直到剩下最后一个人，就是胜者。用循环队列模拟这个过程。

function hotPotato(nameList, num) {
	var queue = new Queue();
	for (var i = 0; i < nameList.length; i++) {
		queue.inQueue(nameList[i]);
	}

	var eliminated = '';
	while (queue.size() > 1) {
		for (var i = 0; i < num; i++) {
			queue.inQueue(queue.outQueue());
		}
		eliminated = queue.outQueue();
		console.log(eliminated + ' is out!');
	}
	return queue.outQueue();
}

核心思想：先将一群人入队，然后循环传花知道剩余最后一个人，传花的过程中不断的出队入队，模拟循环队列，然后循环完毕的时候代表传花停止。这时候，队列顶部的人为淘汰的人。
示例：

var people = ['tony', 'michael', 'jack', 'jenny'];
var winner = hotPotato(people, 5);
console.log(winner + ' is winner');
// 输出
michael is out!
tony is out!
jenny is out!
jack is winner