队列

TIP

队列（Queue），是一种受限的线性结构，特点是先进先出（FIFO：first in first out）

基本特点

• 受限表现：仅允许在表的前端（front）进行删除操作，在表的后端（rear）进行插入操作

结构图例

常用操作

• enqueue(element)：向队列尾部添加一个（或多个）新的项
• dequeue()：移除队列的第一（即排在队列最前面的）项，并返回被移除的元素
• front()：返回队列中的第一个元素——最先被添加，也将是最先被移除的元素。队列不做任何变动（不移除元素）
• isEmpty()：如果队列中不包含任何元素，返回 true，否则返回 false
• size()：返回队列包含的元素个数，与数组的 length 属性类似
• toString()：将队列中的内容，转成字符串形式

代码实现

// 普通队列
function Queue() {
	var items = []

	/* 队列操作的方法 */
	// 1.enqueue()：将元素加入到队列中
	this.enqueue = function(element) {
		items.push(element)
	}

	// 2.dequeue()：从队列中删除前端元素
	this.dequeue = function() {
		return items.shift()
	}

	// 3.front(): 查看前端的元素
	this.front = function() {
		return items[0]
	}

	// 4.isEmpty(): 查看队列是否为空
	this.isEmpty = function() {
		return items.length == 0
	}

	// 5.size(): 查看队列中元素的个数
	this.size = function() {
		return items.length
	}

	// 6.toString(): 将队列中元素以字符串形式输出
	this.toString = function() {
		var resultString = ""
		for (let i = 0; index < this.items.length; index++) {
			resultString += this.items[index] + " "
		}
		return resultString
	}
}

// 创建队列对象
var queue = new Queue()

// 在队列中添加元素
queue.enqueue("a")
queue.enqueue("b")
queue.enqueue("c")

// 查看一下队列前端元素
console.log(queue.front()) // a

// 查看队列是否为空和元素个数
console.log(queue.isEmpty()) // false
console.log(queue.size()) // 3

// 从队列中删除元素
console.log(queue.dequeue()) // a
console.log(queue.dequeue()) // b
console.log(queue.dequeue()) // c

队列应用-击鼓传花

击鼓传花：传入一组数据和设定的数字 num，循环遍历数组内元素，遍历到的元素为指定数字 num 时将该元素删除，直至数组剩下一个元素

// 面试题：实现击鼓传花的函数
function passGame(nameList, num) {
	// 1.创建一个队列, 并且将所有的人放在队列中
	// 1.1.创建队列
	var queue = new Queue()

	// 1.2.通过for循环, 将nameList中的人放在队列中
	for (var i = 0; i < nameList.length; i++) {
		queue.enqueue(nameList[i])
	}

	// 2.寻找最后剩下的人
	while (queue.size() > 1) {
		// 不是num的时候，重新加入到队列的末尾
		// 是num这个数字的时候，从队列中删除
		// 将前num-1中的人, 都从队列的前端取出放在队列的后端
		for (var i = 0; i < num - 1; i++) {
			queue.enqueue(queue.dequeue())
		}

		// 将第num个人, 从队列中移除(num变为第一个了)
		queue.dequeue()
	}

	// 3.获取剩下的一个人
	console.log("最后队列长度：" + queue.size()) // 1
	var endName = queue.front()
	console.log("最终留下来的人:" + endName) // Ingrid

	// 4.获取该人在队列中的位置
	return nameList.indexOf(endName)
}

// 验证结果
var names = ["John", "Jack", "Camila", "Ingrid", "Carl"]
var index = passGame(names, 7)
console.log("最终位置:" + index) // 3

优先级队列

特点

• 每个元素不再只是一个数据，还包含数据的优先级
• 插入数据的时候，会和其他数据比较优先级，然后根据优先级插入到正确的位置

代码实现

// 封装优先级队列
function PriorityQueue() {
	// 内部类：封装一个新的构造函数, 用于保存元素和元素的优先级
	function QueueElement(element, priority) {
		this.element = element
		this.priority = priority
	}

	// 封装属性
	var items = []

	// 1.enqueue(): 实现按照优先级插入方法
	this.enqueue = function(element, priority) {
		// 1.1 根据传入的元素, 创建新的QueueElement
		var queueElement = new QueueElement(element, priority)

		// 1.2 判断队列是否为空
		if (this.isEmpty()) {
			// 如果为空就直接放入队列
			items.push(queueElement)
		} else {
			// 定义一个变量记录是否成功添加了新元素
			var added = false
			for (var i = 0; i < items.length; i++) {
				// // 让新插入的元素与原有元素进行优先级比较(priority越小，优先级越大)
				if (queueElement.priority < items[i].priority) {
					items.splice(i, 0, queueElement)
					added = true
					// 新元素已经找到插入位置了可以使用break停止循环
					break
				}
			}

			// 遍历完所有的元素, 优先级都大于新插入的元素时, 就插入到最后
			if (!added) {
				items.push(queueElement)
			}
		}
	}

	// 2.dequeue(): 从队列中删除前端元素
	this.dequeue = function() {
		return items.shift()
	}

	// 3.front(): 查看前端的元素
	this.front = function() {
		return items[0]
	}

	// 4.isEmpty(): 查看队列是否为空
	this.isEmpty = function() {
		return items.length == 0
	}

	// size(): 查看队列中元素的个数
	this.size = function() {
		return items.length
	}

	// 6.toString():以字符串形式输出队列中的元素
	PriorityQueue.prototype.toString = () => {
		let resultString = ""
		for (let i = 0; i < items.length; i++) {
			resultString += items[i].element + "-" + items[i].priority + " "
		}
		return resultString
	}
}

// 创建优先级队列对象
var pQueue = new PriorityQueue()

// 添加元素
pQueue.enqueue("abc", 10)
pQueue.enqueue("cba", 5)
pQueue.enqueue("nba", 12)
pQueue.enqueue("mba", 3)

// 遍历所有的元素
console.log(pQueue.toString()) // mba-3 cba-5 abc-10 nba-12