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 plexity 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!

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 plexity 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!

• javascript
• queue

• 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 plexity is O(N) for such operation. – 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 Commented Aug 16, 2017 at 3:20
• How do you know JS implementations haven't optimised .shift() to not rebuild the whole array? – nnnnnn Commented Aug 16, 2017 at 3:23
• https://stackoverflow./questions/22614237/javascript-runtime-plexity-of-array-functions Shift is O(1) Only in special cases – TechnoCorner Commented Aug 16, 2017 at 3:26
• 1 @djna yup, that's called Murphy's Law, :-) – tibetty Commented Jun 17, 2021 at 9:46

1 Answer 1

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