DEV Community: Alain D'Ettorre

Queues in JavaScript

Alain D'Ettorre — Thu, 01 May 2025 15:36:50 +0000

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

[NYCR 2024] New Year's Coding Resolutions 2024

Alain D'Ettorre — Sat, 30 Dec 2023 13:05:29 +0000

Maybe I'll read this in a few months and laugh. But here I am, sharing a wishlist of small and big things I'd like to do in 2024 regarding code

Develop one or more non-trivial application using Go https://go.dev/
Practice cloud computing more from a developer perspective
Delve into the microservices architecture
Build something with Lit https://lit.dev/
Apply design patterns and clean code more

I tried to keep the list short. Who knows how far from this next year's gonna be! Feel free to share yours, bye.

Offline Video Player is here

Alain D'Ettorre — Sun, 07 Feb 2021 10:44:56 +0000

[EDIT] Support for subtitles added

Offline Video Player is a new Express MVC application allowing you to watch a lot of videos in a row, without distractions. It also keeps track of your progress automatically and let's you export/import it.

It works completely offline as the name implies though, so you have to put video files into the app's /videos folder in order to make it work.

How to use

Install

git clone https://github.com/alaindet/offline-video-player.git
cd offline-video-player
npm install

Move your .mp4 video files into the /videos folder
Start

npm start

Cover photo by Darren Bockman on Unsplash

How to test all HTTP status codes (and have tea)

Alain D'Ettorre — Tue, 08 Dec 2020 10:22:18 +0000

httpstat.us is the perfect website for trying and learning any HTTP status and its meaning.

You want to test a 500 Internal Server Error HTTP response in your fancy frontend app but your local development server simply doesn't want to fail (lucky you!)? Just make a request to https://httpstat.us/500

You want a teapot? Just make a request to https://httpstat.us/418

Photo by Seb Cumberbirch on Unsplash

Please, manage your z-index

Alain D'Ettorre — Thu, 16 Jul 2020 08:52:11 +0000

If you've ever worked on a medium to big project I'm sure you know how painful it is to work with z-index CSS rules. What number should I use to put this component on top of another, like 1, 5, 10, 999 or even 9999?

The solution is creating variables with meaningful names for z-index values, put them in the same place and refer to them wherever you need them. Here's an example in pure CSS, but you can use the same concept in any styling tool you're currently using

:root {
  --z-index-toolbar: 1;
  --z-index-sidebar-backdrop: 2;
  --z-index-sidebar: 3;
  --z-index-modal-backdrop: 4;
  --z-index-modal: 5;
}

.toolbar {
  z-index: var(--z-index-toolbar);
}

.sidebar-backdrop {
  z-index: var(--z-sidebar-backdrop);
}

.sidebar {
  z-index: var(--z-sidebar);
}

.modal-backdrop {
  z-index: var(--z-modal-backdrop);
}

.modal {
  z-index: var(--z-modal);
}

What really matters about z-index is its relative value and not the absolute one, so it makes sense to have all indices stored in the same place as variables and quickly compare and edit them.

Photo by Héctor J. Rivas on Unsplash

Immutability and you: Part 3

Alain D'Ettorre — Thu, 09 Jul 2020 15:27:00 +0000

In this article we're going to see how you can change an object immutably

Add new properties

const programmer = {
  sleeplessHours: 5347,
};

const hacker = {
  ...programmer,
  nickname: 'h4ck3r_l1f3',
};

/*
hacker = {
  sleeplessHours: 5347,
  nickname: 'h4ck3r_l1f3',
};
*/

Overwrite existing properties

const twoYearsOldKid = {
  name: 'Come up with a name yourself',
  someOtherProp: 42,
  age: 2,
};

const threeYearsOldKid = {
  ...twoYearsOldKid,
  age: 3,
};

/*
threeYearsOldKid = {
  name: 'Come up with a name yourself',
  someOtherProp: 42,
  age: 3,
};
*/

Remove a property

const userData = {
  username: 'john.doe',
  someSecretData: 'I like cats',
  comments: 1234,
  averageRating: 4.3,
};

const { someSecretData, ...filteredUserData } = userData;

/*
filteredUserData = {
  username: 'john.doe',
  comments: 1234,
  averageRating: 4.3,
};
*/

Putting it all together

Let's say we have this recipe object

const recipe = {
  ingredients: [
    'bread',
    'meat',
    'salad',
    'fries',
    'gravy',
  ],
  price: 5.90,
  steps: [
    'Cook the meat',
    'Fry the fries',
    'Slice the bread',
    'Slice the salad',
    'Assemble',
  ],
};

And we want to add a new ingredient and a new step at the same time. Here's how to do it

const betterRecipe = {
  ...recipe,
  ingredients: [
    ...recipe.ingredients,
    'secret sauce',
  ],
  steps: [
    ...recipe.steps.slice(0, recipe.steps.length - 1),
    'Add the secret sauce',
    ...recipe.steps.slice(recipe.steps.length - 1),
  ],
};

/*
betterRecipe = {
  ingredients: [
    'bread',
    'meat',
    'salad',
    'fries',
    'gravy',
    'secret sauce',
  ],
  price: 5.90,
  steps: [
    'Cook the meat',
    'Fry the fries',
    'Slice the bread',
    'Slice the salad',
    'Add the secret sauce',
    'Assemble',
  ],
};
*/

Notice that the new ingredient was added as the last item of the ingredients property, but the new step was added as the second-last item of the steps property (before "Assemble", the last one). This is done by "splitting" the array in two parts (the last step on the right and all the others on the left) and inserting the new step right inside the split.

If you liked this series please leave some feedback. See you next time!

Photo by Salmen Bejaoui on Unsplash

Immutability and you: Part 2

Alain D'Ettorre — Thu, 09 Jul 2020 15:24:33 +0000

In this article we're going to see how you can change an array immutably

Add new values at the end (push)

const boringSuperpowers = [
  'X-ray vision',
  'Invisibility',
  'Super strength',
];

const yourSuperpowers = [
  ...boringSuperpowers,
  'Programming in JavaScript',
  'Using immutability',
];

/*
yourSuperpowers = [
  'X-ray vision',
  'Invisibility',
  'Super strength',
  'Programming in JavaScript',
  'Using immutability',
]
*/

Add new values at the beginning (unshift)

const starWarsBefore2000 = [
  'A New Hope',
  'The Empire Striked Back',
  'Return of the Jedi',
];

const starWarsAfter2000 = [
  'The Phantom Menace',
  'Attack of the Clones',
  'Revenge of the Sith',
  ...starWarsBefore2000,
];

/*
starWarsAfter2000 = [
  'The Phantom Menace',
  'Attack of the Clones',
  'Revenge of the Sith',
  'A New Hope',
  'The Empire Striked Back',
  'Return of the Jedi',
]
*/

Remove the last item (pop)

const week = [
  'Monday',
  'Tuesday',
  'Wednesday',
  'Thursday',
  'Friday',
];

const weekIdLike = week.slice(0, week.length - 1);

/*
weekIdLike = [
  'Monday',
  'Tuesday',
  'Wednesday',
  'Thursday',
]
*/

Remove the first item (shift)

const countdown = [3, 2, 1];

const almostMidnight = countdown.slice(1);

/*
almostMidnight = [2, 1]
*/

Replace an item inside an array

const starters = [
  'Bulbasaur',
  'Squirtle',
  'Charmander',
];

const sorrySquirtle = [
  ...starters.slice(0, 1),
  'Rattata',
  ...starters.slice(2),
];

/*
sorrySquirtle = ['Bulbasaur', 'Rattata', 'Charmander']
*/

Remove an item inside an array

Note: You can remove any portion of the array with this technique, not just a single item

const pickACard = [
  'Queen of Hearts',
  'Ace of Spades',
  '2 of Pikes',
];

const remainingCards = [
  ...pickACard.slice(0, 1),
  ...pickACard.slice(2),
];

/*
remainingCards = [
  'Queen of Hearts',
  '2 of Pikes',
]
*/

Sort and/or reverse an array

const people = [
  'Bob',
  'Alice',
  'Charlie',
];

const sorted = [...people].sort();

const reverseSorted = [...sorted].reverse();

/*
sorted = [
  'Alice',
  'Bob',
  'Charlie',
];

reverseSorted = [
  'Charlie',
  'Bob',
  'Alice',
];
*/

Photo by Pietro Rampazzo on Unsplash

Immutability and you: Part 1

Alain D'Ettorre — Thu, 09 Jul 2020 15:21:38 +0000

The problem

Consider something like this

const a = [1,2,3];
const b = a;
a.push(4);
console.log(b); // [1,2,3,4]

Can you see the problem? You've created an array a, then you copied (you think you copied) it into b, so you legitimately think a and b are now separate. Then you mutate array a by pushing a new value into it and then b changes as well. Why is that?!

Something like this happened:

A new array [1,2,3] is created inside a place in your RAM memory called the heap
You give this array a reference known as a, like an address, so that you can later fetch the array value from memory
You create a new reference b by assigning it a, so now you have two references that point to the same position in memory (red flag!)
The push method just mutates the array value without changing its address, so when you output b you see the unexpected. OMG. And it's just 4 lines of code.

The same problem, but with an object

const question = { content: 'What is 6x9?' };
const answer = question;
answer.content = '42.';
console.log(question); // { content: '42.' }

When you change the content of the answer by mutating it, you change the question too (it's getting deep in here) since question and answer refer to the same value in memory.

The solution

So, how to solve the problem? Immutability!

If you think about primitives in JavaScript, like strings, numbers and booleans, you already know about immutability. Look at this

const a = 10;
const b = a;
// const a = a + 10; // You cannot reassign a const!

As you can see, there's no way to actually mutate the number a and that's because primitives in JavaScript are immutable by default. Compound values, on the other hand, like arrays and objects, are mutable. For example, you can add values to arrays with push or even re-assign object properties (as in the example above): the values have changed, of course, but the position in memory of the whole array or object is still the same so that every variable that points to that value shares the same value.

Instead of changing just a small part of an array or object, thus mutating it, you should replace the whole thing, even if you only changed a single letter. The idea is that values should be like photographs: they're immutable, they represent some point in time and you can take as many as you want, each different even if only by a bit. If you take a bad photo of your kitten doing something funny you just take a new shot.

Updating objects and arrays "immutably" (more on that later) takes a new memory slot in the heap and the old slot just gets automatically captured and erased by a thing called garbage collector. The advantage of this is that you avoid the reference hell like in the first example, you have better testing, predictability and even time-traveling debugging.

Immutability is a key concept of Redux, which is a popular state management pattern heavily used in React and in Angular too.

The spread syntax

The spread syntax, is, really, just a bunch of dots! It's the main operator you need to finally achieve immutability. What they do is expanding what immediately follows them, creating a copy of it. Let's rewrite the first example

const a = [1,2,3];
// const b = a; // <-- We changed this
const b = [...a]; // <-- Into this
a.push(4);
console.log(b); // [1,2,3]

What actually happened? Basically, [...a] means "create a new array and replace ...a with all the items inside a", so you're effectively creating a real copy of a which takes a new place in memory, not just a reference to it. That's why b is now completely unaffected by whatever you do to a.

In part 2 and 3 we'll take a look at how to update arrays and objects with the spread syntax in practice

Photo by Andrea Ferrario on Unsplash

Meet Sass Pal.

Alain D'Ettorre — Thu, 25 Jun 2020 14:33:11 +0000

So, SASS has variables, mixins, functions, parent selectors, nesting. Cool. That gives developers more power, not more structure.

You could npm install bootstrap and import just its sass files into your frontend project. Now you have pre-made components, some variables, utilities. You later realize you don't need all those unused components, so you start to comment out some @import statements. Then you want to change the color palette and override variables. Then you want buttons to look different and add CSS to override the framework's CSS. You may reach a point where you use only Bootstrap's utilities.

You swear you're not gonna use frameworks again and instead switch to a utilities-only library, Tailwind, which is a fully composable way of avoiding to write any CSS and instead stuff your templates with hundreds of utility classes. It has its strengths though: it's good to have everything on the table and just pick up what you want, but it can be tiresome to set up a huge regex via PostCSS and purge everything when you're finished. Try to do that with Angular and let me know (EDIT: this has improved in the last year).

Meet Sass Pal, a Sass library that attempts to solve most of these problems. The main concepts include

Not a single line of CSS is output unless you need it
Sensible defaults for colors, media breakpoints and units
Helps to centralize shared values into a store
Completely overridable and extensible
No pollution of global namespace: only one $_PAL_STORE variable exists and all mixins and functions start with pal-
Gradual migration: you can use as little as needed or go full Sass Pal without colliding with any existing styling code
A suite of unit tests and a comprehensive documentation with examples

The cool part is that is has a lot of features like builders, request maps, device queries, a store and reducers (high five to Redux enthusiasts out there), but you can still ignore everything and just use a tiny fraction of it, since all disappears once compiled to CSS. Let's peak into the docs. So this

.hello-world {
  @include pal((

    'any': (
      space: my2 'p^b4',
      border: (x: 2 #ccc, y: 1 #ddd),
      position: absolute (2 4),
      size: (
        w-3/4,
        h-8u,
        wmin-1/2%,
      ),
    ),

    'tablet+': (
      space: my0 py5 px8,
      border: (x: 3 #ccc, y: 3 #ddd),
    ),

    'desktop+:hover': (
      space: my2
    )

  ));
}

compiles to this

.hello-world {
  margin-top: 1rem;
  margin-bottom: 1rem;
  padding-top: 2rem;
  padding-right: 2rem;
  padding-left: 2rem;
  border-right: 1rem solid #ccc;
  border-left: 1rem solid #ccc;
  border-top: 0.5rem solid #ddd;
  border-bottom: 0.5rem solid #ddd;
  position: absolute;
  top: 1rem;
  bottom: 1rem;
  left: 2rem;
  right: 2rem;
  width: 75%;
  height: 4rem;
  min-width: 50%;
}

@media screen and (min-width: 768px) {
  .hello-world {
    margin-top: 0;
    margin-bottom: 0;
    padding-top: 2.5rem;
    padding-bottom: 2.5rem;
    padding-right: 4rem;
    padding-left: 4rem;
    border-right: 1.5rem solid #ccc;
    border-left: 1.5rem solid #ccc;
    border-top: 1.5rem solid #ddd;
    border-bottom: 1.5rem solid #ddd;
  }
}

@media screen and (min-width: 1024px) {
  .hello-world:hover {
    margin-top: 1rem;
    margin-bottom: 1rem;
  }
}

For me, the best part is not that you write less code, but that you can separate the actual styling (inside the components) from the state management of your styling values (inside your store). Like, what does 'desktop+:hover' mean in the example? Basically, whatever you want it to mean. By default, anyway, it means these rules only apply to desktops or bigger devices, only while hovering, where a desktop is just a name you give to a resolution range you can override. What does side: (w-3/4, h-8u) mean again? It means I want this component to have a width of 75% of its container and an height equal to 8 times the base unit and the base unit is 0.5rem by default or any other number if you override it.

To learn more, visit
https://github.com/alaindet/sass-pal
https://alaindet.github.io/sass-pal/

Photos courtesy of
https://unsplash.com/photos/qV2eVjm7cnw
https://unsplash.com/photos/-LxNvgW1psM