When it comes to the FIFO (First In, First Out) data structure commonly referred as a queue, JavaScript doesn't provide any built-in implementation. If you quickly seach online, people will mostly tell you that a simple array and its .push / .shift methods are fine to mimic a queue. And they're right. But are they? Let's check.

The yogurts analogy

But first, an analogy. You buy yogurts. Now you have to put them into the fridge, but there's already some yogurts from last week, expiring in two days. It's so tempting to just shovel the freshly bought yogurts in front of the old ones, it's a simple operation with an O(1) time complexity, it's like doing fridge.yogurts.push(...newYogurts) in real life. But then you'll waste the old ones, letting them expire on the back of your fridge.

No, no, you have to do the right thing, put the old ones aside or, God forbid, take them out of the fridge maybe, push the new ones to the back and then put the old ones in front. What an effort! Has it ever happened to you? Was it mildly annoying, or ultimately frustrating?

Well, when implementing a queue data structure with a JavaScript array, using Array.prototype.shift to dequeue an element from the queue is the equivalent of emptying the whole fridge and reordering all your yogurts each time you want to eat one (not exactly, but the same effort). Imagine there's a hundred thousand yogurts now. In computer science terms, Array.prototype.shift has a linear time complexity of O(n), meaning the more yogurts you buy, the more time it takes to do this.

Benchmarks

To prove this, I've gathered and benchmarked three implementations of a queue in JavaScript

  • Using a single array and Array.prototype.push / Array.prototype.shift
  • Using double arrays and only O(1) operations like Array.prototype.push and Array.prototype.pop
  • Using a custom implementation of a linked list

The three benchmarks consisted in

  • Enqueueing many elements
  • Dequeueing that many elements (from the previous benchmark)
  • Short queues, i. e. almost synchronized enqueue/dequeue calls so that queues are just small buffers

Code is available here
https://github.com/alaindet/js-park/tree/main/js/benchmarks/queue

Results

  • 200'000 iterations were performed for each benchmark
  • Average machine (Ryzen 5, 16 Gb RAM)

Enqueue

name timing comparison
DoubleArrayQueue 6.7516 ms 1x
SingleArrayQueue 10.3246 ms 1.53x
LinkedListQueue 27.6806 ms 4.10x

Dequeue

name timing comparison
LinkedListQueue 3.8519 ms 1x
DoubleArrayQueue 9.9158 ms 2.57x
SingleArrayQueue 4971.7428 ms 1290.72x

Short queues

name timing comparison
DoubleArrayQueue 10.4831 ms 1.00x
SingleArrayQueue 10.7441 ms 1.02x
LinkedListQueue 41.6060 ms 3.97x

Conclusions

  • The glaring result is that dequeueing from a single array via Array.prototype.shift is painfully slow for the reasons explained above: dequeueing 200'000 elements took ~1300 times more than a linked list and still ~500 times more than double arrays
  • The double arrays implementation offers the best balance between enqueueing and dequeueing
  • Enqueueing on a linked list has a slight overhead since you're creating an instance of the node class
  • For short queues, i. e. almost synchronous enqueue/dequeue cycles, the linked list is a little overkill, but every implementation is comparable

What to use then? Honesly, maybe sticking with .push/.shift was not so bad if you're dealing with small queues! Just beware of big queues or maybe stick with a solution based on double arrays, just in case. The linked list implementation probably uses less memory than the double arrays, but this should be further examined.

If I had to pick, the double arrays is both an ingenious and classic solution and a solid implementation.

Cover photo by Hal Gatewood on Unsplash