JS实现队列和双端队列数据结构

本部分介绍文章预计阅读需要四分钟，全文948个字。

队列（queue），也是常见的数据结构之一。在生活中，各个商场中等待的队伍，羽毛球筒中的羽毛球，计算机打印文档的序列，都是队列的生动实例，和栈（stack）不同的是，它的数据元素遵循FIFO，即先进先出，先来先服务的原则。

下面，我们尝试使用javascript实现一个队列。

class Queue {
  constructor() {
    this.items = {}; // 队列中的元素集合
    this.count = 0; // 队列中元素的个数
    this.lowestCount = 0; // 指定队列中最前排的元素位置
  }
}

然后实现队列中常用的方法

enqueue(elements) 向队列中添加一个或者多个元素
dequeue() 删除队列的第一个元素
peek() 返回队列的第一个元素
isEmpty() 队列是否为空
size() 队列的大小
clear() 清空队列
toString() 将队列中的元素转换成字符串输出

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.count- this.lowestCount === 0;
}
size() {
  return this.count - this.lowestCount;
}
clear() {
  this.items = {};
  this.count = 0;
  this.lowestCount = 0;
}
toString() {
  if(this.isEmpty()) {
    return '';
  }
  const result = `${this.items[this.lowestCount]}`;
  for (let i = this.lowestCount + 1; i < this.size() - 1; i++) {
      result += `,${this.items[i]}`;
  }
  return result;
}

队列和栈十分类似，不同在于dequeue和peek，是由于他们删除元素的特性不同，一个先进先出，一个后进先出；
目前，我们实现了从后边添加元素的队列，下面，我们来实现双端队列（deque），也就是，前端和后端都可以添加元素的队列；
双端队列在生活中比如电影院的排队，餐厅的排队也很常见，后边的人可以先走，前面的人也可以再返回问下这部电影是不是要3D眼镜之类；
在计算机中，双端队列应用于存储撤销操作，也就是Ctrl-Z，用户可以马上撤销最后进行的操作，而存储了一定的操作之后，前边进行的操作也会被移除出去；
可以说，deque是结合了栈以及队列的应用；

它的构造函数和队列相同，如下代码所示：

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

双端队列使用的方法有：

addFront(element) 在队列前端添加元素
addBack(element) 在队列后端添加元素，同Queue中的enqueue
removeFront() 移除队列前端的元素，同Queue中的dequeue
removeBack() 移除队列后端的元素，同Stack中的pop
peekFront() 返回队列前端的第一个元素，同Queue中的peek
peekBack() 返回队列后端的第一个元素，同Stack中的peek

对应的clear, size, isEmpty, toString等也不再赘述；

下边我们主要实现addFront这个方法

addFront(element) {
// 如果为空，可以直接使用addBack方法
  if(this.isEmpty()) {
    addBack(element);
  } else if(this.lowestCount > 0){ 
// 如果最小坐标大于0，那么把最小坐标往前移动，直接赋值给前一个
    this.lowestCount--;
    this.items[this.lowestCount] = element;
  } else {
// 如果最小坐标已经是0了，那么把所有元素后移，0放置添加的元素，count加一
    for(let i = this.count; i > 0; i--) {
      this.items[i] = this.items[i - 1];
    }
    this.items[0] = element;
    this.lowestCount = 0;
    this.count++;
  }
}

现在，我们创建了这两种队列的数据结构之后，可以用来解决一些实际的问题。
比如，循环队列，这个在现实中有一个游戏可以代表它，就是击鼓传花游戏，人们围坐成为一个圈，在音乐响起的时候，传递花朵，音乐停止，花朵到谁手中，谁就淘汰，最终留下的一个人胜出。

下面的示例，是模仿击鼓传花的代码：

// elementList 玩游戏的人的列表， num 在第几秒音乐停止
function hotPotato(elementList, num) {
  const queue = new  Qeque();
  const eliminatedList = []; // 淘汰的人的列表
  // 先把所有玩游戏的人放入队列
  for (let i = 0; i < elementList.length; i++) {
    queue.enqueue(elementList[i]);
  }
// 游戏开始，当人数大于1就一直游戏
  while(queue.size() > 1) {
// 每次到结束音乐的时间之后，把轮到队列前端的人移除
    for (let i = 0; i < num; i++) {
       queue.enqueue(queue.dequeue());
    }
    eliminatedList.push(queue.dequeue());
  }
// 返回淘汰的列表，和最后的赢家
  return { eliminated: eliminatedList, winner: queue.dequeue() };
}

算法问题中经常见到检测回文字符串，而双端队列可以说是最为方便的一种解决它的数据结构，实现检测回文字符串的代码如下：

function palindromeChecker(aString) {
  // 首先判断传入的字符串是否合法
  if(aString === null || aString ===  undefined || 
  (aString !== null && aString.length === 0)) {
    return false;
  }
  const deque = new Deque();
  const lowerString = aString.toLocaleLowerCase().split(' ').join(''); // 先转换成小写，如果句子有空格，可以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;
}

最后补充一个和队列相关的知识，当我们打开浏览器，就会创建一个任务队列，每个标签都是单线程的处理所有任务，这就叫做事件循环，包括渲染HTML，执行javascript代码，处理用户交互（鼠标点击，输入）、执行异步请求等。
到此为止，队列相关的内容总结完毕，觉得有用的友友可以点一个赞，一起学习~