队列是一种列表,不同的是队列只能在队尾插入元素,在队首删除元素。队列用于存储按 顺序排列的数据,先进先出,这点和栈不一样,在栈中,最后入栈的元素反而被优先处 理。可以将队列想象成在银行前排队的人群,排在最前面的人第一个办理业务,新来的人 只能在后面排队,直到轮到他们为止。

队列是一种先进先出的数据结构。队列被用在很多地方,比如 提交操作系统执行的一系列进程、打印任务池等,一些仿真系统用队列来模拟银行或杂货 店里排队的顾客。

队列类的实现：

function Queue(){
	this.dataStore = [];
	this.top = 0;
	this.enqueue = enqueue;
	this.dequeue = dequeue;
	this.front = front;
	this.back = back;
	this.toString = toString;
	this.empty = empty;
}
function enqueue(element){
	this.dataStore.push(element);
}
function dequeue(){
	return this.dataStore.shift();
}
function front(){
	return this.dataStore[0];
}
function back(){
	return this.dataStore[this.dataStore.length-1];
}
function toString(){
	return this.dataStore.join("\n");
}
function empty(){
	return this.dataStore.length ? true : false;
}

队列使用示例，方块舞的舞伴分配问题。

当男男女女来到舞池,他们按照自己的性别排成两队。当舞池中有地方空出来时,选两个队列中的第一个人组成舞伴。他们身后的人各自向前移动一位,变成新的队首。当一对舞伴 迈入舞池时,主持人会大声喊出他们的名字。当一对舞伴走出舞池,且两排队伍中有任意 一队没人时,主持人也会把这个情况告诉大家。

首先我们会有一些舞者，有男有女。

var dancers = ['F Allison McMillan','M Frank Opitz','M Mason McMillan','M Clayton Ruff','F Cheryl Ferenback','M Raymond Williams','F Jennifer Ingram','M Bryan Frazer','M David Durr','M Danny Martin','F Aurora Adney'];

每个舞者都被存在一个Dancer对象中

function Dancer(name,sex){
	this.name = name;
	this.sex = sex;
}

然后按照各自性别分别排成队

function sortDancers(){
	for(var i=0,len=dancers.length;i<len;i++){
		var item = dancers[i].split(' '),
			name = item[1],
			sex = item[0];
		if(sex==='M'){
			maleDancers.enqueue(new Dancer(name,sex));
		}else{
			femaleDancers.enqueue(new Dancer(name,sex));
		}
	}
}

当舞池中有地方空出来时,选两个队列中的第一个人组成舞伴。他们身后的人各自向前移动一位,变成新的队首。当一对舞伴 迈入舞池时,主持人会大声喊出他们的名字。

function dance(){
	console.log('The dance partners are: ');
	while(!maleDancers.empty() && !femaleDancers.empty()){
		var person = maleDancers.dequeue();
		console.log('The male dancer is ',person.name);
		person = femaleDancers.dequeue();
		console.log('The female dancer is ',person.name);
	}
}

完整代码：

function Queue(){
	this.dataStore = [];
	this.top = 0;
	this.enqueue = enqueue;
	this.dequeue = dequeue;
	this.front = front;
	this.back = back;
	this.toString = toString;
	this.empty = empty;
}
function enqueue(element){
	this.dataStore.push(element);
}
function dequeue(){
	return this.dataStore.shift();
}
function front(){
	return this.dataStore[0];
}
function back(){
	return this.dataStore[this.dataStore.length-1];
}
function toString(){
	return this.dataStore.join("\n");
}
function empty(){
	return this.dataStore.length ? true : false;
}

var dancers = ['F Allison McMillan','M Frank Opitz','M Mason McMillan','M Clayton Ruff','F Cheryl Ferenback','M Raymond Williams','F Jennifer Ingram','M Bryan Frazer','M David Durr','M Danny Martin','F Aurora Adney'],
	maleDancers = new Queue(),
	femaleDancers = new Queue();

sortDancers();

dance();

if(!femaleDancers.empty()){
	console.log(femaleDancers.front().name,' is wating to dance');
}

if(!maleDancers.empty()){
	console.log(maleDancers.front().name,' is wating to dance');
}

function Dancer(name,sex){
	this.name = name;
	this.sex = sex;
}

function sortDancers(){
	for(var i=0,len=dancers.length;i<len;i++){
		var item = dancers[i].split(' '),
			name = item[1],
			sex = item[0];
		if(sex==='F'){
			maleDancers.enqueue(new Dancer(name,sex));
		}else{
			femaleDancers.enqueue(new Dancer(name,sex));
		}
	}
}

function dance(){
	console.log('The dance partners are: ');
	while(!maleDancers.empty() && !femaleDancers.empty()){
		var person = maleDancers.dequeue();
		console.log('The male dancer is ',person.name);
		person = femaleDancers.dequeue();
		console.log('The female dancer is ',person.name);
	}
}