一、认识队列

  • 受限的线性结构

栈是一种受限的线性结构，但是有些特定的问题，栈结构无法解决，所以就有了另一种受限的线性结构-队列。

  • 队列(Queue)：是一种受限的线性表，先进先出（FIFO first in first out）

受限之处：只允许在表的前端（front）进行删除，在表的后端（rear）进行插入。
image.png

二、生活中的例子以及程序中的应用场景

  • 比如电影院，商场排队
  • 优先队列：优先处理（医院急诊…）

  • 线程队列

    三、队列的常用方法

  • enqueue(element)：向队列尾部添加一个或多个元素（新的项）

  • dequeue()：移除队列的第一项，并返回移除的元素
  • front()：返回队列第一个元素，不对队列做任何操作
  • isEmpty()：判断队列是否为空
  • size()：返回队列长度
  • toString()：将队列中的内容转成字符串模式

    四、封装队列以及常用方法

    1. function Queue() {
    2.   // 属性
    3.   this.items = []
    4.   // 方法
    5.   Queue.prototype.enqueue = function(ele) {
    6.       this.items.push(ele)
    7.   }
    8.   // 删除元素，性能不高，原因是删除第一个元素，后面的元素都要向前移动
    9.   Queue.prototype.dequeue = function() {
    10.       return this.items.shift()
    11.   }
    12.   Queue.prototype.front = function() {
    13.       return this.items[0]
    14.   }
    15.   Queue.prototype.isEmpty = function() {
    16.       return this.items.length == 0
    17.   }
    18.   Queue.prototype.size = function() {
    19.       return this.items.length
    20.   }
    21.   Queue.prototype.toString = function() {
    22.       var str = ''
    23.       for(var i = 0; i < this.items.length; i ++) {
    24.           str += this.items[i] + ' '
    25.       }
    26.       return str
    27.   }
    28. }
    29. var queue = new Queue()
    30. queue.enqueue('11')
    31. queue.enqueue('22')
    32. queue.enqueue('33')
    33. queue.enqueue('44')
    34. console.log(queue.items)

    五、队列完成击鼓传花

    游戏规则：班级中所有学生围成一圈，从某位同学开始向旁边的同学传一束花；这个时候有一个人（班长）来击鼓，鼓声停下的那一刻，花落在谁手里，谁就出来表演节目。
    修改游戏规则：所有人围成一圈，进行数数，数到某个数的人自动淘汰，最后剩下的会获得胜利，请问最后剩下的是在原来哪一个位置上的人？
    1. 思路：
    2. 1、创建一个队列
    3. 2、将人循环添加到队列中
    4. 3、从0位置开始，循环num-1位置（这里num是传入的要数的数字，并不是数组的长度）
    5. 4、循环不断将num之前的元素删除并重新添加到队列的末尾（不断向队列中添加删除的元素（队列中删除的都是一个元素））
    6. 5、将num位置的元素直接删除
    7. 6、直到删除到队列中还剩下一个元素的时候，停止删除 while循环
    8. 7、获取当前队列的第一个元素
    9. 8、通过indexOf方法在数组中查找到该元素
    10. function passGream(nameList, num) {
    11.   // 1、创建一个队列
    12.   var queue = new Queue()
    13.   // 2、将name添加到队列中
    14.   for (var i = 0; i < nameList.length; i ++) {
    15.       queue.enqueue(nameList[i])
    16.   }
    17.   // 3、开始数数字
    18.   while (queue.size() > 1) { // 当队列中的长度为1的时候，停止循环
    19.       // 不是num的时候，重新加入队列的末尾
    20.       // 是num这个数字的时候，将其从队列中删除
    21.       // 3.1 num数字之前的人重新放到队列的末尾
    22.       for (var j = 0; j < num - 1; j ++) {
    23.           queue.enqueue(queue.dequeue())  // 从第0位置开始，不断循环到num(传入的数字)-1的位置，将不是num位置的删除后重新插入到队列的末端
    24.       }
    25.       console.log(queue.dequeue(), '=====')
    26.       // num对应的这个人直接删除
    27.       queue.dequeue()
    28.   }
    29.   // 4、获取剩下的那个人
    30.   // console.log(queue.size())
    31.   var endName = queue.front()
    32.   // console.log('最终剩下的人：'+endName)
    33.   return nameList.indexOf(endName)
    34. }
    35. // 测试击鼓传花
    36. var names = [1, 2, 3, 4, 5]
    37. console.log(passGream(names, 3), '====传花最后的人')

    六、优先级队列

    1. 需要有一个优先级字段，用来进行比较
    2. function PriorityQueue() {
    3.   // 封装内部类（函数）
    4.   function QueueElement(element, priority) {
    5.       this.element = element
    6.       this.priority = priority
    7.   }
    8.   // 创建队列
    9.   this.items = []
    10.   // 实现插入方法
    11.   PriorityQueue.prototype.enqueue = function (element, priority) {
    12.       // 1、创建queueElement类
    13.       var queueElement = new QueueElement(element, priority)
    14.       // 2、判断队列是否为空
    15.       if (this.items.length == 0) {
    16.           // 如果为空，直接插入到队列中，不需要比较
    17.           this.items.push(queueElement)
    18.       } else { // 原数组中有元素,循环比较原数组
    19.           var added = false
    20.           for (var i = 0; i < this.items.length; i ++) {
    21.               if (queueElement.priority < this.items[i].priority) {
    22.                   // 传入元素的优先级和队列中的优先级比较
    23.                   this.items.splice(1, 0, queueElement)
    24.                   added = true
    25.                   break
    26.               }
    27.           }
    28.           if (!added) {
    29.               this.items.push(queueElement)
    30.           }
    31.       }
    32.   }
    33.   PriorityQueue.prototype.dequeue = function() {
    34.       return this.items.shift()
    35.   }
    36.   PriorityQueue.prototype.front = function() {
    37.       return this.items[0]
    38.   }
    39.   PriorityQueue.prototype.isEmpty = function() {
    40.       return this.items.length == 0
    41.   }
    42.   PriorityQueue.prototype.size = function() {
    43.       return this.items.length
    44.   }
    45.   PriorityQueue.prototype.toString = function() {
    46.       var str = ''
    47.       for(var i = 0; i < this.items.length; i ++) {
    48.           str += this.items[i].element + '-' + this.items[i].priority + ' '
    49.       }
    50.       return str
    51.   }
    52. }
    53. var pq = new PriorityQueue()
    54. pq.enqueue('aa', 1)
    55. pq.enqueue('gf', 52)
    56. pq.enqueue('dd', 32)
    57. pq.enqueue('rr', 15)
    58. pq.enqueue('tt', 100)
    59. console.log(pq.items)
    60. console.log(pq.toString())