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 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 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

May 1, 2025 - 17:03

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

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 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