JavaScript Queue Native

Question

I'm learning Algorithms and DS. How can I use queue in JavaScript?

I get that you can do something like this.

var stack = [];
stack.push(2);       // stack is now [2]
stack.push(5);       // stack is now [2, 5]
var i = stack.pop(); // stack is now [2]
alert(i);            // displays 5

var queue = [];
queue.push(2);         // queue is now [2]
queue.push(5);         // queue is now [2, 5]
var i = queue.shift(); // queue is now [5]
alert(i);              // displays 2

But wouldn't shift() would shift everything Hence, time complexity is O(N) instead of Dequeue in Java which is O(1)

Why doesn't JavaScript has the concept of Queue like Stack(array) natively?

I was just curious. Please enlighten me.

(I asked myself this question but couldn't find a valid reason why ES8 or ES9 would have queues inbuilt with Dequeue O(1) and enqueue O(1) without having to implement one myself)

PS: Sorry for asking silly question but this has been itching my brain!

Just as you mentioned, Array is designed as a very flexible object that you can mimic array, stack and queue operations by calling different methods. I don't think its time complexity is O(N) for such operation. — tibetty, Aug 16 '17 at 03:18
Any shift or unshift () operation will re-create the array. Hence it will be O(N) if i'm not mistaken. — TechnoCorner, Aug 16 '17 at 03:20
How do you know JS implementations haven't optimised `.shift()` to *not* rebuild the whole array? — nnnnnn, Aug 16 '17 at 03:23
`https://stackoverflow.com/questions/22614237/javascript-runtime-complexity-of-array-functions` Shift is O(1) Only in special cases — TechnoCorner, Aug 16 '17 at 03:26
It's at worst, sir. Almost all algorithms the has worst case. — tibetty, Aug 16 '17 at 03:29
There's nowhere indicated that shift is O(1) as well =)) please enlighten me if you do find — TechnoCorner, Aug 16 '17 at 03:33
@tibetty in my life the worst case seems to happen with alarming frequency :-) — djna, Jun 15 '21 at 08:34

score 3 · Accepted Answer · answered Aug 29 '17 at 21:18

You could implement it from scratch in vanilla JS. As to why it's not native, probably because that efficiency gain is hardly ever necessary and arrays/objects are flexible enough to use.

function Queue() {
    this._oldestIndex = 1;
    this._newestIndex = 1;
    this._storage = {};
}

Queue.prototype.size = function() {
    return this._newestIndex - this._oldestIndex;
};

Queue.prototype.enqueue = function(data) {
    this._storage[this._newestIndex] = data;
    this._newestIndex++;
};

Queue.prototype.dequeue = function() {
    var oldestIndex = this._oldestIndex,
        newestIndex = this._newestIndex,
        deletedData;

    if (oldestIndex !== newestIndex) {
        deletedData = this._storage[oldestIndex];
        delete this._storage[oldestIndex];
        this._oldestIndex++;

        return deletedData;
    }
};

I have a question. I'm the OP, got an idea. Why can't we `SWAP(arr[0], arr[len-1])` and then do a `pop()` and then do the swap again so that the original order is preserved? — TechnoCorner, Dec 29 '19 at 06:09

JavaScript Queue Native

1 Answers1