我正在用 javascript 学习数据结构
我现在的重点是如何实现双端队列？
编辑：从下面的评论中我得到了有关如何实施的有用指示
deque based array。有没有一个具体实施的方向deque based object使用类？
我明白了我需要的一些要点：
但我对某些点感到困惑：
我需要多少指针？ 至少我知道queue我需要两个（头尾）指针，但不确定是否需要更多deque
在这种情况下，javascript 中哪种数据类型方便作为基础？我在 youtube 上看到一些导师谈论圆形数组，例如我在 JS 中不知道的。
edite2:
我正在关注一本书，名为：学习javascript数据结构与算法第三版
在本书的第五章中，作者开始实现仅基于对象和一些变量的双端队列
但我不明白他是如何做到这一点的，因为代码已加密，但我仍然可以访问他的文件并测试他的方法github 存储库 https://github.com/PacktPublishing/Learning-JavaScript-Data-Structures-and-Algorithms-Third-Edition/tree/master/LearningJavaScriptDataStructuresandAlgorithmsThirdEdition_Code/examples/chapter05
我可以说@trincot 的回答非常接近书籍作者的方法
but when I compare the results I get this [1 = author - 2 = @trincot] :
根据本书索引取约链表出现在第六章，所以我没想到他的解决方案会基于他之前没有提到的东西
如果我错过任何一点，我将不胜感激地告诉我......谢谢
正如评论和维基百科中所述mentions https://en.wikipedia.org/wiki/Double-ended_queue#Language_support--，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()); // undefinedclass 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，当尝试从空双端队列中检索值时。
在我的测试中，随着数据集的增长，链表解决方案成为获胜者。对于较小的数据集大小，本机数组可能是最好的。但它也取决于双端队列元素所具有的引擎和数据类型：整数的结果与对象或字符串的结果不同。因此，我建议对您的实际数据和双端队列操作进行一些基准测试，以了解哪种实现最适合您的情况。