队列

一、概念


队列（Queue）

1. 受限的线性结构，==先进先出==（FIFO First In First Out）

2. 只允许在表的==前端进行删除==操作，在表的==后端进行插入==操作

队列结构的实现

1. 基于数组实现
2. 基于链表实现（链表：也是一种数据结构，JavaScript中没有自带的链表结构）

二、属性和方法

队列的方法（6个）：

• enqueue(): 向队列尾部添加一个或多个新的项
• dequeue(): 移出队列的第一项，并返回被移出的元素
• front(): 返回队列中第一个元素
• isEmpty(): 如果队列中不包含任何元素，返回true，否则返回false
• size(): 返回队列包含的元素个数
• toString(): 将队列中的内容，转换成字符串形式

代码实现

/***************  队列的封装 ***********/
function Queue() {
  this.items = [];

  // 向队列尾部天机一个或多个新的项
  Queue.prototype.enqueue = function (el) {
    this.items.push(el);
  }

  // 移出队列的第一项（排在队列最前面的）项，并返回被移出的元素
  Queue.prototype.dequeue = function () {
    return this.items.shift();
  }

  // 返回队列中第一个元素——最先被添加，也将是最先被移除的元素。
  // 队列不做任何变动，不移除元素，只返回元素
  Queue.prototype.front = function () {
    return this.items[0]
  }

  // 如果队列中不包含任何元素，返回true，否则返回false
  Queue.prototype.isEmpty = function () {
    return this.items.length === 0
  }

  // 返回队列包含的元素个数，与数组的length属性类似
  Queue.prototype.size = function () {
    return this.items.length;
  }

  // 将队列中的内容，转换成字符串形式
  Queue.prototype.toString = function () {
    return this.items.toString();
  }
}

三、算法实例

击鼓传花游戏

原游戏规则：

• 班级中玩一个游戏，所有学生围成一圈，从某位同学手里开始向旁边的同学传一束花。
• 这个时候某个人(比如班长)在击鼓，鼓声停下的一颗，花落在谁手里，谁就出来表演节目。

修改游戏规则：

• 几个朋友一起玩—个游戏，围成一圈，开始数数，数到某个数字的人自动淘汰。
• 最后剩下的这个人会获得胜利，请问最后剩下的是原来在哪一个位置上的人?

封装一个基于队列的函数

• 参数: 所有参与人的姓名，基于的数字。
• 结果: 最终剩下的一人的姓名。

function passGame(nameList, num) {

  // 1.创建一个队列结构
  const queue = new Queue();

  // 2.将所有人添加到 队列 中
  for (const item of nameList) {
    queue.enqueue(item)
  }

  // 3.开始数数
  while(queue.size() > 1) {
    // - 不是num的时候，重新添加到队列的 末尾
    // - 是num这个数字的时候，将其从队列中删除

    // 3.1 num数字之前的人，添加到队列的末尾
    for (let i = 0; i < num - 1; i++) {
      queue.enqueue(queue.dequeue());
    }

    // 3.2 num数字的这个人，直接从队列中删除
    queue.dequeue();
  }

  // 4.获取最后剩下的那个人
  const lastName = queue.front();
  console.log('剩下的人：', lastName)

  return nameList.indexOf(lastName);
}

const index = passGame(['红', '橙', '黄', '绿', '青', '蓝', '紫'], 3);
console.log('剩下人的索引：', index)