If you simply implement it with .push()
to .enqueue()
and .shift()
to .dequeue()
that's easy but the the time complexity of .enqueue()
is O(1) and .dequeue()
is O(n).
While still using arrays, I have come come up with a nice solution to make both .enqueue()
and .dequeue()
in O(1). I am using sparse arrays. It turns out to be super efficient but only when the Queue
size is larger than 25000. My benchmarks are like this;
Queue size 100
Queue: 0.12999999523162842
Array: 0.03999999910593033
Queue size 1000
Queue: 1.1049999967217445
Array: 0.5250000059604645
Queue size 10000
Queue: 3.0750000029802322
Array: 1.7799999937415123
Queue size 100000
Queue: 13.944999992847443
Array: 887.390000000596
OK Queue
becomes much faster than Array
as the size grows but i can not tell what to improve so that Queue
doesn't fall behind Array
at smaller scales. Is there anything that you can suggest in the below code?
class Queue extends Array {
constructor(){
super();
Object.defineProperty(this,"head",{ value : 0
, writable: true
});
}
enqueue(x) {
this.push(x);
return this;
}
dequeue() {
var first;
return this.head < this.length ? ( first = this[this.head]
, delete this[this.head++]
, first
)
: void 0;
}
peek() {
return this[this.head];
}
}
var p = Array(100000).fill().map(_ => ~~(Math.random()*1000)),
q = p.reduce((r,e) => r.enqueue(e), new Queue());
var s,e;
s = performance.now();
for (i=0; i < 100000; i++){
q.dequeue();
}
e = performance.now();
console.log("Queue:", e-s);
s = performance.now();
for (i=0; i < 100000; i++){
p.shift();
}
e = performance.now();
console.log("Array:", e-s);
Edit:
After some research, now i understand that what many of us have been told is in fact not correct. .shift()
is not O(n). It's been optimized to O(1) many years ago and i think last ones to optimize were the Firefox guys in 2017. Here the guys are discussing how to implement the optimization and it turns they do a very similar thing to what i implemented here. Unlike me, they just skip the "delete
out the dequeued item" part since they write it in C++ and can move the pointer (head
in above code) by leaving out freed spaces to GC. But in JS we have to delete
them either in each .dequeue()
operation or wait for (this.length - this.head) > 50000
and make a .splice(0,this.head)
in order to prevent memory leak. This is inline with what i see with Chrome and new Edge (Chromium). Up until 50000 items .shift()
works O(1) but then they switch to non optimized code. In Firefox this seems to be not the case as mentioned in a developer's comment.
Verdict:
You may safely and simply implement efficient Queue
s with .push()
and .shift()
.