优先级队列

概念

在计算机科学中, 优先级队列(priority queue) 是一种抽象数据类型, 它类似于常规的队列或栈, 但每个元素都有与之关联的“优先级”。

在优先队列中, 低优先级的元素之前前面应该是高优先级的元素。 如果两个元素具有相同的优先级, 则根据它们在队列中的顺序是它们的出现顺序即可。

优先队列虽通常用堆来实现,但它在概念上与堆不同。优先队列是一个抽象概念，就像“列表”或“图”这样的抽象概念一样;

正如列表可以用链表或数组实现一样，优先队列可以用堆或各种其他方法实现,例如无序数组。

特点

普通队列插入一个元素，数据会被放在末尾，并且需要前面的所有元素都处理完后才会处理前面的数据，但是优先级队列，在插入一个元素的时候会考虑该数据的优先级。

和其他数据优先级进行比较。比较完后，可以得出这个元素在队列中的正确位置。

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

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

基于数组实现

  // 优先级队列
  class QueueElement {
	  constructor(element, priority) {
		  this.element = element
		  this.priority = priority
	  }
  }

  class PriorityQueue {
	  constructor() {
		  this.items = []
	  }
	  // 1.插入数据
	  enqueue(element, priority) {
		  // 1.1创建 QueueElement
		  const queueElement = new QueueElement(element, priority)
		  // 1.2判断队列是否为空
		  if (this.isEmpty()) {
			  this.items.push(queueElement)
		  } else {
			  let added = false
			  // array.splice(starti, n, 值1, 值2)
			  // starti 指的是从哪个位置开始(不包含starti)
			  // n 为 0 删除 0个 即插入数据
			  // n 不为 0 表示修改或者替换数据
			  for (let 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)
			  }
		  }
	  }
	  // 2.从队列中删除前端的元素
	  dequeue() {
		  return this.items.shift() // 删除第一个元素
	  }
	  // 3.查看队列前端的元素
	  front() {
		  return this.items[0]
	  }
	  // 4.查看队列是否为空
	  isEmpty () {
		  return this.items.length === 0
	  }
	  // 5.查看队列中元素的个数
	  size() {
		  return this.items.length
	  }
	  // 6.toString 方法
	  toString() {
		  let resultString = ''
		  for (let i = 0; i < this.items.length; i++) {
			  resultString += this.items[i] + ''
		  }
		  return resultString
	  }
  }


  let pq = new PriorityQueue()
  pq.enqueue('A', 1)
  pq.enqueue('D', 12)
  pq.enqueue('D2', 132)
  pq.enqueue('D3', 9)
  console.log(pq, 'pq000')

代码实现

队列、栈和数组