# Simple Queue Implementation in JavaScript

**URL:** <https://forum.kirupa.com/t/simple-queue-implementation-in-javascript/637077>\
**Category:** web dev\
**Created:** [August 21, 2017, 8:21pm UTC](https://forum.kirupa.com/t/simple-queue-implementation-in-javascript/637077 "2017-08-21T20:21:57Z")\
**Posts on this page:** 7\
**Page:** 1

<div class="post-metadata">

**Author:** ![kirupa](https://yyz1.discourse-cdn.com/flex011/user_avatar/forum.kirupa.com/kirupa/32/11616_2.png) [@kirupa](https://forum.kirupa.com/u/kirupa)\
**Post date:** [August 21, 2017, 8:21pm UTC](https://forum.kirupa.com/t/simple-queue-implementation-in-javascript/637077/1 "2017-08-21T20:21:57Z")

</div>

Filing under the bucket of “Why not!”, here is a Queue implementation (with some optimizations from @senocular from the [Stacks thread](http://forum.kirupa.com/t/simple-stack-implementation-in-javascript/637069/3)):

```
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](http://forum.kirupa.com/t/simple-queue-implementation-in-javascript/637077/3?u=kirupa) that is actually slower in practice, so don’t use it! My guess is the various JS engines optimize Array behavior ([see here](https://stackoverflow.com/questions/8423493/what-is-the-performance-of-objects-arrays-in-javascript-specifically-for-googl)) 🙂

Cheers,  
Kirupa

---

<div class="post-metadata">

**Author:** ![senocular](https://yyz1.discourse-cdn.com/flex011/user_avatar/forum.kirupa.com/senocular/32/7217_2.png) [@senocular](https://forum.kirupa.com/u/senocular)\
**Post date:** [August 21, 2017, 10:33pm UTC](https://forum.kirupa.com/t/simple-queue-implementation-in-javascript/637077/2 "2017-08-21T22:33:09Z")

</div>

> [@kirupa](#):
>
> new Queue([“Bono”, “Edge”, “Larry”]);

Typo. This should be

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

```

😉

---

<div class="post-metadata">

**Author:** ![kirupa](https://yyz1.discourse-cdn.com/flex011/user_avatar/forum.kirupa.com/kirupa/32/11616_2.png) [@kirupa](https://forum.kirupa.com/u/kirupa)\
**Post date:** [August 22, 2017, 8:28pm UTC](https://forum.kirupa.com/t/simple-queue-implementation-in-javascript/637077/3 "2017-08-22T20:28:25Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![senocular](https://yyz1.discourse-cdn.com/flex011/user_avatar/forum.kirupa.com/senocular/32/7217_2.png) [@senocular](https://forum.kirupa.com/u/senocular)\
**Post date:** [August 22, 2017, 8:53pm UTC](https://forum.kirupa.com/t/simple-queue-implementation-in-javascript/637077/4 "2017-08-22T20:53:20Z")

</div>

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

```javascript
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 🙂. Has there been much on [kirupa.com](http://kirupa.com) about testing code?

---

<div class="post-metadata">

**Author:** ![kirupa](https://yyz1.discourse-cdn.com/flex011/user_avatar/forum.kirupa.com/kirupa/32/11616_2.png) [@kirupa](https://forum.kirupa.com/u/kirupa)\
**Post date:** [August 22, 2017, 9:06pm UTC](https://forum.kirupa.com/t/simple-queue-implementation-in-javascript/637077/5 "2017-08-22T21:06:34Z")

</div>

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](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](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**!

---

<div class="post-metadata">

**Author:** ![senocular](https://yyz1.discourse-cdn.com/flex011/user_avatar/forum.kirupa.com/senocular/32/7217_2.png) [@senocular](https://forum.kirupa.com/u/senocular)\
**Post date:** [August 22, 2017, 9:37pm UTC](https://forum.kirupa.com/t/simple-queue-implementation-in-javascript/637077/6 "2017-08-22T21:37:19Z")

</div>

> [@kirupa](#):
>
> The “faster” queue implementation is actually slower.

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

---

<div class="post-metadata">

**Author:** ![kirupa](https://yyz1.discourse-cdn.com/flex011/user_avatar/forum.kirupa.com/kirupa/32/11616_2.png) [@kirupa](https://forum.kirupa.com/u/kirupa)\
**Post date:** [August 22, 2017, 11:36pm UTC](https://forum.kirupa.com/t/simple-queue-implementation-in-javascript/637077/7 "2017-08-22T23:36:54Z")

</div>

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