阿里朋友的忠告：大厂里数据结构很重要，先来了解一下队列

一、定义

队列是一种受限线性表，它只允许在表的前端（front）进行删除操作，进行删除操作的端称为队头。在表的后端（rear）进行插入操作，进行插入操作的端称为队尾。队列中没有元素时，称为空队列。

队列元素：队列的数据元素

入队：在队列中插入一个队列元素

出队：从队列中删除一个队列元素

因为队列只允许在一端插入，在另一端删除，所以只有最早进入队列的元素才能最先从队列中删除，故队列又称为先进先出（FIFO—first in first out）线性表。

比如：可以把队列想成排队买票，先来的先排队，后来的人只能站末尾，不允许插队。先来者先买票，这就是典型的“队列”。

二、队列的分类与实现

1.顺序队列

用数组存储队列，即利用一组地址连续的存储单元依次存放队列中的元素。

为了避免当只有一个元素时，队头和队尾重合使得处理变得麻烦，所以引入两个指针(头尾指针)：front指针指向队头元素，rear指针指向队尾元素的下一个位置。初始化时的头尾指针，初始值均为0。入队时尾指针rear加1，出队时头指针front加1，头尾指针相等时队列为空。

• 空队列：

• 入队：

• 出队：

• 顺序队列的假溢出：队列的存储空间未满，却发生了溢出。

• 克服假溢出的方法：

（1）将队列中的所有元素均向低地址区移动

（2）将数组存储区域看成是一个首位相接的环，即循环队列

2.循环队列

循环队列  通过  将尾指针在走到最后一个位置的时候，重新连接到头部，也就是头尾相接的循环的方法 成功解决了“假溢出”的问题

• 在使用循环队列的时候，不能像顺序队列一样，front指针和rear指针后移不能直接使用++，而要使用%

• 当到达数组尾后需要移动到数组头：front = (front+1)%MaxSize（最大空间数）

• 虽然使用循环队列，成功的解决了假溢出的问题，但是又产生了新的问题——判空

因为在顺序队列的时候，我们判断队列是否为空是通过   rear == front 来判断的。

但是在循环的时候，如果队列中的元素是满的，此时同样的 rear == front  。就无法判断队列是否是空的还是满的。

• 解决判空判满方法：

(1) 设置一个标志变量flag， 当front == rear，且flag = 0时为队列空，当front== rear，且flag= 1 时为队列满。

(2) 另一种办法是浪费一个空间，当尾指针rear的下一个位置front是时，就认为是队满。

在入队和出队的过程中，rear可能比front大，也有可能比front小，所以它们只相差一个位置时就是满的情况，但也可能是相差整整一圈。所以若队列的最大空间为MaxSize，

那么队列满的条件是：(rear+1) % MaxSize == front 。

构造器的入参是 队列长度，那么我们队列就应该持有队列长度变量，通常用 capacity 表示，其次需要实现首尾相接，也就必须要有首尾指针，分别为 front 和 rear，另外需要一个额外存放数据的空间，可用数组来代替。

/** * @param {number} k * 构造器，设置队列长度为 k */var MyCircularQueue = function (k) {  this.front = 0;  this.rear = 0;  this.capacity = k;  this.queue = new Array(k);};
/** * @param {number} value * @return {boolean} * 向循环队列插入一个元素。如果成功插入则返回真。 */MyCircularQueue.prototype.enQueue = function (value) {  if (this.isFull()) {    return false;  } else {    this.queue[this.rear] = value;    this.rear = (this.rear + 1) % this.capacity;    return true;  }};
/** * @return {boolean} * 从循环队列中删除一个元素。如果成功删除则返回真 */MyCircularQueue.prototype.deQueue = function () {  if (this.isEmpty()) {    return false;  } else {    this.queue[this.front] = null;    this.front = (this.front + 1) % this.capacity;  }};
/** * @return {boolean} * 检查循环队列是否为空。 */MyCircularQueue.prototype.isEmpty = function () {  return this.rear == this.front;  或 return this.rear == this.front && !this.queue[this.front]};
/** * @return {boolean} * 检查循环队列是否已满。 */MyCircularQueue.prototype.isFull = function () {  return (this.rear + 1) % this.capacity == this.front;  或  return this.rear == this.front && this.queue[this.front]};

3.链队列

队列的链式存储结构，其实就是一个操作受限的单向链表，只不过它只能尾进头出而已，我们把它简称为链队列。链式队列和单向链表比就多了两个指针，头指针和尾指针。

对于链队列而言，由于程序需要从rear端添加元素，然后从front端删除元素，因此考虑对链队列增加front、rear两个引用变量，使他们分别指向链队列的头、尾两个节点。

• 入队：

创建一个新节点，让原rear节点的next指向新节点，在让rear指向新节点即可

• 出队：

将原front节点指向原front节点的next节点，当然不要忘记释放原front节点的引用

function LinkQueue() {  this.length = 0;  this.front = null; //队头  this.rear = null; //队尾}LinkQueue.prototype.Node = function (el) {  this.element = el;  this.next = null;};//入队LinkQueue.prototype.push = function (el) {  var current = null,    node = new this.Node(el);  if (this.length == 0) {    this.length++;    this.front = this.rear = node;    return true;  } else {    current = this.rear;    current.next = node;    this.rear = node;    this.length++;    return true;  }};
//出队LinkQueue.prototype.pop = function () {  var current = null;  if (this.length != 0) {    current = this.front;    this.front = current.next;    this.length--;    return true;  } else {    return null;  }};
//清空队列LinkQueue.prototype.clear = function () {  this.front = this.rear = null;  this.length = 0;  return true;};

优点：

• 相比普通的队列，元素出队时无需移动大量元素，只需移动头指针。

• 可动态分配空间，不需要预先分配大量存储空间。

• 适合处理用户排队等待的情况。

缺点：

• 单链表存储数据同时还需要额外存储下一个节点的地址，空间开销比较大。

时间复杂度：

• 读取时的时间复杂度为O(1)。

• 插入、删除时的时间复杂度为O(1)。

4.优先队列

• 定义：普通的队列具有先进先出的特性，元素追加在队尾，如果删除的话，从队头删除。而在优先队列中，队列中的数据被赋予了优先级。当访问元素时，优先级最高的会先被删除。所以说优先队列是最高级数据先出

• 实现方式：堆

• 堆是一颗完全二叉树。

• 重要的性质：父节点一定是其所有子孙节点的最值。

• 堆的插入：首先在堆的末尾插入该数值，然后不断向上调整，直到没有大小颠倒为止。

• 取出最值：最值就在堆顶，即二叉树的第一个元素。

• 删除最值：首先将堆的最后一个元素复杂到根节点，并删除最后一个元素，然后将根节点不断向下进行调整直到没有大小颠倒。

• 为什么要用堆来实现优先队列？

1.优先队列所需要实现的两种操作，不同于队列和栈，它需要一个有序的元素序列，但不要求全部有序，只需要从这些元素中找到最大（或最小）的一个元素。而堆刚好满足这个条件，而插入元素这个操作，即是由下至上的堆有序化。

2. 队列，栈都是用数组或者链表来实现的，针对优先队列，用数组和链表实现也是可以的，在队列较小，大量使用两种操作之一时，或者所操作的元素的顺序已知时，用数组和链表十分有用，但是，在最坏的情况下，优先队列用这两张方法实现所需的时间却是线性的。而用堆在最坏情况下的时间则是对数级别。

三、队列与栈的区别

1、队列先进先出，栈先进后出。

2、对插入和删除操作的"限定"不同。

栈是限定只能在表的一端进行插入和删除操作的线性表。 

队列是限定只能在表的一端进行插入和在另一端进行删除操作的线性表。  

3、遍历数据速度不同。

栈只能从头部取数据，也就最先放入的需要遍历整个栈最后才能取出来，而且在遍历数据的时候还得为数据开辟临时空间，保持数据在遍历前的一致性。

队列则不同，它基于地址指针进行遍历，而且可以从头或尾部开始遍历，但不能同时遍历，无需开辟临时空间，因为在遍历的过程中不影响数据结构，速度要快的多。

四、应用

约瑟夫环

m个人围成一个圈， 指定一个数字n,从第一个人开始报数， 每轮报到n的选手出局，由下一个人接着从头开始报，最后一个人是赢家。其中m>1,n>2

例如四人，每轮到3出局

1,2,3,4    1,2， ，4,1， ，4,1，，1

function josephRingQueue(list, num, winNum) {    let queue = new Queue();
    //遍历数组，让数组中的元素依次入队    list.forEach((item) => {        queue.enqueue(item);    });    //队列中还有大于winNum人时    while (queue.size() > winNum) {        //存活的人从队首出队再从队尾入队        for (let i = 0; i < num - 1; i++) {            queue.enqueue(queue.dequeue());        }        //淘汰的人直接从队列出不再入队        queue.dequeue();    }    //队列中仅剩winNum个人时游戏结束    return queue;}let m = 4, n = 3let people = [];
let initArr = (() => {    for (let i = 1; i <= m; i++) {        people.push(i);    }})
initArr()console.log(josephRingQueue(people, n, 1));