大家好，我是前端图图，已经有段时间没有写文章了?。回家过年之后就没有什么心思了，只想多陪陪家人。导致假期回来才慢慢找回感觉?。好啦！下面废话不多说，就来聊聊数据结构队列。

队列和双端队列

队列和栈相似，但是使用和栈不同的原则。双端队列是队列和栈的原则混合在一起的数据结构。

队列

队列是遵循先进先出（LIFO，也就是先进来的先出去的意思）原则的一组有序的项。队列是从尾部添加新元素，并从头部移除元素，最新添加元素必须排在队列的末尾。

在生活中有很多例子，比如超市的收银台，大家都会排队，而排在第一位的人先接收服务。

在计算机中，一个常见的例子是打印文件，比如说要打印五份文件。在点击打印的时候，每个文件都会被发送到打印队列。第一个发送到打印队列的文档会先被打印，以此类推，知道打印完所有文件。

创建队列

下面就来创建一个表示队列的类。

class Queue {
  constructor() {
    this.count = 0; // 队列元素总数
    this.lowestCount = 0; // 跟踪队列第一个元素的值
    this.items = {};
  }
}

首先用一个存储队列的数据结构，可以是数组，也可以是对象。items就是用来存储元素的。看起来是不是和栈非常相似？只是添加和删除的原则不一样而已。

count属性是用来控制队列大小的。而lowestCount属性是用来在删除队列前面的元素时，追踪第一个元素。

下面是要声明一些队列的方法。

• enqueue：向队列的尾部添加一个元素。
• dequeue：移除队列的第一个元素并且返回该元素。
• peek：返回队列中最先添加的元素，也是最先被移除的元素。
• isEmpty：校验该队列是否为空队列。
• size：返回队列中的元素个数，和数组的length类似。

enqueue方法

首先实现的是enqueue方法，该方法用于向队列尾部添加元素。大家要记住！新添加的元素只能在队列的末尾添加，这个方法和栈的push方法一样。

enqueue(ele) {
  this.items[ele] = ele;
  this.count++;
}

dequeue方法

接下来就是dequeue方法，用于移除队列中的元素。队列遵循先进先出的原则，最先添加的元素最先被移除。

dequeue() {
  if (this.isEmpty()) {
    return undefined;
  }
  
  // 暂存头部元素
  const result = this.items[this.lowestCount];
  delete this.items[this.lowestCount];
  // 删除之后将lowestCount递减
  this.lowestCount--;
  return result;
}

有了这两个方法，Queue类就遵循先进先出的原则了。

peek方法

peek方法用于查看队列头部的元素。把lowestCount作为键名来获取元素值。

peek() {
  if (this.isEmpty()) {
    return undefined;
  }

  return this.items[this.lowestCount];
}

isEmpty方法

isEmpty方法和栈的isEmpty方法一样，只不过这里用的是count和lowestCount之间的差值计算而已。

isEmpty() {
  return this.count - this.lowestCount === 0;
}

size方法

size方法也是用count和lowestCount之间的差值计算。然后返回计算后的差值即可。

size() {
  return this.count - this.lowestCount;
}

clear方法

清空队列中的所有元素，直接把队列里面的所有属性值都重置为构造函数里一样就行了。

clear() {
  this.count = 0;
  this.lowestCount = 0;
  this.items = {};
}

toString方法

还有一个toString方法，该方法返回队列中的所有元素。

toString() {
  if (this.isEmpty()) {
    return "";
  }

  let objString = `${this.items[this.lowestCount]}`;
  for (let i = this.lowestCount + 1; i < this.count; i++) {
    objString = `${objString}, ${this.items[i]}`;
  }

  return objString;
}

由于Queue类中的第一个索引不一定是0，所以从lowestCount的位置开始迭代。

一个队列就这样大功告成啦！

Queue类和Stack类非常像，主要的区别就在于dequeue方法和peek方法，这是由于两个数据结构的原则不一样所导致。

队列整体代码

class Queue {
  constructor() {
    this.count = 0;
    this.lowestCount = 0;
    this.items = {};
  }

  enqueue(ele) {
    this.items[this.count] = ele;
    this.count++;
  }

  dequeue() {
    if (this.isEmpty()) {
      return undefined;
    }

    const result = this.items[this.lowestCount];
    delete this.items[this.lowestCount];
    this.lowestCount++;
    return result;
  }

  peek() {
    if (this.isEmpty()) {
      return undefined;
    }

    return this.items[this.lowestCount];
  }

  isEmpty() {
    return this.count - this.lowestCount === 0;
  }

  size() {
    return this.count - this.lowestCount;
  }

  clear() {
    this.count = 0;
    this.lowestCount = 0;
    this.items = {};
  }

  toString() {
    if (this.isEmpty()) {
      return "";
    }

    let objString = `${this.items[this.lowestCount]}`;
    for (let i = this.lowestCount + 1; i < this.count; i++) {
      objString = `${objString}, ${this.items[i]}`;
    }

    return objString;
  }
}

const queue = new Queue();

console.log(queue.isEmpty()); // true
queue.enqueue("前端工程师");
queue.enqueue("后端工程师");
queue.enqueue("算法工程师");
console.log(queue.toString());
// 前端工程师, 后端工程师, 算法工程师

console.log(queue.size()); // 3

queue.dequeue();

console.log(queue.toString());
// 后端工程师, 算法工程师

双端队列

双端队列是一种同时可以从头部和尾部添加或删除的特殊队列。它是普通队列和栈的结合版。

举个例子，例如：你在食堂排队打饭，你刚打完饭，发现阿姨给的饭有点少。你就回到队伍的头部叫阿姨给多点饭。另外，如果你排在队伍的尾部。看到排在前面还有很多人，你就可以直接离开队伍。

在计算机中，双端队列常见的应用是存储一系列的撤销操作。每当在软件中进行一个操作时，该操作会被存在双端队列里。当点击撤销时，该操作会从双端队列末尾弹出。当操作的次数超出了给定的次数后，最先进行的操作会从双端队列的头部移除。

创建Deque类

和之前一样，先声明一个Deque类。

class Deque {
  constructor() {
    this.count = 0;
    this.lowestCount = 0;
    this.items = {};
  }
}

可以看到Deque类的部分代码和普通队列的代码一样。还有isEmpty、size、clear和toString方法都是一样的。

双端队列可以在两端添加和移除元素，下面列出这几种方法。

• addFront：从双端队列的头部添加元素。
• addBack：从双端队列的尾部添加元素（和队列的enqueue方法一样）。
• removeFront：从双端队列的头部移除元素（和队列的dequeue方法一样）。
• removeBack：从双端队列的尾部移除元素（和栈的peek方法一样）。
• peekFront：获取双端队列头部的第一个元素（和队列的peek方法一样）。
• peekBack：获取双端队列尾部的第一个元素（和栈的peek方法一样）。

addFront方法

addFront(ele) {
  if (this.isEmpty()) {
    this.addBack(ele);
  } else if (this.lowestCount > 0) {
    this.lowestCount--;
    this.items[this.lowestCount] = ele;
  } else {
    for (let i = this.count; i > 0; i--) {
      this.items[i] = this.items[i - 1];
    }
    this.count--;
    this.lowestCount = 0;
    this.items[0] = ele;
  }
}

要将一个元素添加到双端队列的头部，有三种情况。

1. 当双端队列为空时，就把元素从尾部添加到双端队列中，这样就添加到双端队列的头部了。
2. 一个元素已经从双端队列的头部移除，也就是说lowestCount属性的值大于等于1时，就把lowestCount的值减1并将新元素的值放到该键的位置上。
3. 当lowestCount的值为0时，我们可以设置一个负值的键，就拿数组来说。要在第一个位置添加一个元素，就要把所有的元素都往后挪一位来空出第一个位置。就从最后一位开始迭代，并把元素赋上索引值减1的位置的值（也就是前一个元素）。在所有元素都完成了移动之后，第一位的索引值将是0，再把添加的元素覆盖掉它就可以了。

测试Deque类

const deque = new Deque();

deque.addBack("前端工程师");
deque.addBack("后端工程师");
console.log(deque.toString());
// 前端工程师, 后端工程师

deque.addBack("算法工程师");
console.log(deque.toString());
// 前端工程师, 后端工程师, 算法工程师
console.log(deque.size()); // 3

deque.removeFront(); // 前端工程师跑路了

console.log(deque.toString());
// 后端工程师, 算法工程师

deque.removeBack(); // 算法工程师也跑路了
console.log(deque.toString());
// 后端工程师

deque.addFront("前端工程师"); // 前端工程师又回来了
console.log(deque.toString());
// 前端工程师, 后端工程师

Deque类整体代码

class Deque {
  constructor() {
    this.count = 0;
    this.lowestCount = 0;
    this.items = {};
  }

  addFront(ele) {
    if (this.isEmpty()) {
      this.addBack(ele);
    } else if (this.lowestCount > 0) {
      this.lowestCount--;
      this.items[this.lowestCount] = ele;
    } else {
      for (let i = this.count; i > 0; i--) {
        this.items[i] = this.items[i - 1];
      }
      this.count--;
      this.lowestCount = 0;
      this.items[0] = ele;
    }
  }

  addBack(ele) {
    this.items[this.count] = ele;
    this.count++;
  }

  removeFront() {
    if (this.isEmpty()) {
      return undefined;
    }
    const result = this.items[this.lowestCount];
    delete this.items[this.lowestCount];
    this.lowestCount++;
    return result;
  }

  removeBack() {
    if (this.isEmpty()) {
      return undefined;
    }
    
    this.count--;
    const result = this.items[this.count];
    delete this.items[this.count];
    return result;
  }

  peekFront() {
    if (this.isEmpty()) {
      return undefined;
    }
    return this.items[this.lowestCount];
  }

  peekBack() {
    if (this.isEmpty()) {
      return undefined;
    }
    return this.items[this.count - 1];
  }

  isEmpty() {
    return this.count - this.lowestCount === 0;
  }

  size() {
    return this.count - this.lowestCount;
  }

  clear() {
    this.count = 0;
    this.lowestCount = 0;
    this.items = {};
  }

  toString() {
    if (this.isEmpty()) {
      return "";
    }

    let objString = `${this.items[this.lowestCount]}`;
    for (let i = this.lowestCount + 1; i < this.count; i++) {
      objString = `${objString}, ${this.items[i]}`;
    }
    return objString;
  }
}

用队列、双端队列解决问题

循环队列——击鼓传花游戏

循环队列的一个例子是击鼓传花游戏。在这个游戏里，小孩子围成一个圈，把花尽快地传递给旁边的小孩子。在某个时刻传花停止了，花在谁手上，谁就被淘汰。重复这个过程，直到只剩下一个孩子。

下面来模拟击鼓传花游戏。

function hotPotato(names, num) {
  const queue = new Queue();
  const eliminatedList = []; // 淘汰名单

  for (let i = 0; i < names.length; i++) {
    // 先把名单加入队列
    queue.enqueue(names[i]);
  }

  while (queue.size() > 1) {
    for (let i = 0; i < num; i++) {
      // 从队列头部移除一项，并把该项添加到队列尾部
      queue.enqueue(queue.dequeue());
    }

    // for循环一旦停止了，就将队列最前一项移除并添加到淘汰名单中
    eliminatedList.push(queue.dequeue());
  }

  return {
    eliminated: eliminatedList,
    winner: queue.dequeue(),
  }
}

hotPotato函数接收两个参数：names是一份名单，num是循环次数。首先把名单里的名字添加到队列中，然后用num迭代队列。从队列头部移除一项并将该项添加到队列尾部。一旦到达num的次数（for循环停止了），将从队列移除一个元素并添加到淘汰名单里，直到队列里只剩下一个人时，这个人就是获胜者。

我们来试验一下hotPotato算法。

const names = [
  "前端工程师",
  "后端工程师",
  "算法工程师",
  "测试工程师",
  "运维工程师",
];

const result = hotPotato(names, 1);

result.eliminated.forEach((item) => {
  console.log(`${item}被淘汰了`);
});
// 后端工程师被淘汰了
// 测试工程师被淘汰了
// 前端工程师被淘汰了
// 运维工程师被淘汰了

console.log(`${result.winner}获胜了！`);
// 算法工程师获胜了！

下图展示整个过程。

可以传入不同的数值，模拟不同的场景。

回文检查

将一个句子正着读和倒着读的意思一样，就可以称为回文。

检查一个词或字符串是不是回文，最简单的方式是把字符串反转过来并检查它和原字符串是否相同。如果相同，那就是回文。可以用栈来实现，但是利用数据结构来解决这个问题最简单的方法就是双端队列。

function palindromeCheck(str) {
  // 判断传入的字符串是否合法
  if (str === undefined || str === null || (str != null && str.length === 0)) {
    return false;
  }

  const deque = new Deque();
  // 把字符串转成小写并剔除空格
  const lowerString = str.toLocaleLowerCase().split(" ").join("");

  // 回文标识
  let isEqual = true;

  // 存储双端队列头部字符串
  let firstChar = "";

  // 存储双端队列尾部字符串
  let lastChar = "";

  // 将字符串逐个添加到双端队列中
  for (let i = 0; i < lowerString.length; i++) {
    deque.addBack(lowerString.charAt(i));
  }

  while (deque.size() > 1 && isEqual) {
    // 移除双端队列头部的字符串并将返回结果赋值给firstChar变量
    firstChar = deque.removeFront();

    // 移除双端队列尾部的字符串并将返回结果赋值给lastChar变量
    lastChar = deque.removeBack();

    // 如果双端队列两端移除的元素互不相同，证明不是回文
    if (firstChar !== lastChar) {
      isEqual = false;
    }
    return isEqual;
  }
}

console.log(palindromeCheck("stts")); // true
console.log(palindromeCheck("level")); // true
console.log(palindromeCheck("小姐姐姐姐小")); // true
console.log(palindromeCheck("上海自来水来自海上")); // true
console.log(palindromeCheck("知道不不知道")); // false

总结

这篇文章介绍了队列和双端队列所遵循的原则，还有它们的实现方法。还介绍了两个经典的队列问题：击鼓传花和回文检查。 喜欢的掘友可以点击关注+点赞哦！后面会持续更新其他数据结构，也把自己学的知识分享给大家。当然写作也可以当成复盘。