周亚博的个人博客

  • 首页
  • 盛夏光年
  • 陪风去荡
  • 布响丸啦
我频繁记录着 因为生活值得
  1. 首页
  2. 陪风去荡
  3. 正文

数据结构——队列

2022-08-11 84点热度 0人点赞 0条评论

一、什么是队列结构

队列结构(Queue)是另一种受限的数据结构,他是一种受限的线性表,先进先出(FIFO First In First Out)

  • 只允许在表的前端(font)进行删除操作
  • 在表的后端(rear)进行插入操作

图解:

image-20220811154346557

二、队列结构的实现

队列的实现和栈一样,有两种方案:

  • 基于数组实现
  • 基于链表实现
/**
 * 封装一个队列类
*/

function Queue() {
  // 属性
  this.items = []

  // 元素进入队列
  Queue.prototype.enqueue = function (element) {
    this.items.push(element)
  }
  // 移除队列第一项,并返回数据
  Queue.prototype.dequeue = function () {
    return this.items.shift()
  }
  // 返回队列第一项数据
  Queue.prototype.front = function () {
    return this.items[0]
  }
  // 判断队列是否为空
  Queue.prototype.isEmpty = function () {
    return this.items.length == 0
  }
  // 返回队列的元个数
  Queue.prototype.size = function () {
    return this.items.length
  }
  // toString方法
  Queue.prototype.toString = function () {
    let str = ''
    for (let i = 0; i < this.items.length; i++) {
      str += this.items[i] + ' '
    }
    return str
  }

}

let queue = new Queue()
queue.enqueue('a')
queue.enqueue('b')
queue.enqueue('c')
queue.enqueue('d')
console.log(queue)  // Queue { items: [ 'a', 'b', 'c', 'd' ] }
queue.dequeue()
queue.dequeue()
console.log(queue)  // Queue { items: [ 'c', 'd' ] }
console.log(queue.front())  // c
console.log(queue.isEmpty())  // false
console.log(queue.size())   // 2

三、面试题

击鼓传花的实现

/**
 * 一群人从一开始读到特定的数字淘汰,返回最后一个人
*/
function gameOut(nameList, num) {
  // 创建一个队列结构
  let queue = new Queue()
  // 将人添加到队列中
  for (let i = 0; i < nameList.length; i++) {
    queue.enqueue(nameList[i])
  }
  while (queue.size() > 1) {
    // 开始数数字,不是对应数字则添加到队列末尾,是则移出队列
    for (let i = 0; i < num - 1; i++) {
      queue.enqueue(queue.dequeue())
    }
    queue.dequeue()
  }
  // 获取仅剩的人
  let successName = queue.front()
  return successName
}

console.log(gameOut(['张三', '李四', '王五'], 2)) // 王五
console.log(gameOut(['Monkey', 'Lucy', 'Tom', 'Lilei', 'Wang'], 3)) // Lilei

四、优先级队列

普通队列插入元素,数据会被放入后端,等待前端数据处理完毕才会处理

优先级队列插入元素会考虑数据的优先级,进行比较后会得出正确的位置

  • 每个数据不仅仅是一个数据,还有数据的优先级
  • 添加方式中,根据优先级将数据放入正确的位置

优先级队列的封装:

/**
 * 封装一个优先级队列,使用数字代表优先级
*/

// 规定数据越小,优先级越高
function PriorityQueue() {
  // 内部类,保存数据和优先级
  function QueueElement(element, priority) {
    this.element = element
    this.priority = priority
  }
  // 使用属性保存数据
  this.items = []

  // 实现插入方法
  PriorityQueue.prototype.enqueue = function (element, priority) {
    // 创建QueueElement对象
    let queueElement = new QueueElement(element, priority)
    // 判断队列是否为空
    if (this.items.length == 0) {
      this.items.push(queueElement)
    } else { // 不为空,从最大优先级开始比较
      let flag = false
      for (let i = 0; i < this.items.length; i++) {
        if (queueElement.priority < this.items[i].priority) {
          this.items.splice(i, 0, queueElement) // 前方插入
          flag = true
          break  // 跳出循环
        }
      }

      if (!flag) { // 比较完毕,优先级是最小的,直接放到最后
        this.items.push(queueElement)
      }
    }
  }

  // 移除队列第一项,并返回数据
  PriorityQueue.prototype.dequeue = function () {
    return this.items.shift()
  }
  // 返回队列第一项数据
  PriorityQueue.prototype.front = function () {
    return this.items[0]
  }
  // 判断队列是否为空
  PriorityQueue.prototype.isEmpty = function () {
    return this.items.length == 0
  }
  // 返回队列的元个数
  PriorityQueue.prototype.size = function () {
    return this.items.length
  }
  // toString方法
  PriorityQueue.prototype.toString = function () {
    let str = ''
    for (let i = 0; i < this.items.length; i++) {
      str += this.items[i].element + ':' + this.items[i].priority + ' '
    }
    return str
  }
}

let pq = new PriorityQueue()
pq.enqueue('吃饭', 10)
pq.enqueue('睡觉', 50)
pq.enqueue('打游戏', 100)
pq.enqueue('学习', 1)
console.log(pq.toString())  // 学习:1 吃饭:10 睡觉:50 打游戏:100 
标签: 数据结构 队列
最后更新:2022-08-11

粥呀Bo

所谓惊喜,就是苦苦等候的兔子来了,后面却跟着狼

点赞
< 上一篇
下一篇 >

文章评论

取消回复
目录
  • 一、什么是队列结构
  • 二、队列结构的实现
  • 三、面试题
  • 四、优先级队列

COPYRIGHT © 2022 zhouyaker.cn. ALL RIGHTS RESERVED.

THEME KRATOS MADE BY VTROIS

陕ICP备2022009272号