队列（Queue）

1. 队列结构

队列是一种运算受限的线性表,先进先出(FIFO First In First Out)

• 队列是一种受限的线性结构
• 受限之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作

队列

先进先出(FIFO First In First Out)

队列示意图

2. 队列结构在程序中的应用

• 打印队列

打印会按照放入的先后顺序一个个打印

3. 队列操作常见的方法或属性

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

• dequeue()：移除队列的第一（即排在队列最前面的）项，并返回被移除的元素。

• front：查看队列中即将出队的元素（不移除元素，只返回元素信息——与 Stack 中的 peek 属性非常类似）。

• isEmpty：如果队列中不包含任何元素，返回 true，否则返回 false。

• size：返回队列包含的元素个数，与数组的 length 属性类似。

4. 队列的实现

基于数组的实现

封装示例

/* *********封装******** */
class Queue {
  constructor(queue = []) {
    this.source = queue;
  }

  // 返回队列包含的元素个数，与数组的length属性类似。
  get size() {
    return this.source.length;
  }

  // 如果队列中不包含任何元素，返回true，否则返回false。
  get isEmpty() {
    return this.source.length <= 0;
  }

  // 查看队列中即将出队的元素（不移除元素，只返回元素信息——与Stack中的peek属性非常类似）。
  get front() {
    if (this.isEmpty) return null;
    return this.source[0];
  }

  // 向队列尾部添加一个（或多个）新的项
  enqueue(ele) {
    this.source.push(ele);
  }

  // 移除队列的第一（即排在队列最前面的）项，并返回被移除的元素
  dequeue() {
    return this.source.shift();
  }
}

使用示例

/* *********使用******** */
let queue = new Queue();

queue.enqueue("1");
queue.enqueue("4");
queue.enqueue("2");
queue.enqueue("hello");

queue.size; // 4
queue.isEmpty; // false
queue.front; // 1
queue.dequeue(); // 1
queue.size; // 3

5. 队列使用案例

题一

一些人围成一个圈, 从某一个人开始报数 1,2,3,4,5,当数到 5 的一个人退出圈外, 其余人接着数, 一直往复, 直到剩下一个人,请找出最后的那一位赢家的编号。

思路： 用队列实现， 首先将这些人依次加入队列， 然后取出一个，若这个人数的数不是 5 则从新加入队列，若是 5 则不加入队列，直到队列里面剩下一个人， 这个人就是最后的赢家。

代码实现：

function findWinAt5(arr) {
  const queue = new Queue();
  for (let i = 0; i < arr.length; i++) {
    const item = arr[i];
    queue.enqueue(item);
  }
  let curNum = 1;
  while (queue.size > 1) {
    let curItem = queue.dequeue();

    if (curNum !== 5) {
      queue.enqueue(curItem);
    }
    if (++curNum > 5) curNum = 1;
  }
  return queue.dequeue();
}

let str = "123456";
let res = findWinAt5(str);
console.log(res); // 1