How to Implement a Queue in JavaScript

at dmitripavlutin.com

1 up and 0 down, posted by panzerdp 1378 days ago 6 comments

tracker1 1378 days ago. link 1 point ▲ ▼

I'm not sure why one would do this over simply using an array...  Delete in particular is a somewhat costly execution penalty.

    class Queue {
      constructor() {
        this._items = [];
      }
    
      enqueue(item) {
        this._items.push(item);
      }
    
      dequeue() {
        return this._items.shift();
      }

      peek() {
        return this._items[0];
      }

      get length() {
        return this._items.length;
      }
    }

Replies

panzerdp 1378 days ago. link 1 point ▲ ▼

this._items.shift() cannot be used because it's O(n) time complexity.

tracker1 1376 days ago. link 1 point ▲ ▼

Then use splice if you're really concerned about it... will be O(n) with an n of 2.

Also, have you actually measured the performance cost of Delete... as I mentioned, you're optimizing by using an expensive call.

panzerdp 1375 days ago. link 1 point ▲ ▼

"Then use splice if you're really concerned about it... will be O(n) with an n of 2."

enqueue() and dequeue() operations on a queue have to be O(1) time complexity. Using unshift(), splice() is a mistake, they are O(n).

Your proposal is to use an O(n) complexity function splice() instead of delete O(1) - but that's just a mistake.

"Also, have you actually measured the performance cost of Delete... as I mentioned, you're optimizing by using an expensive call."

delete operator is O(1) time complexity. That's all that matters.

If you are concerned about the delete operator performance (which in 99% you shouldn't be), use a Map instead of a plan JavaScript object, then use map.delete(key).

tracker1 1373 days ago. link 2 points ▲ ▼

You are correct, I apologize.  I will note, that `undefined` assignment is faster than deletion.  I wasn't able to get a good/consistent memory profile for comparison.  I was mistaken about how Array is implemented from a couple articles that I'd read, the impression was slice would only effect the starting index and the number of items in the array affected, not the entire series.

Depending on how big the queue might get, it might be worth exploring using a linked-list instead of object refs.

https://github.com/tracker1/queue-testing

panzerdp 1371 days ago. link 1 point ▲ ▼

Thanks for comparing the different implementations! Yeah, clearly the SplicingQueue is the slowest.