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 6 · Accepted Answer · answered Aug 29 '17 at 21:18

6

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;
    }
};

answered Aug 29 '17 at 21:18

DoloMike

499
6
15

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
You can't swap js has no reference concept all is a value. – Et7f3XIV Sep 20 '21 at 12:40
@Et7f3XIV That's not entirely accurate. In Javascript, all objects are passed by reference to the object location. While there is no way to read the address of the object, whenever you assign the object to a new value, you are truly only assigning the reference of the object. If this is an array of objects, then a standard swap operation could be easily used. – Frozenfrank Mar 04 '23 at 20:10
Yes you are right we can swap but not with the prototype given in the comment. We would need to add a array parameter and give index (or use indexOf but this would be brittle) – Et7f3XIV Mar 04 '23 at 23:03

JavaScript Queue Native

1 Answers1