双端队列的定义

双端队列是一种允许我们同时从两端进行入队和出队操作的特殊队列。双端队列同时遵守了 先进先出 和 后进先出 原则，因此可以说它是把队列和栈相结合的一种数据结构。
image.png

在现实生活中，电影院、餐厅中排队的队伍就是双端队列最好的例子。例如，一个刚买了票的人如果只是还需要再问一些简单的信息，就可以直接回到队伍的头部。另外，队伍末尾的人如果赶时间，他可以直接离开队伍。

在计算机科学中，双端队列的一个常见应用是存储一系列的撤销操作。每当用户在软件中进行了一个操作，该操作会被存在一个双端队列中（就像在一个栈里）。当用户点击撤销按钮时，该操作会被从双端队列中弹出，表示它被从后面移除了。在进行了预先定义的一定数量的操作后，最先进行的操作会被从双端队列的前面移除。

基于Object对象的双端队列

与使用 Object 对象实现队列一样，我们使用 ES6 的类来创建一个基于 Object 对象的双端队列

  1. class Deque {
  2.     constructor() {
  3.       this.count = 0;
  4.     this.lowestCount = 0;
  5.     this.items = {};
  6.   }
  7. }

接下来，我们为双端队列声明一些可用的方法

addFront(element) 在双端队列的前端添加新的元素
addBack(element) 在双端队列的后端添加新的元素
removeFront() 从双端队列的前端移除第一个元素
removeBack() 从双端队列的后移除除第一个元素
peekFront() 返回双端队列 前端的第一个元素（注意：只是查看，不是删除）
peekBack() 返回双端队列 后端的第一个元素（注意：只是查看，不是删除）
isEmpty() 判断双端队列是否为空
clear() 清空双端队列中的元素
size() 返回双端队列中的元素个数
toString() 输出双端队列的字符形式

下面，我们逐一实现这些方法：

addFront 在双端队列前端添加元素

addFront 方法将一个元素添加到双端队列的前端

  1. addFront(element) {
  2.     if (this.isEmpty()) {
  3.       this.addBack(element);
  4.   } else if (this.lowestCount > 0) {
  5.       this.lowestCount--;
  6.     this.items[this.lowestCount] = element;
  7.   } else {
  8.       for (let i = this.count; i> 0; i--) {
  9.         this.items[i] = this.items[i - 1];
  10.     }
  11.     this.count++;
  12.     this.items[0] = element;
  13.   }
  14. }

要将一个元素添加到双端队列的前端，会存在三种场景：

第一种场景：双端队列是空的。在这种情况下，我们调用 addBack 方法将元素添加大双端队列的后端，也就是将元素添加到了双端队列的前端。

第二种场景：一个元素已经被从双端队列的前端删除。在这种情况下，lowestCount 的值会大于等于 1，因此，我们只需要将 lowestCount 的值减 1 并将新元素的值放在这个键 的位置上即可。如下所示 的 Deque 类的内部值：

  1. items = {
  2.   1: 8,
  3.   2: 9
  4. }
  5. count = 3;
  6. lowestCount = 1;

如果我们想将元素 7 添加到双端队列的前端，那么将lowestCount的值减 1（新的值是 0），7 会成为键0的值

第三种场景：lowestCount 为 0的情况。在这种情况下，为了便于演示，我们把本场景看作使用数组。要在第一位添加一个新元素，我们需要将所有元素后移一位来空出第一个位置。我们从最后一位开始迭代所有的值，并为元素赋上索引值减 1 位置的值。在所有的元素都移动完后，第一位将是空闲状态，这样就可以用需要添加的新元素来覆盖它了。

addBack 在双端队列后端添加元素

addBack 方法将一个元素添加到双端队列的后端

  1. addBack(element) {
  2.     this.items[this.count] = element;
  3.   this.count++
  4. }

removeFront 移除双端队列前端的第一个元素

removeFront 方法会从双端队列的前端移除第一个元素

  1. removeFront() {
  2.     if (this.isEmpty()) {
  3.       return undefined;
  4.   }
  6.   const result = this.items[this.lowestCount];
  7.   delete this.items[this.lowestCount];
  8.   this.lowestCount++;
  9.   return result;
  10. }

removeBack 移除双端队列后端的第一个元素

removeBack 方法会会从双端队列的后端移除第一个元素

  1. removeBack() {
  2.     if (this.isEmpty()) {
  3.       return undefined;
  4.   }
  6.   this.count--;
  7.   const result = this.items[this.count];
  8.   delete this.items[this.count];
  9.   return result
  10. }

peekFront 返回双端队列前端的第一个元素

peekFront 方法返回双端队列前端的第一个元素，注意，只是查看元素，不是移除元素

  1. peekFront() {
  2.     if (this.isEmpty()) {
  3.       return undefined;
  4.   }
  5.   return this.items[this.lowestCount]
  6. }

peekBack 返回双端队列后端的第一个元素

peekBack 方法返回双端队列后端的第一个元素

  1. peekBack() {
  2.     if (this.isEmpty()) {
  3.       return undefined;
  4.   }
  5.   return this.items[this.count - 1]
  6. }

isEmpty 判断双端队列是否为空

  1. isEmpty() {
  2.     return this.size() === 0
  3. }

clear 清空双端队列中的元素

  1. clear() {
  2.     this.items = {};
  3.   this.count = 0;
  4.   this.lowestCount = 0;
  5. }

size 返回双端队列中的元素个数

  1. size() {
  2.     return this.count - this.lowestCount
  3. }

toString 输出双端队列的字符形式

  1. toString() {
  2.     if (this.isEmpty()) {
  3.       return '';
  4.   }
  5.   let objString = `${this.items[this.lowestCount]}`;
  6.   for (let i = this.lowestCount + 1, i < this.count; i++) {
  7.       objString = `${objString}, ${this.items[i]}`l
  8.   }
  9.   return objString
  10. }

完整代码

  1. class Deque {
  2.   constructor() {
  3.     this.count = 0;
  4.     this.lowestCount = 0;
  5.     this.items = {};
  6.   }
  8.   // 在双端队列前端添加元素
  9.   addFront(element) {
  10.     if (this.isEmpty()) {
  11.       this.addBack(element);
  12.     } else if (this.lowestCount > 0) {
  13.       this.lowestCount--;
  14.       this.items[this.lowestCount] = element;
  15.     } else {
  16.       for (let i = this.count; i > 0; i--) {
  17.         this.items[i] = this.items[i - 1];
  18.       }
  19.       this.count++;
  20.       this.items[0] = element;
  21.     }
  22.   }
  24.     // 在双端队列后端添加元素
  25.   addBack(element) {
  26.     this.items[this.count] = element;
  27.     this.count++;
  28.   }
  30.     // 在双端队列前端移除元素
  31.   removeFront() {
  32.     if (this.isEmpty()) {
  33.       return undefined;
  34.     }
  35.     const result = this.items[this.lowestCount];
  36.     delete this.items[this.lowestCount];
  37.     this.lowestCount++;
  38.     return result;
  39.   }
  41.   // 在双端队列后端移除元素
  42.   removeBack() {
  43.     if (this.isEmpty()) {
  44.       return undefined;
  45.     }
  46.     this.count--;
  47.     const result = this.items[this.count];
  48.     delete this.items[this.count];
  49.     return result;
  50.   }
  52.   // 查看双端队列的前端的第一个元素
  53.   peekFront() {
  54.     if (this.isEmpty()) {
  55.       return undefined;
  56.     }
  57.     return this.items[this.lowestCount];
  58.   }
  60.   // 查看双端队列的后端的第一个元素
  61.   peekBack() {
  62.     if (this.isEmpty()) {
  63.       return undefined;
  64.     }
  65.     return this.items[this.count - 1];
  66.   }
  68.   // 判断双端队列是否为空
  69.   isEmpty() {
  70.     return this.size() === 0;
  71.   }
  73.   // 清空双端队列
  74.   clear() {
  75.     this.items = {};
  76.     this.count = 0;
  77.     this.lowestCount = 0;
  78.   }
  80.   // 返回双端队列的长度
  81.   size() {
  82.     return this.count - this.lowestCount;
  83.   }
  85.   // 将双端队列转换成字符串
  86.   toString() {
  87.     if (this.isEmpty()) {
  88.       return '';
  89.     }
  90.     let objString = `${this.items[this.lowestCount]}`;
  91.     for (let i = this.lowestCount + 1; i < this.count; i++) {
  92.       objString = `${objString},${this.items[i]}`;
  93.     }
  94.     return objString;
  95.   }
  96. }

基于数组的双端队列

同样，我们可以使用的 ES6 的类来创建一个基于数组的双端队列：

  1. class Deque {
  2.     constructor() {
  3.       this.items = []
  4.   }
  5. }

同样，我们为双端队列声明一些可用的方法:
addFront(element) 在双端队列的前端添加新的元素
addBack(element) 在双端队列的后端添加新的元素
removeFront() 从双端队列的前端移除第一个元素
removeBack() 从双端队列的后移除除第一个元素
peekFront() 返回双端队列 前端的第一个元素（注意：只是查看，不是删除）
peekBack() 返回双端队列 后端的第一个元素（注意：只是查看，不是删除）
isEmpty() 判断双端队列是否为空
clear() 清空双端队列中的元素
size() 返回双端队列中的元素个数
toString() 输出双端队列的字符形式

下面，我们逐一实现这些方法：

addFront 在双端队列前端添加元素

  1. addFront(element) {
  2.     this.items.unshift(element);
  3. }

addBack 在双端队列后端添加元素

  1. addBack(element) {
  2.     this.items.push(element);
  3. }

removeFront 移除双端队列前端的第一个元素

  1. removeFront() {
  2.     if (this.isEmpty()) {
  3.       return undefined;
  4.   }
  5.   return this.items.shift()
  6. }

removeBack() 移除双端队列后端的第一个元素

  1. removeBack() {
  2.     if (this.isEmpty()) {
  3.       return undefined;
  4.   }
  5.   return this.items.pop();
  6. }

peekFront() 返回双端队列前端的第一个元素

  1. peekFront() {
  2.     if (this.isEmpty()) {
  3.       return undefined;
  4.   }
  5.   return this.items[0];
  6. }

peekBack() 返回双端队列后端的第一个元素

  1. peekBack() {
  2.     if (this.isEmpty()) {
  3.       return undefined;
  4.   }
  5.   return this.items[this.items.length - 1];
  6. }

isEmpty() 判断双端队列是否为空

  1. isEmpty() {
  2.     return this.size() === 0;
  3. }

clear() 清空双端队列中的元素

  1. clear() {
  2.     this.items = [];
  3. }

size() 返回双端队列中的元素个数

  1. size() {
  2.     return this.items.length;
  3. }

toString() 输出双端队列的字符形式

  1. toString() {
  2.     if (this.isEmpty()) {
  3.       return '';
  4.   }
  5.   return this.items.toString();
  6. }

完整代码

  1. class Deque {
  2.   constructor() {
  3.     this.items = [];
  4.   }
  6.   addFront(element) {
  7.     this.items.unshift(element
  8.   }
  10.   addBack(element) {
  11.     this.items.push(element)
  12.   }
  14.   removeFront() {
  15.     if (this.isEmpty()) {
  16.       return undefined;
  17.     }
  18.     return this.items.shift();
  20.   }
  22.   removeBack() {
  23.     if (this.isEmpty()) {
  24.       return undefined;
  25.     }
  26.     return this.items.pop();
  27.   }
  29.   peekFront() {
  30.     if (this.isEmpty()) {
  31.       return undefined;
  32.     }
  33.     return this.items[0];
  34.   }
  36.   peekBack() {
  37.     if (this.isEmpty()) {
  38.       return undefined;
  39.     }
  40.     return this.items[this.items.length - 1];
  41.   }
  43.   isEmpty() {
  44.     return this.size() === 0;
  45.   }
  47.   clear() {
  48.     this.items = [];
  49.   }
  51.   size() {
  52.     return this.items.length;
  53.   }
  55.   toString() {
  56.     if (this.isEmpty()) {
  57.       return '';
  58.     }
  59.     return this.items.toString();
  60.   }
  61. }

双端队列的应用

回文检查器

回文是正反都能读通的单词、词组、数或句子，例如数字：11、131，单词：level、reviver。

有不同的算法可以检查一个词组或字符串是否为回文，最简单的方式时将字符串反向排列并检查它和原字符串是否相同，如果两者相同，那么它就是一个回文。我们也可以用栈来实现，但是利用数据结构来解决这个问题的最简单方法是使用双端队列。

思路分析：

  1. 首先检查传入的字符串是否合法，如果不合法，返回 false；
  2. 由于可能接收到包含大小写字母的字符串，因此需要将所有字母转换为小写，并同时移除所有的空格；
  3. 然后将字符串中的所有字符都放入双端队列中；
  4. 同时从双端队列的两端移除一个元素，比较两个字符是否相同，直至双端队列中只剩下一个元素，如果此时比较的结果是两个字符相同，则这个字符串是一个回文，否则这个字符串不是一个回文

算法实现：

  1. const palindromeChecker = (str) => {
  2.   // 检查传入的字符串是否合法
  3.     if (str === undefined || str === null || (str !== null && str.length === 0)) {
  4.       return false;
  5.   }
  7.   const deque = new Deque();
  8.   // 将字符串转换成小写，移除空格
  9.   let lowerString = str.toLocaleLowerCase().split(' ').join('');
  10.   let isEqual = true;
  11.   let firstChar, lastChar;
  13.   // 将字符串放入双端队列中
  14.   for (let i = 0; i < lowerString.length; i++) {
  15.       deque.addBack(lowerString.charAt(i));
  16.   }
  18.   // 同时在两端对字符串进行出队操作，比较两个字符是否相同
  19.   while (deque.size() > 1 && isEqual) {
  20.       firstChar = deque.removeFront();
  21.     lastChar = deque.removeBack();
  22.     if (firstChar !== lastChar) {
  23.         isEqual = false;
  24.     }
  25.   }
  27.   return isEqual;
  28. }