JS数据结构&算法学习——队列

队列

在之前的栈，是一种受限的线性结构，为先进后出，那么同为线性结构的队列，特点又是怎么样的呢？

概念

队列是一种受限的线性表，先进先出，它只允许我们在表的前端进行删除操作，在表的后端进行添加操作。

生活应用

1. 在生活中最常看到的队列场景就是排队了，即我们在排队时，排头也就是我们的表头，它允许出去，无法进行插队也就是添加操作，而排尾，也就是我们的表尾，它允许有人进行排队，即添加操作
2. 在火车检票的时候，我们正常的是进行排队，而军人，老人等特殊人群可以优先进行处理，这就是优先队列。

程序应用

1. 就拿我们JS来说，事件队列是比较常见的，因为JS是一门单线程语言，即在我们触发我们的函数的时候，会有一个事件队列，其会按照事件的触发顺序来执行，即先触发先执行，这就是队列的一种体现
2. 当然线程队列也是一种队列的体现，我们一般为了任务能够并行处理，会用到多线程，但是多个线程会占据非常多的内存，所以这个时候我们可以通过使用线程队列，按照次序来启动线程，并处理对应的任务。

队列结构

当然队列结构的实现和栈一样，可以通过数组和链表实现

首先我们先封装一下队列

function queue(){
    //队列的属性
    this.items = []
    //队列的相关操作
}
var queue = new queue()
复制代码

因为JS中的类是基于对象的所以我们封装了一个队列类，在类中我们可以定义队列的属性与方法，封装好之后我们可以去通过调用来对队列实现一些操作

常见操作及封装

1. enqueue(element)：在队列的尾部添加元素
2. dequeue()：移除队列的首个元素，并返回其值
3. front()：返回队列的第一个元素
4. isEmpty：判断队列是否为空队列
5. size：返回队列长度
6. toString()：转换字符串

enqueue(element)：使用push方法来进行入队封装

queue.prototype.enqueue = function (element) {
      this.items.push(element)
}
复制代码

dequeue()：通过JS提供的shift的方法来进行出队操作

queue.prototype.delet = function () {
      return this.items.shift()
}
复制代码

front()：直接通过数组下标来返回队首元素

queue.prototype.front = function () {
      return this.items[0]
}
复制代码

isEmpty()：通过数组的length来进行栈的判空

queue.prototype.isEmpty = function () {
      return this.items.length == 0
}
复制代码

size()

queue.prototype.size = function () {
      return this.items.length
}
复制代码

toString()：通过声明字符串变量，对栈进行遍历，通过JS字符串的特性，来进行字符串拼接，最后返回其字符串，其实现原理和栈的toString一样。

queue.prototype.toString = function () {
      var reString = ''
      for (let i = 0; i < this.items.length; i++) {
        reString += this.items[i] + ''
      }
      return reString
    }
复制代码

使用

在封装好之后我们就可以开始进行调用

queue.enqueue(1)
queue.enqueue(19)
queue.enqueue(11)
console.log(queue)
复制代码

queue.delet()
console.log(queue)
复制代码

大家可以试着自己些写一下并体验队列的这几种操作

击鼓传花

相信大家都玩过击鼓传花的游戏吧，击鼓的时候传递花朵，鼓声停，花在谁手中谁就受惩罚

现在有不同的游戏规则，即同学围成一圈，按阿拉伯数字顺序进行数数，当某人数到在场人数的时候就会被淘汰

我们现在要用队列来实现这个游戏并返回来最终获胜者的姓名

1. 算法原理：

现在我们将所有人按次序放入一个队列中，然后从队首开始出队入队，以此当出现在场人数的时候，其正好是队首，出队，多次操作，得到结果

2. 算法实现：

1. 创建队列并将所有人入队

var queue = new queue
    for (let i = 0; i < list.length; i++) {
     queue.enqueue(nameList[i])
}
复制代码

1. 开始循环入队出队直到队列的长度为1

while (queue.size() > 1) {
      //开始数num，当不是num的时候出队后重新入队，当num是在场人数时，出队。
      for (let i = 0; i < num - 1; i++) {
        queue.enqueue(queue.dequeue())
      }
      //删除目标即现在的队首
      queue.dequeue()
    }