JavaScript内核与高级编程之：`JavaScript`的`Deque`：如何实现双端队列。

各位靓仔靓女，早上好！我是你们的老朋友，今天要跟大家聊聊JavaScript里一个稍微冷门但又实用的数据结构：双端队列（Deque）。 别怕，听名字唬人，其实用起来可香了！

开场白：队列这玩意儿，你得懂！

咱们先回忆一下基础的队列。 队列就像你去银行排队，先进先出（FIFO）。新来的人排在队尾，办完事儿的人从队首离开。JavaScript里可以用数组模拟：

let queue = [];

// 入队 (队尾添加)
queue.push(1);
queue.push(2);
queue.push(3);

// 出队 (队首移除)
let first = queue.shift(); // first 现在是 1
console.log(queue); // 输出: [2, 3]

简单粗暴，对吧？ 但是，问题来了！ shift() 操作在数组头部移除元素，涉及到后面所有元素的移动，如果队列很长，效率就比较低。 这时候，就需要我们的主角——双端队列登场了！

什么是双端队列？ (Deque = Double Ended Queue)

顾名思义，双端队列就是两端都可以进出的队列。 你可以从队头添加元素，也可以从队尾添加元素；可以从队头移除元素，也可以从队尾移除元素。 这就灵活多了！ 想象一下，你排队的时候，突然有人插队到队首，或者你突然想从队尾溜走，双端队列就能完美模拟这种场景。

为什么要用双端队列？

双端队列的优势在于：

• 灵活: 两端都可以操作，满足更多场景需求。
• 高效: 某些实现方式下，两端操作的时间复杂度都是 O(1)，比数组的 shift() 操作高效。

JavaScript 实现双端队列的几种方式

咱们来研究一下，在 JavaScript 里，如何实现一个双端队列。 主要有以下几种方式：

1. 使用数组模拟 (简单但可能低效)
2. 使用对象模拟 (优化版)
3. 使用链表 (更高级)

方式一：数组模拟

这是最简单直接的方式。 利用数组的 push()、pop()、unshift()、shift() 方法来实现双端队列的功能。

class Deque {
  constructor() {
    this.items = [];
  }

  addFront(element) {
    this.items.unshift(element);
  }

  addBack(element) {
    this.items.push(element);
  }

  removeFront() {
    if (this.isEmpty()) {
      return undefined;
    }
    return this.items.shift();
  }

  removeBack() {
    if (this.isEmpty()) {
      return undefined;
    }
    return this.items.pop();
  }

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

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

  isEmpty() {
    return this.items.length === 0;
  }

  size() {
    return this.items.length;
  }

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

  toString() {
    return this.items.toString();
  }
}

// 示例
let deque = new Deque();
deque.addFront(1);
deque.addBack(2);
deque.addFront(0);
console.log(deque.toString()); // 输出: 0,1,2
console.log(deque.removeFront()); // 输出: 0
console.log(deque.removeBack()); // 输出: 2
console.log(deque.toString()); // 输出: 1

• addFront(element): 在队头添加元素。
• addBack(element): 在队尾添加元素。
• removeFront(): 从队头移除元素。
• removeBack(): 从队尾移除元素。
• peekFront(): 查看队头元素。
• peekBack(): 查看队尾元素。
• isEmpty(): 判断队列是否为空。
• size(): 返回队列的大小。
• clear(): 清空队列。
• toString(): 将队列转换为字符串。

优缺点分析:

• 优点: 实现简单，代码量少。
• 缺点: unshift() 和 shift() 操作效率较低，特别是当队列很长时。

方式二：对象模拟 (优化版)

为了解决数组模拟的效率问题，我们可以使用对象来模拟双端队列。 核心思想是维护两个指针：lowestCount 指向队头，highestCount 指向队尾。 这样，我们就可以避免数组元素的移动。

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

  addFront(element) {
    if (this.isEmpty()) {
      this.addBack(element); //如果为空，直接调用addBack
    } else if (this.lowestCount > 0) {
      this.lowestCount--;
      this.items[this.lowestCount] = element;
    } else {
      // 当lowestCount为0时，需要将所有元素后移一位
      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(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()) {
      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.items = {};
    this.count = 0;
    this.lowestCount = 0;
  }

  toString() {
    if (this.isEmpty()) {
      return '';
    }
    let str = `${this.items[this.lowestCount]}`;
    for (let i = this.lowestCount + 1; i < this.count; i++) {
      str = `${str},${this.items[i]}`;
    }
    return str;
  }
}

// 示例
let deque = new Deque();
deque.addFront(1);
deque.addBack(2);
deque.addFront(0);
console.log(deque.toString()); // 输出: 0,1,2
console.log(deque.removeFront()); // 输出: 0
console.log(deque.removeBack()); // 输出: 2
console.log(deque.toString()); // 输出: 1

• count: 记录队列中元素的总数。
• lowestCount: 记录队列头部的索引。
• items: 使用对象存储队列中的元素。

优缺点分析:

• 优点: 避免了数组元素的移动，提高了效率。 addBack, removeFront, removeBack操作都是O(1)复杂度。
• 缺点: 代码稍微复杂一些。当需要addFront，且lowestCount为0时，需要所有元素后移，复杂度是O(n)。

方式三：链表实现 (更高级)

使用链表实现双端队列，可以达到更好的性能。 链表的特点是插入和删除节点的时间复杂度都是 O(1)。

class Node {
  constructor(element) {
    this.element = element;
    this.next = null;
    this.prev = null; // 双向链表需要 prev 指针
  }
}

class Deque {
  constructor() {
    this.head = null;
    this.tail = null;
    this.count = 0;
  }

  addFront(element) {
    const node = new Node(element);
    if (this.isEmpty()) {
      this.head = node;
      this.tail = node;
    } else {
      node.next = this.head;
      this.head.prev = node;
      this.head = node;
    }
    this.count++;
  }

  addBack(element) {
    const node = new Node(element);
    if (this.isEmpty()) {
      this.head = node;
      this.tail = node;
    } else {
      node.prev = this.tail;
      this.tail.next = node;
      this.tail = node;
    }
    this.count++;
  }

  removeFront() {
    if (this.isEmpty()) {
      return undefined;
    }
    const removedNode = this.head;
    if (this.count === 1) {
      this.head = null;
      this.tail = null;
    } else {
      this.head = this.head.next;
      this.head.prev = null; // 删除之前的 head 的 prev 引用
    }
    this.count--;
    return removedNode.element;
  }

  removeBack() {
    if (this.isEmpty()) {
      return undefined;
    }
    const removedNode = this.tail;
    if (this.count === 1) {
      this.head = null;
      this.tail = null;
    } else {
      this.tail = this.tail.prev;
      this.tail.next = null; // 删除之前的 tail 的 next 引用
    }
    this.count--;
    return removedNode.element;
  }

  peekFront() {
    if (this.isEmpty()) {
      return undefined;
    }
    return this.head.element;
  }

  peekBack() {
    if (this.isEmpty()) {
      return undefined;
    }
    return this.tail.element;
  }

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

  size() {
    return this.count;
  }

  clear() {
    this.head = null;
    this.tail = null;
    this.count = 0;
  }

  toString() {
    if (this.isEmpty()) {
      return '';
    }
    let str = '';
    let current = this.head;
    while (current) {
      str += current.element + (current.next ? ',' : '');
      current = current.next;
    }
    return str;
  }
}

// 示例
let deque = new Deque();
deque.addFront(1);
deque.addBack(2);
deque.addFront(0);
console.log(deque.toString()); // 输出: 0,1,2
console.log(deque.removeFront()); // 输出: 0
console.log(deque.removeBack()); // 输出: 2
console.log(deque.toString()); // 输出: 1

• Node: 链表节点类，包含 element、next 和 prev 属性。
• head: 指向链表头部的指针。
• tail: 指向链表尾部的指针。
• count: 记录链表中节点的数量。

优缺点分析:

• 优点: addFront, addBack, removeFront, removeBack 的时间复杂度都是 O(1)，性能最好。
• 缺点: 代码实现相对复杂。

性能对比

为了更直观地了解这三种实现方式的性能差异，我们用表格来总结一下：

操作	数组模拟	对象模拟	链表实现
addFront	O(n)	O(n)	O(1)
addBack	O(1)	O(1)	O(1)
removeFront	O(n)	O(1)	O(1)
removeBack	O(1)	O(1)	O(1)
peekFront	O(1)	O(1)	O(1)
peekBack	O(1)	O(1)	O(1)
isEmpty	O(1)	O(1)	O(1)
size	O(1)	O(1)	O(1)

双端队列的应用场景

双端队列虽然不如数组和链表常用，但在某些场景下却非常有用：

• 历史记录: 浏览器的前进和后退功能可以用双端队列实现。
• 撤销/重做: 文本编辑器的撤销和重做功能也可以用双端队列实现。
• 循环队列: 双端队列可以用来实现循环队列，例如在多线程环境中，生产者和消费者可以使用循环队列来共享数据。
• 算法优化: 某些算法，例如 A* 搜索算法，可以使用双端队列来优化性能。
• 回文检查: 可以使用双端队列来检查一个字符串是否是回文。 将字符串的字符逐个添加到队列的尾部，然后同时从队列的头部和尾部移除字符进行比较。 如果所有字符都匹配，则该字符串是回文。

回文检查示例

function isPalindrome(str) {
  const deque = new Deque();
  str = str.toLowerCase().replace(/[^a-zA-Z0-9]+/g, ''); // 移除特殊字符和空格

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

  while (deque.size() > 1) {
    const first = deque.removeFront();
    const last = deque.removeBack();
    if (first !== last) {
      return false;
    }
  }

  return true;
}

console.log(isPalindrome("madam")); // true
console.log(isPalindrome("racecar")); // true
console.log(isPalindrome("A man, a plan, a canal: Panama")); // true
console.log(isPalindrome("hello")); // false

总结

今天我们一起学习了 JavaScript 中双端队列的概念、实现方式和应用场景。 记住，没有银弹！ 选择哪种实现方式，取决于你的具体需求。 如果对性能要求不高，数组模拟最简单； 如果对性能要求较高，链表实现是更好的选择。 希望大家以后遇到类似的问题，能够灵活运用双端队列来解决。

课后作业

1. 尝试用你最喜欢的 JavaScript 框架 (例如 React, Vue, Angular) 实现一个简单的历史记录组件，使用双端队列来管理历史记录。
2. 研究一下 JavaScript 中还有哪些类似的数据结构，例如优先队列、堆等。

好啦，今天的讲座就到这里。 咱们下期再见！ 祝大家编码愉快！