I'm Learning data structure with javascript
and my focus now on how to implement deque?
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 ?
I get understand some points like I need :
but I'm confused about some points :
how many pointers I need ? at least I know from queue I need two(head-tail) pointer but not sure if I need more in deque
which data type in javascript convenient in this case as a base? I saw some tutors in youtube talking about circular array for example which unknown for me in JS.
edite2:
I was following a book called: learning javascript data structures and algorithms 3rd edition
in chapter5 of this book the author started to implement Deque based on object only and some variables
but I didn't understand how he did that because the code encrypted but I can still reach to his files from and test his approach github repository
I can say that @trincot answer very close of book author approach
but when I compare the results I get this [1 = author - 2 = @trincot] :
according to the book index taking about linked list comes in chapter6 so I didn't expect his solution will be based on something he didn't mentioned before
plz if I miss any point I will be grateful to tell me it ... thanks
Although Wikipedia mentions that JavaScript has native support for deque operations via its Array class/prototype (push
, pop
, shift
, unshift
), this does not give the optimal time efficiency, which becomes important the larger your dataset is. If we regard the optimal time efficiency a requirement for a deque implementation, then JavaScript does not have a native implementation.
If you need good performance for larger datasets, you will want to write your own implementation. You can go for a doubly linked list, where you just need two "pointers". It should be said that in JavaScript we don't really speak of pointers, but of objects. Variables or properties that get an object as value, are in fact references in JavaScript.
Alternatively, you can go for a circular array. Since in JavaScript standard Arrays are not guaranteed to be consecutive arrays as for example is the case in C, you don't really need to use an Array instance for that. A plain object (or Map) will do.
So here are two possible implementations:
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
Methods will return undefined
, when an attempt is made to retrieve a value from an empty deque.
In my tests the linked list solution came out as the winner as the data set grows. For small datasets sizes, the native array may turn out to be best. But it also depends on the engine and the data type that the deque elements have: the results for integers are different from the results for objects or strings. So I would advise to do some benchmarking on your actual data and deque manipulations to see which implementation will be best for your case.