如何在javascript中实现双端队列数据结构?
How to implement deque data structure in javascript?
我正在学习 javascript
的数据结构
我现在的重点是如何实现双端队列?
Edite: from comments below I get useful directions on how to implement deque based array
. Is there a direction how to implement deque based object
using class ?
我明白了一些我需要的点:
- addFront()
- removeFront()
- peekFront()
- addBack()
- removeBack()
- peekBack()
但我对某些点感到困惑:
我需要多少指点?
至少我从 queue 知道我需要两个(头尾)指针但不确定我是否需要更多 deque
javascript 中的哪种数据类型在这种情况下方便作为基础?例如,我在 youtube 上看到一些导师在谈论循环数组,这对我来说在 JS 中是未知的。
edite2:
我在关注一本书叫:学习javascript数据结构与算法第3版
作者在本书的第5章开始实现基于对象和一些变量的双端队列
但我不明白他是怎么做到的,因为代码已加密,但我仍然可以访问他的文件并测试他的方法 github repository
我可以说@trincot 的回答非常接近本书作者的方法
但是当我比较结果时,我得到这个 [1 = author - 2 = @trincot] :
根据书本索引链表出现在第6章所以我没想到他的解决方案将基于他之前没有提到的东西
如果我遗漏了任何一点,我将不胜感激告诉我...谢谢
如评论中所述,JavaScript 通过其数组 class/prototype 原生支持双端队列操作:push、pop、shift、unshift。
如果你还想自己写实现,那么你可以选择双向链表,只需要两个"pointers"。应该说,在JavaScript中我们真正讲的不是指针,而是对象。获取对象作为值的变量或属性,实际上是 references in JavaScript.
或者,您可以选择圆形阵列。由于在 JavaScript 中标准数组不能保证是连续数组,例如 C 中的情况,因此您实际上不需要为此使用 Array 实例。普通对象(或地图)即可。
所以这里有两种可能的实现方式:
双向链表
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
循环"Array"
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
当尝试从空双端队列中检索值时,方法将 return undefined
。
简单的出队实现:
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]
与理解新事物的任何其他尝试一样,采用比较方法。
会很有帮助
JS数组是deques因为可以修改前面out-of-the-box。你不会在 Python 中得到这个,其中 out-of-the-box 列表结构只支持在后面修改(称之为 append
和 pop
)。如果您需要开始添加和删除前面的项目,您需要显式添加对双端队列的支持(通过在模块顶部添加 from collections import deque
)并使用专用构造函数(d = deque([1,2,3]
)创建对象。仅然后你可以执行 popleft
和 appendleft
操作(在 JS 中称为 unshift
和 shift
)
再说一遍,none在JS中是必须的,JS数组的实现支持这个OOTB。要了解整个语言领域的术语,请参阅维基百科的 table
我正在学习 javascript
的数据结构我现在的重点是如何实现双端队列?
Edite: from comments below I get useful directions on how to implement
deque based array
. Is there a direction how to implementdeque based object
using class ?
我明白了一些我需要的点:
- addFront()
- removeFront()
- peekFront()
- addBack()
- removeBack()
- peekBack()
但我对某些点感到困惑:
我需要多少指点? 至少我从 queue 知道我需要两个(头尾)指针但不确定我是否需要更多 deque
javascript 中的哪种数据类型在这种情况下方便作为基础?例如,我在 youtube 上看到一些导师在谈论循环数组,这对我来说在 JS 中是未知的。
edite2:
我在关注一本书叫:学习javascript数据结构与算法第3版
作者在本书的第5章开始实现基于对象和一些变量的双端队列
但我不明白他是怎么做到的,因为代码已加密,但我仍然可以访问他的文件并测试他的方法 github repository
我可以说@trincot 的回答非常接近本书作者的方法
但是当我比较结果时,我得到这个 [1 = author - 2 = @trincot] :
根据书本索引链表出现在第6章所以我没想到他的解决方案将基于他之前没有提到的东西
如果我遗漏了任何一点,我将不胜感激告诉我...谢谢
如评论中所述,JavaScript 通过其数组 class/prototype 原生支持双端队列操作:push、pop、shift、unshift。
如果你还想自己写实现,那么你可以选择双向链表,只需要两个"pointers"。应该说,在JavaScript中我们真正讲的不是指针,而是对象。获取对象作为值的变量或属性,实际上是 references in JavaScript.
或者,您可以选择圆形阵列。由于在 JavaScript 中标准数组不能保证是连续数组,例如 C 中的情况,因此您实际上不需要为此使用 Array 实例。普通对象(或地图)即可。
所以这里有两种可能的实现方式:
双向链表
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
循环"Array"
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
当尝试从空双端队列中检索值时,方法将 return undefined
。
简单的出队实现:
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]
与理解新事物的任何其他尝试一样,采用比较方法。
会很有帮助JS数组是deques因为可以修改前面out-of-the-box。你不会在 Python 中得到这个,其中 out-of-the-box 列表结构只支持在后面修改(称之为 append
和 pop
)。如果您需要开始添加和删除前面的项目,您需要显式添加对双端队列的支持(通过在模块顶部添加 from collections import deque
)并使用专用构造函数(d = deque([1,2,3]
)创建对象。仅然后你可以执行 popleft
和 appendleft
操作(在 JS 中称为 unshift
和 shift
)
再说一遍,none在JS中是必须的,JS数组的实现支持这个OOTB。要了解整个语言领域的术语,请参阅维基百科的 table