如何在javascript中实现deque数据结构？

Question

我正在使用 javascript 学习数据结构

我现在的重点是如何实现双端队列？

编辑：从下面的评论中我得到了有关如何实施
deque based array
的有用指示。有没有指导如何使用类来实现
deque based object
？

我明白了一些我需要的要点：

addFront()
删除Front()
peekFront()

addBack()
移除返回()
peekBack()

但我对某些点感到困惑:

我需要多少指针？至少我从 queue 知道我需要两个（头尾）指针，但不确定在 deque
在这种情况下，JavaScript 中哪种数据类型作为基础比较方便？我在 youtube 上看到一些导师在谈论圆形数组，例如我在 JS 中不知道的。

编辑2：

我正在关注一本书：学习 javascript 数据结构和算法第三版

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

但我不明白他是如何做到这一点的，因为代码已加密，但我仍然可以从 github 存储库

访问他的文件并测试他的方法

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

但是当我比较结果时，我得到这个 [1 = 作者 - 2 = @trincot] ：

根据书籍索引，关于链表出现在第6章，所以我没想到他的解决方案将基于他之前没有提到的东西

如果我错过任何一点，我将不胜感激地告诉我......谢谢

Answer 1

正如评论和维基百科提及中所述，JavaScript 通过其 Array 类/原型对双端队列操作提供本机支持：push、pop、shift、unshift。然而，这并不能提供最佳的时间效率，数据集越大，时间效率就变得越重要。

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

或者，您可以选择圆形阵列。由于在 JavaScript 标准数组中不能保证是连续数组（例如在 C 中的情况），因此您实际上不需要为此使用数组实例。一个普通的对象（或地图）就可以了。

所以这里有两种可能的实现方式：

双向链表

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

。

在我的测试中，随着数据集的增长，链表解决方案成为获胜者。对于较小的数据集大小，本机数组可能是最好的。但它也取决于双端队列元素所具有的引擎和数据类型：整数的结果与对象或字符串的结果不同。因此，我建议对您的实际数据和双端队列操作进行一些基准测试，以了解哪种实现最适合您的情况。

Answer 2

简单的出队实现方式：

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]

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;
  }
}

Answer 4

与理解新事物的任何其他尝试一样，采用比较方法会有所帮助。

JS 数组是双端队列，因为你可以开箱即用地修改前面的数组。在 Python 中你不会得到这个，因为开箱即用的列表结构仅支持后面的修改（称为

append

和

pop

）。如果您需要开始添加和删除前面的项目，您需要显式添加对双端队列的支持（通过在模块顶部添加

from collections import deque

）并使用专用构造函数（

d = deque([1,2,3]

）创建对象。只有这样您才能执行

popleft

和

appendleft

操作（JS中称为

unshift

和

shift

）

再次强调，JS 中不需要这些，JS 数组的实现支持此 OOTB。要了解整个语言领域的术语，请参阅维基百科的表格：

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

如何在javascript中实现deque数据结构？

问题描述投票：0回答：4

4个回答

双向链表

圆形“数组”

最新问题

如何在javascript中实现deque数据结构？

问题描述 投票：0回答：4

4个回答

双向链表

圆形“数组”

最新问题

问题描述投票：0回答：4