【数据结构基础】队列简介（使用ES6）

上一篇系列文章 《【数据结构基础】栈简介（使用ES6）》 笔者介绍了什么是数据结构和什么是栈及相关代码实现，本篇文章笔者给大家介绍下什么是队列以及相关的代码实现。

本篇文章将从以下几个方面进行介绍：

• 什么是队列
• 如何用代码实现队列
• 什么是双端队列
• 如何用代码实现双端队列
• 实际应用举例

本篇文章阅读时间预计 10 分钟。

什么是队列

队列是一个有序集合，遵循先进先出的原则(FIFO),与堆栈的原则恰恰相反。允许插入的一端称为队尾，允许删除的一端称为对头。假设队列是q=(a1,a2,......,an),那么a1就是队头，an就是队尾。我们删除时，从a1开始删除，而插入时，只能在an后插入。

队列就好比我们生活中的排队，比如我们去医院挂号需要排队，进电影院需要排队进场，去超市买东西需要排队结账，打电话咨询客服需要排队接听等等。

在计算机中最常见的例子就是打印机的打印队列任务，假设我们要打印五分不同的文档，我们需要依次打开每个文档，依次的单击“打印按钮”，每个打印指令都会送往打印队列任务，最先按打印按钮的文档最先被打印，直到所有文档被打印完成。

如何用代码实现队列

首先我们先声明创建一个初始化的queue类，实现代码如下：

class Queue {
  constructor() {
    this.count = 0; 
    this.lowestCount = 0;
    this.items = {}; 
  }
} 复制代码

首先我们创建了一个存储队列元素的数据结构，我们声明了count变量，方便我们统计队列大小，声明lowestCount变量标记队列的对头，方便我们删除元素。接下来我们要声明如下方法，来实现一个完整的队列：

• enqueue(element)：此方法用于在队尾添加元素。
• dequeue(): 此方法用于删除队列的队头元素。
• peek():此方法用于队列的队头元素。
• isEmpty(): 此方法用于判断队列是否为空，是的话返回True,否的话返回False。
• size(): 此方法返回队列的大小，类似数组length属性。
• clear():清空队列所有元素。
• toString()：打印队列中的元素。

enqueue(element)

此方法主要实现了向队列的队尾添加新的元素，实现的关键就是“ 队尾 ”添加元素，实现代码如下：

enqueue(element) {
  this.items[this.count] = element;
  this.count++;
} 复制代码

由于队列的items属性是对象，我们使用count作为对象的属性，元素添加至队列后，count的值递增加1。

dequeue()

此方法主要用于删除队列元素，由于队列遵循先进先出原则，我们需要将队列的“队头”元素进行移除，代码实现如下：

dequeue() {
  if (this.isEmpty()) {
    return undefined;
  }
  const result = this.items[this.lowestCount]; 
  delete this.items[this.lowestCount];
  this.lowestCount++;
  return result; 
}复制代码

首先我们需要验证队列是否为 空 ，如果未空返回未定义。如果队列不为空，我们首先获取“ 队头 ”元素，然后使用 delete 方法进行删除，同时标记对头元素的变量lowestCount 递增加一 ，然后返回删除的队头元素。

peek()

现在我们来实现一些辅助方法，比如我们想查看“队头”元素，我们用peek()方法进行实现，使用lowestCount变量进行获取，实现代码如下：

peek() {
  if (this.isEmpty()) {
    return undefined;
  }
  return this.items[this.lowestCount];
} 复制代码

size()与isEmpty()

获取队列的长度，我们可以使用count变量与lowestCount相减即可，假如我们的count属性为2，lowestCount为0，这意味着队列有两个元素。接下来我们从队列里中删除一个元素，lowestCount的值更新为1，count的值不变，因此队列的长度为1，依次类推。因此size()方法的实现代码如下：

size() {
  return this.count - this.lowestCount;
} 复制代码

isEmpty()的实现方式更为简单了，只需要判断size()是否返回为0即可，实现代码如下：

isEmpty() {
  return this.size() === 0;
}复制代码

clear()

要清空队列元素，我们可以一直调用dequeue()方法，直至返回undefined即可或者将各变量重置为初始值即可，我们使用重置初始化的思路，代码如下：

clear() {
  this.items = {};
  this.count = 0;
  this.lowestCount = 0;
}复制代码

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类

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

  enqueue(element) {
    this.items[this.count] = element;
    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.size() === 0;
  }

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

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

  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类

首先引入我们的Queue类，然后初始化创建我们的Queue类，验证是否为空，然后进行添加删除元素，示例代码如下：

const queue = new Queue();
console.log(queue.isEmpty()); // outputs true
queue.enqueue('John');
queue.enqueue('Jack');
console.log(queue.toString()); // John,Jack
queue.enqueue('Camila');
console.log(queue.toString()); // John,Jack,Camila
console.log(queue.size()); // outputs 3
console.log(queue.isEmpty()); // outputs false
queue.dequeue(); // remove John
queue.dequeue(); // remove Jack
console.log(queue.toString()); // Camila复制代码

如下图所示演示了上述代码的执行效果：

什么是双端队列

双端队列是一个特殊的更灵活的队列，我们可以在队列的“队头”或“队尾”添加和删除元素。由于双端队列是实现了FIFO和LIFO这两个原则，也可以说是队列和堆栈结构的合体结构。

在我们生活中，比如排队买票，有的人着急或特殊情况，直接来到队伍的最前面，有的人因为其他的事情，等不了太长时间，从队尾离开了。

如何用代码实现双端队列

首先我们声明初始化一个双端队列，代码和队列的结构类似，如下段代码所示：

class Deque {
  constructor() {
    this.count = 0;
    this.lowestCount = 0;
    this.items = {};
  }
}复制代码

由于双端队列的结构和队列的结构类似，只是插入和删除更灵活而已，isEmpty(), clear(), size()和toString()相关方法保持一致，还需要增加以下相关的方法：

• addFront(element)：此方法用于在双端队列的“队头”添加元素。
• addBack(element)：此方法用于在双端队列的“队尾”添加元素。
• removeFront()：此方法用于删除双端队列的“队头”元素。
• removeBack()：此方法用于删除双端队列的“队尾”元素。
• peekFront()：此方法用于返回双端队列的“队头”元素
• peekBack()：此方法用于返回双端队列的“队尾”元素

addFront(element)

由于从双端队列的的“队头”添加元素，稍微复杂些，实现代码如下：

addFront(element) {
  if (this.isEmpty()) {
    this.addBack(element);
  } else if (this.lowestCount > 0) {
    this.lowestCount--;
    this.items[this.lowestCount] = element;
  } else {
    for (let i = this.count; i > 0; i--) { 
      this.items[i] = this.items[i - 1];
    }
    this.count++;
    this.lowestCount = 0;
    this.items[0] = element; 
  }
}复制代码

从上述代码我们可以看出，如果双端队列为空，我们复用了addBack()方法，避免书写重复的代码；如果队头元素lowestCount的变量大于0，我们将变量递减，将新添加的元素赋值给队头元素；如果lowestCount的变量为0，为了避免负值的出现，我们将队列元素整体往后移动1位，进行重新赋值，将队头索引为0的位置留给新添加的元素。

最终实现的Deque类

由于文章篇幅有限，其他的方法又很类似，不再一一介绍，完整的代码如下：

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

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

  addBack(element) {
    this.items[this.count] = element;
    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.size() === 0;
  }

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

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

  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;
  }
}复制代码

如何使用Deque类

接下来我们来验证下我们的Deque类，首先引入Deque类的文件，代码如下：

const deque = new Deque();
console.log(deque.isEmpty()); // outputs true
deque.addBack('John');
deque.addBack('Jack');
console.log(deque.toString()); // John,Jack
deque.addBack('Camila');
console.log(deque.toString()); // John,Jack,Camila
console.log(deque.size()); // outputs 3
console.log(deque.isEmpty()); // outputs false
deque.removeFront(); // remove John
console.log(deque.toString()); // Jack,Camila
deque.removeBack(); // Camila decides to leave
console.log(deque.toString()); // Jack
deque.addFront('John'); // John comes back for information
console.log(deque.toString()); // John,Jack”复制代码

实际应用举例1：击鼓传花

不知道大家玩过击鼓传花吗,笔者最怕玩这个，不知道是点背还在咋地，这个花球总和我有缘，本身就五音不全还要表演，人可丢大了。什么是击鼓传花，在这里给没玩过的朋友解释下：数人或几十人围成圆圈坐下，其中一人拿花（或一小物件）；另有一人背着大家或蒙眼击鼓（桌子、黑板或其他能发出声音的物体），鼓响时众人开始依次传花，至鼓停止为止。此时花在谁手中（或其座位前），谁就上台表演节目（多是唱歌、跳舞、说笑话；或回答问题、猜谜、按纸条规定行事等）；偶然如果花在两人手中，则两人可通过猜拳或其它方式决定负者。

今天我们要用队列实现这个游戏，稍微不同的是，拿到花球的人需要出列，直到最后一个拿到花球的人获胜。假设告诉敲鼓的人一个数字(从0开始)，按照数字循环在场的人，到达这个数字停止敲鼓，直到最后一个人为止。

大家是不是迫不及待的想知道代码如何实现？代码如下所示：

function hotFlower(elementsList, num) {
  const queue = new Queue(); 
  const elimitatedList = [];

  for (let i = 0; i < elementsList.length; i++) {
    queue.enqueue(elementsList[i]); 
  }

  while (queue.size() > 1) {
    for (let i = 0; i < num; i++) {
      queue.enqueue(queue.dequeue()); 
    }
    elimitatedList.push(queue.dequeue()); 
  }

  return {
    eliminated: elimitatedList,
    winner: queue.dequeue() 
  };
}复制代码

从上述代码我们可以看出：

• 我们声明了一个队列queue和数组elimitatedList（出局者信息）。
• 通过迭代的方式填充给定的对象elementsList并赋值给queue。
• 然后在给定的变量num之下，不断的删除队列的头元素，并插入到队尾，相当保持队列数目不变，循环依次移动队列；（循环队列）
• 到达给定数字num,删除当前队列“队头”元素，并将队头“出局者”信息，添加至数组elimitatedList。
• 直到队列的元素为1时，函数输出elimitatedList（出局者信息）和获胜者信息winner。

接下来我们来验证下，此算法是否正确，验证代码如下：

const names = ['John', 'Jack', 'Camila', 'Ingrid', 'Carl'];
const result = hotFlower(names, 7);

result.eliminated.forEach(name => {
  console.log(`${name} was eliminated from the Hot Flower game.`);
});

console.log(`The winner is: ${result.winner}`);复制代码

上述代码将会输出：

Camila was eliminated from the Hot Flower game.
Jack was eliminated from the Hot Flower game.
Carl was eliminated from the Hot Flower game.
Ingrid was eliminated from the Hot Flower game.
The winner is: John复制代码

代码运行时，队列的变化示意图如下：

实际应用举例2：验证英语回文

许多英语单词无论是顺读还是倒读，其词形和词义完全一样，如dad（爸爸）、noon（中午）、level（水平）等。最简单的方法就是反转字符串与原始字符串进行比较是否相等。从数据结构的角度我们可以运用堆栈的结构进行实现，然而用双端队列的结构实现起来也非常简单，示例代码如下：

function palindromeChecker(aString) {
    if (aString === undefined || aString === null ||
        (aString !== null && aString.length === 0)) { 
        return false;
    }
    const deque = new Deque(); 
    const lowerString = aString.toLocaleLowerCase().split(' ').join(''); 
    let isEqual = true;
    let firstChar, lastChar;

    for (let i = 0; i < lowerString.length; i++) {
        deque.addBack(lowerString.charAt(i));
    }

    while (deque.size() > 1 && isEqual) { 
        firstChar = deque.removeFront();
        lastChar = deque.removeBack(); 
        if (firstChar !== lastChar) {
            isEqual = false; 
        }
    }

    return isEqual;
}复制代码

从上述代码我们可以看出：

• 首先我们需要验证输入的字符串是否有效。
• 声明实例化一个双端队列。
• 针对输入的字符串进行转成小写、删除空格的处理。
• 然后将字符串拆成字符添加至双端队列
• 然后通过removeFront()和deque.removeBack()这两个出列方法进行比较，只要不相等就返回fasle跳出方法。
• 返回布尔变量isEqual，True为回文，fasle

接下来我们来验证下我们的算法是否正确：

console.log('a', palindromeChecker('a'));
console.log('aa', palindromeChecker('aa'));
console.log('kayak', palindromeChecker('kayak'));
console.log('level', palindromeChecker('level'));
console.log('Was it a car or a cat I saw', palindromeChecker('Was it a car or a cat I saw'));
console.log('Step on no pets', palindromeChecker('Step on no pets'));复制代码

上述代码的运行结果都返回为true。

小节

今天关于队列的介绍就到这里，我们一起学习了什么是队列和双端队列，以及如何进行代码实现。并且运用循环队列的机制实现了击鼓传花的游戏，同时又运用双端队列的结构实现了回文的验证。其实队列在我们的实际业务场景中运用还是蛮多的，比如我们要实现一个队列的消息推送机制，我们JS的event loop的时间循环机制，浏览器的页面渲染机制等等。希望本篇的内容对大家有所帮助，在实践中运用多了才能运用队列的机制解决更多的实际问题。