如何在 JavaScript 中实现双端队列数据结构？

Question

我正在学习使用JavaScript实现数据结构

现在我的重点是如何实现deque？

编辑：从下面的评论中，我得到了有关如何实现基于数组的deque的有用指导。是否有一种使用类来实现基于对象的deque的方向？

我了解了一些要点，例如我需要：

• addFront()
• removeFront()
• peekFront()

---

• addBack()
• removeBack()
• peekBack()

---

但我对一些问题感到困惑：

• 我需要多少指针？至少，我知道从队列中我需要两个（头尾）指针，但不确定在双端队列中是否需要更多。

• 在这种情况下，JavaScript中哪种数据类型方便作为基础？例如，我在Youtube上看到一些导师谈论圆形数组，但这在JS中未知。

编辑2：

我正在跟随一本名为《JavaScript数据结构和算法学习指南（第3版）》的书籍。

在该书的第5章中，作者仅基于对象和一些变量开始实现Deque。

但是我不明白他是怎么做到的，因为代码已经加密了，但我仍然可以从中获取他的文件并测试他的方法Github存储库

我可以说@trincot的答案非常接近书籍作者的方法

但当我比较我的结果时[1 = 作者 - 2 = @trincot]：

根据书籍索引，关于链接列表的内容在第6章中才有，所以我没有预料到他的解决方案将基于他之前没有提到过的东西

如果我遗漏了任何要点，请告诉我...谢谢

- Ayman Morsy

---

默认的JS数组已经具备了这样的结构：push()、pop()、shift()、unshift()以及标准索引访问，它们能够提供你所需要的全部工具。 - Sirko

@Sirko，您的意思是我不需要使用deque，只需使用默认JS数组就可以完成工作吗？ - Ayman Morsy

一个JS数组支持你需要的所有方法。如果需要抑制任何其他方法，那么你将需要一个包装器或类似的东西来限制访问（也许还包括map()等）。 - Sirko

@AymanMorsy 请跟随我刚刚发布的链接。根本没有“加密”。 - Bergi

让我们在聊天中继续这个讨论。 - Ayman Morsy

Answer 1

如评论所述 - 以及维基百科提到的 - JavaScript通过其Array类/原型本身支持双端队列操作：push，pop，shift，unshift。然而，这并不能提供最佳的时间效率，而随着数据集的增大，时间效率变得越来越重要。

如果您需要处理较大数据集的良好性能，您将需要编写自己的实现。您可以选择使用双向链表，其中您只需要两个“指针”。值得注意的是，在JavaScript中，我们实际上并不谈论指针，而是对象。在JavaScript中，将对象作为值的变量或属性实际上是JavaScript中的“引用”。

或者，您可以选择使用循环数组。由于在JavaScript中，标准数组不保证像C语言中那样是连续的数组，因此您实际上不需要使用Array实例。一个普通的对象（或Map）就足够了。

因此，这里有两种可能的实现方式：

双向链表

class Deque {
    constructor() {
        this.front = this.back = undefined;
    }
    addFront(value) {
        if (!this.front) this.front = this.back = { value };
        else this.front = this.front.next = { value, prev: this.front };
    }
    removeFront() {
        let value = this.peekFront();
        if (this.front === this.back) this.front = this.back = undefined;
        else (this.front = this.front.prev).next = undefined;
        return value;
    }
    peekFront() { 
        return this.front && this.front.value;
    }
    addBack(value) {
        if (!this.front) this.front = this.back = { value };
        else this.back = this.back.prev = { value, next: this.back };
    }
    removeBack() {
        let value = this.peekBack();
        if (this.front === this.back) this.front = this.back = undefined;
        else (this.back = this.back.next).back = undefined;
        return value;
    }
    peekBack() { 
        return this.back && this.back.value;
    }
}

// demo
let deque = new Deque;
console.log(deque.peekFront()); // undefined
deque.addFront(1);
console.log(deque.peekBack()); // 1
deque.addFront(2);
console.log(deque.removeBack()); // 1
deque.addFront(3);
deque.addFront(4);
console.log(deque.peekBack()); // 2
deque.addBack(5);
deque.addBack(6);
console.log(deque.peekBack()); // 6
console.log(deque.removeFront()); // 4
console.log(deque.removeFront()); // 3
console.log(deque.removeFront()); // 2
console.log(deque.removeFront()); // 5
console.log(deque.removeFront()); // 6
console.log(deque.removeFront()); // undefined

循环“数组”

class Deque {
    constructor() {
        this.data = {}; // Or Array, but that really does not add anything useful
        this.front = 0;
        this.back = 1;
        this.size = 0;
    }
    addFront(value) {
        if (this.size >= Number.MAX_SAFE_INTEGER) throw "Deque capacity overflow";
        this.size++;
        this.front = (this.front + 1) % Number.MAX_SAFE_INTEGER;
        this.data[this.front] = value;
    }
    removeFront()   {
        if (!this.size) return;
        let value = this.peekFront();
        this.size--;
        delete this.data[this.front];
        this.front = (this.front || Number.MAX_SAFE_INTEGER) - 1;
        return value;
    }
    peekFront()     { 
        if (this.size) return this.data[this.front];
    }
    addBack(value) {
        if (this.size >= Number.MAX_SAFE_INTEGER) throw "Deque capacity overflow";
        this.size++;
        this.back = (this.back || Number.MAX_SAFE_INTEGER) - 1;
        this.data[this.back] = value;
    }
    removeBack()   {
        if (!this.size) return;
        let value = this.peekBack();
        this.size--;
        delete this.data[this.back];
        this.back = (this.back + 1) % Number.MAX_SAFE_INTEGER;
        return value;
    }
    peekBack()     { 
        if (this.size) return this.data[this.back];
    }
}

// demo
let deque = new Deque;
console.log(deque.peekFront()); // undefined
deque.addFront(1);
console.log(deque.peekBack()); // 1
deque.addFront(2);
console.log(deque.removeBack()); // 1
deque.addFront(3);
deque.addFront(4);
console.log(deque.peekBack()); // 2
deque.addBack(5);
deque.addBack(6);
console.log(deque.peekBack()); // 6
console.log(deque.removeFront()); // 4
console.log(deque.removeFront()); // 3
console.log(deque.removeFront()); // 2
console.log(deque.removeFront()); // 5
console.log(deque.removeFront()); // 6
console.log(deque.removeFront()); // undefined

方法在尝试从空的双端队列中检索值时，会返回undefined。

在我的测试中，随着数据集的增长，链表解决方案成为了赢家。对于小型数据集，本机数组可能是最佳选择。但这也取决于引擎和双端队列元素的数据类型：整数的结果与对象或字符串的结果不同。因此，我建议根据您的实际数据和双端队列操作进行一些基准测试，以确定哪种实现对您的情况最佳。

- trincot

---

因为Native Array没有原生deque操作而被downvoted...deque是恒定时间，Array对于push / pop是恒定时间，但对于shift / unshift是O（N）时间。 - Alexander Mills

@Alexander，时间复杂度是算法的一个方面，而不是数据结构。这也是为什么Wikipedia没有将时间复杂度列为要求，但将复杂度列为几种不同实现的属性，并将JavaScript列为具有deque实现的方法push、pop、unshift、shift的语言。 - trincot

我不认为deque是过于正式的，但这篇文章确实提到了常数时间操作作为指示 - https://en.wikipedia.org/wiki/Double-ended_queue - Alexander Mills

那篇文章就是我所提到的，正如我所说，它列出了几个没有所有四种方法的O（1）复杂性实现，并包括JavaScript作为一个实现。 - trincot

所以，我撤销了你对我的答案的编辑，因为在我看来（并且写答案的意图），我们可以说JavaScript实现了一个双端队列，尽管我们可能会考虑时间复杂度。 - trincot

Answer 2

简单实现 Dequeue（双端队列）：

const dequeue = [];

// push element from rear end
dequeue.push(3); // [3]
dequeue.push(8); // [3, 8]

// push element from front end
dequeue.unshift(5); // [5, 3, 8]
dequeue.unshift(11); // [11, 5, 3, 8]     

// pop element from rear end
dequeue.pop(); // [11, 5, 3]

// pop element from front end
dequeue.shift(); // [5, 3]

- Ashish Kumar

---

在双端队列中，pushleft 操作的时间复杂度应该是 O(1)，但是 JS 数组的 unshift() 操作的时间复杂度却是 O(n)，这是错误的。 - Azamat Abdullaev

Answer 3

的双向链表，但已经重构并进行了类型化：

type DequeNode<T> = {
  value: T;
  prev?: DequeNode<T>;
  next?: DequeNode<T>;
};

class Deque<T = any> {
  front?: DequeNode<T>;
  back?: DequeNode<T>;

  constructor(...initialValues: T[]) {
    initialValues.forEach(initialValue => {
      this.addBack(initialValue);
    });
  }

  addFront(value: T) {
    if (!this.front) {
      this.front = this.back = { value };
      return;
    }

    this.front = this.front.next = { value, prev: this.front };
  }

  removeFront() {
    if (!this.front) {
      return;
    }

    const value = this.peekFront();

    if (this.front === this.back) {
      this.front = undefined;
      this.back = undefined;
      return value;
    }

    (this.front = this.front.prev!).next = undefined;
    return value;
  }

  peekFront() {
    return this.front?.value;
  }

  addBack(value: T) {
    if (!this.front) {
      this.front = this.back = { value };
      return;
    }

    this.back = this.back!.prev = { value, next: this.back };
  }

  removeBack() {
    if (!this.back) {
      return;
    }

    const value = this.peekBack();

    if (this.front === this.back) {
      this.front = undefined;
      this.back = undefined;
      return value;
    }

    (this.back = this.back.next!).prev = undefined;
    return value;
  }

  peekBack() {
    return this.back?.value;
  }
}

- Eugene P.

Answer 4

和任何尝试理解新事物一样，采用比较方法会很有帮助。

JS数组是双端队列，因为您可以直接修改前端。在Python中，您无法像使用“附加”和“弹出”一样仅通过内置列表结构支持后向修改。如果您需要开始添加和删除前缀项，则需要显式添加对双端队列的支持（通过在模块顶部添加from collections import deque），并使用专用构造函数创建对象（d=deque([1,2,3])）。只有这样，您才能执行popleft和appendleft操作（在JS中称为unshift和shift）。

同样，JS中不需要这些操作，JS数组的实现本身就支持此功能。要了解跨语言环境的术语，请参见维基百科的表格。

https://en.wikipedia.org/wiki/Double-ended_queue#Operations

- pavol.kutaj

---

问题在于JavaScript数组操作的时间复杂度。从真正的双端队列（Deque）前部弹出一个项目的复杂度为O(1)，而从普通数组前面弹出项目的复杂度为O(n)，因为每个后续项都需要向左移动一个位置。 - Todd

有关以上内容的更多信息，请参见https://leetcode.com/explore/learn/card/fun-with-arrays/525/inserting-items-into-an-array/3244/。 - pavol.kutaj