Simple Queue Implementation in JavaScript

programming web dev
1

Filing under the bucket of “Why not!”, here is a Queue implementation (with some optimizations from @senocular from the Stacks thread):

class Queue {
    constructor(...items) {
        this.items = items;
    }
    clear() {
        this.items.length = 0;
    }
    clone() {
        return new Queue(...this.items);
    }
    contains(item) {
        return this.items.includes(item);
    }
    peek() {
        var item = null;

        if (this.items.length > 0) {
            item = this.items[0];
        }
        
        return item;
    }
    dequeue() {
        var removedItem = this.items.shift();
        return removedItem;
    }
    enqueue(item) {
        this.items.push(item);
        return item;
    }
}

The usage for it is really simple:

var line = new Queue("Bono", "Edge", "Larry");
line.enqueue("Adam");
line.dequeue() // Bono

The only thing I definitely don’t like about this naive implementation is that removing an item from the front of an array is a performance issue. Or is it? There is a theoretically faster version below that is actually slower in practice, so don’t use it! My guess is the various JS engines optimize Array behavior (see here) :slight_smile:

Cheers,
Kirupa

2

Typo. This should be

new Queue("Bono", "Edge", "Larry");

:wink:

3

Just for kicks, I created a version that doesn’t use shift:

class Queue {
    constructor(...items) {
        this.items = items;
        this.start = 0;
    }
    clear() {
        this.items.length = 0;
    }
    clone() {
        var newItems = this.items.slice(this.start);

        return new Queue(...newItems);
    }
    contains(item) {
        return this.items.includes(item);
    }
    peek() {
        var item = null;

        if (this.items.length > this.start) {
            item = this.items[this.start];
        }
        
        return item;
    }
    dequeue() {
        var removedItem = this.items[this.start];
        this.start++;

        return removedItem;
    }
    enqueue(item) {
        this.items.push(item);
        return item;
    }
}

Usage of this should be the same as the earlier. In my cursory testing, As I mention below, it is slower than the shift approach for some bizarre reason.

Cheers,
Kirupa

4

The biggest problem with this version is that cloning will wipe any null/undefined entries in the queue.

var q = new Queue(null)
q.contains(null) //-> true
q.clone().contains(null) //-> false

You’re also growing the items array indefinitely as you add new items, even when removing old ones. This would be less of a problem if you deleted instead of set to null, because then you’d at least have a sparse array not physically using every slot up to its length. But eventually (though unlikely) you’ll also hit a start which will break the queue. That value would be… let me see here… 9007199254740992 I think? No, wait, it would really by the max range of length which is 4294967295. After that, you’re adding into indices length no longer reports for which can mess up your peek().

You’ll have to publish your tests along with your code next time :slight_smile:. Has there been much on kirupa.com about testing code?

5

Publishing tests is a good idea. I haven’t written about that at all, so that’s something to look into. I did create a perf test a few seconds ago: https://jsperf.com/queuekirupa

The “faster” queue implementation is actually slower. In the test, the length of the items is a fixed amount. Only the dequeue runs. It may be that JS engines optimize shift already as seen here: https://bugs.chromium.org/p/v8/issues/detail?id=3059, so any extra code I write will be slower than the C++ implementation under the covers.

Regarding your feedback about null getting obliterated in this approach, that’s true! Let me tweak the code a bit and also use this.start instead of filtering to get the new array during cloning.

EDIT: No more filtering via null!

6

Heh. I noticed that. I did a double take to make sure I was reading that right.

1 Like
7

My only explanation after fiddling with this is that the browsers optimize Arrays heavily. I still don’t have a better explanation :stuck_out_tongue: