my canteen
登录       注册

您现在的位置是:网站首页 > 学无止境

数据结构之队列结构

王伟2020年8月12日160人围观
简介认识队列结构 使用ES6语法对队列结构进行封装

数据结构之队列结构

一. 认识队列

队列结构

  • 队列(Queue),它是一种运算受限的线性表,先进先出(FIFO First In First Out)
  • 队列是一种受限的线性结构
  • 受限之处在于它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作

生活中类似的队列结构

  • 生活中类似队列的场景就是非常多了, 比如在电影院, 商场, 甚至是厕所排队.
  • 优先排队的人, 优先处理. (买票, 结账, WC)

队列的图解

队列在程序中的应用

打印队列:
  • 有五份文档需要打印, 这些文档会按照次序放入到打印队列中.
  • 打印机会依次从队列中取出文档, 优先放入的文档, 优先被取出, 并且对该文档进行打印.
  • 以此类推, 直到队列中不再有新的文档.
线程队列:
  • 在进行多线程开发时, 我们不可能无限制的开启新的线程.
  • 这个时候, 如果有需要开启线程处理任务的情况, 我们就会使用线程队列.
  • 线程队列会依照次序来启动线程, 并且处理对应的任务.

二. 队列实现

队列的创建

  • 我们需要创建自己的类, 来表示一个队列
class Queue {
  constructor() {
    this.items = []
  }
   // 队列操作方法
}

队列的操作

队列有哪些常见的操作呢?

  • enqueue(element):向队列尾部添加一个(或多个)新的项。
  • dequeue():移除队列的第一(即排在队列最前面的)项,并返回被移除的元素。
  • front():返回队列中第一个元素——最先被添加,也将是最先被移除的元素。队列不做任何变动(不移除元素,只返回元素信息——与Stack类的peek方法非常类似)。
  • isEmpty():如果队列中不包含任何元素,返回true,否则返回false
  • size():返回队列包含的元素个数,与数组的length属性类似。
enqueue方法
enqueue(ele) {
    this.items.push(ele)
}
dequeue方法
  • 先进入队列中的元素, 先从队列中取出. 因此, 应该删除第一个元素
dequeue() {
    return this.items.shift()
 }
front()方法
front() {
    if (this.isEmtpy()) {
      return null
    }
isEmpty方法
isEmtpy() {
    return this.items.length === 0
  }
size方法
size() {
    return this.items.length
  }

完整的代码

export class Queue {
  constructor() {
    this.items = []
  }
  enqueue(ele) {
    this.items.push(ele)
  }
  dequeue() {
    return this.items.shift()
  }
  front() {
    if (this.isEmtpy()) {
      return null
    }

    return this.items[0]
  }
  isEmtpy() {
    return this.items.length === 0
  }
  size() {
    return this.items.length
  }
}

三. 优先级队列

优先级队列的特点:

  • 我们知道, 普通的队列插入一个元素, 数据会被放在后端. 并且需要前面所有的元素都处理完成后才会处理前面的数据.
  • 但是优先级队列, 在插入一个元素的时候会考虑该数据的优先级.(和其他数据优先级进行比较)
  • 比较完成后, 可以得出这个元素正确的队列中的位置. 其他处理方式, 和队列的处理方式一样.
  • 也就是说, 如果我们要实现优先级队列, 最主要是要修改添加方法. (当然, 还需要以某种方式来保存元素的优先级)

优先级队列的实现

实现优先级队列相对队列主要有两方面需要考虑:
  • 1.封装元素和优先级放在一起(可以封装一个新的构造函数)
  • 2.添加元素时, 将当前的优先级和队列中已经存在的元素优先级进行比较, 以获得自己正确的位置.

优先级队列代码实现:

封装一个新的构造函数, 用于保存元素和元素的优先级
class QueueElement {
  constructor(element, priority) {
    this.element = element
    this.priority = priority
  }
}
封装优先级队列
// 除插入操作外 其他操作和普通对流一样 所以使用ES6方法进行继承
class PriorityQueue extends Queue {
  //添加元素方法
  enqueue(element, priority) {
    const queueElement = new QueueElement(element, priority)
    let added = false
    if (this.isEmtpy()) {
      this.items.push(queueElement)
    } else {
      for (let i = 0; i < this.items.length; i++) {
          //数字越大优先级越高
        if (this.items[i].priority > queueElement.priority) {
          this.items.splice(i, 0, queueElement);
          added = true
          break;
        }
      }
      // 优先级都大于新插入的元素时 就插入到最后
      if (!added) {
        this.items.push(queueElement)
      }
    }
  }
}

代码解析:

  • 封装了一个QueueElement, 将element和priority封装在一起.
  • 根据新的元素先创建一个新的QueueElement对象.
  • 如果元素是第一个被加进来的, 那么不需要考虑太多, 直接加入数组中即可.
  • 如果是后面加进来的元素, 需要和前面加进来的元素依次对比优先级.
  • 一旦优先级, 大于某个元素, 就将该元素插入到元素这个元素的位置. 其他元素会依次向后移动.
  • 如果遍历了所有的元素, 没有找到某个元素被这个新元素的优先级低, 直接放在最后即可.

四. 队列面试题

击鼓传花的规则

  • 原游戏规则:
  • 班级中玩一个游戏, 所有学生围成一圈, 从某位同学手里开始向旁边的同学传一束花.
  • 这个时候某个人(比如班长), 在击鼓, 鼓声停下的一颗, 花落在谁手里, 谁就出来表演节目.
  • 修改游戏规则:
  • 我们来修改一下这个游戏规则.
  • 几个朋友一起玩一个游戏, 围成一圈, 开始数数, 数到某个数字的人自动淘汰.
  • 最后剩下的这个人会获得胜利, 请问最后剩下的是原来在哪一个位置上的人?

击鼓传花的实现

function passGame(namelist, num) {
  const 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; i++) {
        // 每次通过删除加入进行重新排列
      queue.enqueue(queue.dequeue())
    }
    queue.dequeue()
  }
  return queue.front()
}

淘汰过程图解

路漫漫其修远兮,吾将上下而求索!


文章评论

来说句话吧.... 共有评论数:0条


微信二维码 博主微信 qq二维码 博主QQ
177****8743
7*24小时电话