数据结构：用JS实现队列

队列特点：遵循先进先出（FIFO）原则的一组有序的项。队列在尾部添加新元素，并从顶部移除元素。 创建队列

首先，创建一个类来表示一个队列。

function Queue () {}

同样，我们选择数组来存储队列中的元素。

var items = [];

接下来，我们考虑一下为这个队列声明哪些方法：

• enqueue(element)：向队列尾部添加一个新的项。
• dequeue()：移除队列的第一项，并返回被移除的项。
• front()：返回队列中的第一个元素，队列不做任何变动。
• isEmpty()：判断队列是否为空。
• size()：返回队列长度。

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;
	};
	this.print = function () {
		console.log(items.toString());
	};
}

嗯，我们已经算是创建一个较为完整的队列了，接下来，我再说说其它的。

优先队列

优先队列元素的添加和移除是基于优先级的。拿医院候诊室举例，医生会优先处理病情比较严重的患者。

function PriorityQueue () {
	var items = [];
	//每个元素都包含要添加到队列的元素，以及在队列中的优先级
	function QueueElement (element, priority) {
		this.element = element;
		this.priority = priority;	
	}
	this.enqueue = function () {
		var queueElement = new QueueElement(element, priority);	
		//当队列为空，直接添加
		if (this.isEmpty()) {
			items.push(queueElement);
		}else {
			var added = false;
			//循环比较所添加元素和队列中元素优先级
			//当找到比要添加元素优先级更大的项时，就把新元素插入到它之前（priority越小，优先级越高）
			//优先级相同，遵循先进先出原则
			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);
			}
		}
	}
	//其他方法和默认的Queue实现相同
}

循环队列——击鼓传花

还有一个修改版的队列实现，那就是循环队列。我们拿击鼓传花这个例子来实现循环队列。 在游戏中，孩子们围成一个圆圈，把花传给旁边的人，某一时刻传花停止，拿着花的孩子结束游戏，重复这个过程，直到剩下一个孩子（胜者）。

function hotPotato (nameList, num) {
	var queue = new Queue;
	var eliminated = "";
	for (var i = 0; i < nameList.length; i++) {
		queue.enqueue(nameList[i]);//将玩游戏孩子名字加入队列
	}
	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 names = ["小明", "小花", "小黄", "小易", "小华"];
var winner = hotPotato(names, 5);//可以改变传入数字，模拟不同场景
console.log("胜利者：" + winner);

控制台模拟结果如图：