JavaScript 数据结构与算法（二）队列

一种受限的线性结构

队列的应用

线程队列

让任务并行处理,通常开启多个线程, 但是不能大量的线程同时运行(占用过多资源)这个时候, 我们就会使用线程队列, 按照次序来启动线程

队列的实现（基于数组）

属性： items=[]

方法：

enqueue (element)

向队列尾部添加一个或多个元素 dequeue()

移除队列第一个元素,并返回被移除的元素 front()

返回队列第一个元素 类似 Stack.peek() isEmplty()

空 true 否则 false size()

返回队列包含的元素个数 toString()

返回字符串

代码：

class Queue {
  items = []
  enqueue = (element) => {
    this.items.push(element)
  }
  dequeue = () => {
    return this.items.shift()
  }
  front = () => {
    return this.items[0]
  }
  isEmpty = () => {
    return this.items.length === 0
  }
  size = () => {
    return this.items.length - 1
  }
  toString = () => {
    let res = ""
    for (const i in this.items) {
      res += i === this.items.length - 1 ? this.items[i] : this.items[i] + " "
    }
    return res
  }
}

队列的应用

击鼓传花（面试题）

给定人数和一个数字，所有人轮流喊数字，喊到对应的数字的人淘汰，直到剩下最后一个人，求一个能够胜利的位置。

题解：

将人抽象为队列,删除对应数字的人,其余人重新加入队列

const passGame = (nameList, num) => {
  // 1. 创建一个队列
  let queue = new Queue()
  // 2. 将所有人加入队列中
  for (const i in nameList) {
    queue.enqueue(nameList[i])
  }
  // 3.不是num的重新加入队列,是num的从队列中删除
  while (queue.size() > 1) {
    for (let i = 0; i < num - 1; i++) {
      // 3.1 不是num的人重新加入队列
      queue.enqueue(queue.dequeue())
    }
    // 3.2 删除对应num的人
    queue.dequeue()
  }
  return queue.front()
}

​

特点: 考虑插入元素的优先级

每个元素不仅是一个数据,还包含数据的优先级根据优先级放入正确位置

应用:

每个线程处理的任务重要性不同, 通过优先级大小来决定被处理的次序

实现:

除了添加元素的时候需要考虑优先级，其余操作与普通队列一致

封装数据类型QueueElement(){this.element, this.priority}

代码：

// 封装优先级队列
function PriorityQueue() {
  function QueueElement(element, priority) {
    this.element = element
    this.priority = priority
  }
  this.items = []

  PriorityQueue.prototype.enqueue = (element, priority) => {
    // 1. 创建QueueElement对象
    let queueElement = new QueueElement(element, priority)

    // 2. 判断队列是否为空
    if (this.items.length === 0) {
        // 如果队列空,就直接push进去
      this.items.push(queueElement)
    } 
    // 非空,遍历队列, 对比 新元素的优先级和已有元素的优先级(数值小的优先级高)
    for (let i in this.items) {
        if (queueElement.priority < this.items[i].priority) {
            // 插入当前位置, 并将已添加的标志位置1
          this.items.splice(i, 0, queueElement)
          added = true
          break
        }
      }
        // 如果优先级最低,那么将push到末尾
      if (!added) {
        this.items.push(queueElement)
      }    
  }
  PriorityQueue.prototype.dequeue = () => {
    return this.items.shift()
  }
  PriorityQueue.prototype.front = () => {
    return this.items[0]
  }
  PriorityQueue.prototype.isEmpty = () => {
    return this.items.length === 0
  }
  PriorityQueue.prototype.size = () => {
    return this.items.length
  }
  PriorityQueue.prototype.toString = () => {
    let res = ""
    for (const i in this.items) {
      res += i === this.items.length - 1 ? this.items[i] : this.items[i] + " "
    }
    return res
  }
}
// 测试
let pq = new PriorityQueue()
pq.enqueue(22, 200)
pq.enqueue(22, 20)
pq.enqueue(22, 2)
pq.enqueue(22, 0)
console.log(pq)
pq.dequeue()
console.log(pq)