Queues in JavaScript

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

You buy new groceries and bring home yogurts you like to eat for breakfast. Now you have to store what you bought into the fridge, but there's already some yogurt 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, rotting on the back of your fridge. No, you have to put the old ones aside or, God forbid, take them out of the fridge, push the new ones to the back and then put the old ones in front to avoid letting the old ones expire. 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 to emptying the hole fridge and reorder all your yogurts each time you want to eat one (it's actually the opposite, but it takes the same time). And maybe there's 100 hundreds of them. 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 fetch the oldest one.

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 many elements (from the previous benchmark)


• Short queues, i. e. almost syncrhonized enqueue/dequeue calls so that queues act as buffers and are quite small

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

Dequeue

Short queues

Conclusions

• The glaring result is that dequeueing from a single array 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 a double array


• The double array implementation offers the best balance between enqueueing and dequeueing


• 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! Just beware of big queues or maybe stick with a solution based on double arrays, just in case.

Cover photo by Hal Gatewood on Unsplash