本文共 2297 字，大约阅读时间需要 7 分钟。

一.队列

• 特性：先进先出
• 在后端添加数据，在前端删除数据
• 常见应用场景：打印机、线程工作

二.队列的实现

队列类的创建：基于数组和基于链表

以下是基于数组实现的：

function Queue(){   	//属性	this.items = []	//方法	// 1.将元素加入到队列中	Queue.prototype.enqueue() = function(element){    		this.items.push(element)	}	// 2.从队列中删除前端元素	Queue.prototype.dequeue() = function(){   		return this.items.shift()	}	// 3.查看前端的元素	Queue.prototype.front() = function(){   		return this.items[0]	}	// 4.查看队列是否为空	Queue.prototype.isEmpty() = function(){   		return this.items.length == 0	}	// 5.查看队列中元素的个数	Queue.prototype.size() = function(){   		return this.items.length	}	// 6.toString方法	Queue.prototype.toString() = function(){   		var resultString = ''		for(var i = 0;i < this.items.length; i++){   		resultString += this.items[i] + ' '	}		return resultString	}}//使用队列var queue = new Queue()queue.enqueue('abc')

三.队列的实例（面试题）

击鼓传花：几个朋友一起玩游戏，大家围成一个圈，开始数数，当数到某个固定数的人将自动淘汰。接着剩下的人从1开始重新玩游戏，当再次数到该数字时，对应的人继续淘汰，当最后只剩下一个人时，即为获胜，请问最后剩下的人是原来在哪个位置的人？

 function passGame(nameList,num){    	//1.创建一个队列结构 	var queue = new Queue()	//2.将所有人依次加入到队列中	for(var i = 0; i < nameList.length; i++){   		queue.enqueue(nameList[i])	}	//3.开始数数字	while(queue.size() > 1){   		//当不是num时，将头部的元素重新加入到队列尾部		//是num时，将其从队列中删除		//3.1 num数字之前的人重新放到队列的尾部		for(var i = 0; i < num - 1; i++){   			queue.enqueue(queue.dequeue())		}		// 3.2 num对应的这个人，直接从队列中删除		queue.dequeue()	}	// 4.获取剩下的那个人	var endName = queue.front()	return nameList.indexOf(endName) } // 测试击鼓传花passGame()

四.优先级队列

特点：

• 优先级队列再插入元素时会考虑该数据的优先级
• 和其他数据优先级进行比较，比较完成后，可以得出这个元素在队列中正确的位置

优先级队列主要考虑的问题

• 每个元素不再只是一个数据，而是包含数据的优先级
• 在添加方式中，根据优先级放入正确的位置

场景应用：

• 机场登机：头等舱优先，老人/孕妇优先级高于其他乘客
• 急诊科：优先处理病情较为严重的患者

function priorityQueue() {   	//在priorityQueue中额外创建了一个类：可以理解为内部类	function QueueElement(element,priority) {   		this.element = element		this.priority = priority	}	// 封装属性	this.items = []		//实现插入方法	priorityQueue.prototype.enqueue = function(element,priority){   		//1.创建QueueElement对象		var queueElement = new QueueElement(element,priority)		//2.判断队列是否为空		if(this.items.length == 0){   			this.items.push(queueElement)		} else {   			var added = false			for(var i = 0; i < this.items.length ; i++){   				if(queueElement.priority < this.items[i].priority){   					this.items.splice(i,0,queueElement)					added = true					break				}			}			if(!added){   				this.items.push(queueElement)			}		}	}}

转载地址：http://shze.baihongyu.com/