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
– tibetty, Commented Aug 16, 2017 at 3:18
Any shift or unshift () operation will re-create the array. Hence it will be O(N) if i'm not mistaken. — TechnoCorner
– TechnoCorner, Commented Aug 16, 2017 at 3:20
How do you know JS implementations haven't optimised .shift() to not rebuild the whole array? — nnnnnn
– nnnnnn, Commented Aug 16, 2017 at 3:23
https://stackoverflow.com/questions/22614237/javascript-runtime-complexity-of-array-functions Shift is O(1) Only in special cases — TechnoCorner
– TechnoCorner, Commented Aug 16, 2017 at 3:26

DoloMike · Accepted Answer · 2017-08-29 21:18:05Z

7

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, 2017 at 21:18

DoloMike

5296 silver badges15 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

TechnoCorner Over a year ago

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?

Et7f3XIV Over a year ago

You can't swap js has no reference concept all is a value.

Frozenfrank Over a year ago

@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.

Et7f3XIV Over a year ago

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)

Collectives™ on Stack Overflow

JavaScript Queue Native

1 Answer 1

4 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

4 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related