Creating Queues for In-Order Executions With JavaScript by using WeakMap()

A queue is a programming construct that bears a heavy resemblance to real-world queues, for example, a queue at the movie theater, ATMs, or the bank. Queues, as opposed to stacks, are first-in-first-out (FIFO), so whatever goes in first comes out first as well. This is especially helpful when you would like to maintain data in the same sequence in which it flows.

Types of queues

Before you understand queues, take a quick look at the types of queues that you may want to use in your applications:

  • Simple queue: In a simple FIFO queue, the¬†order¬†is retained and¬†the data¬†leaves in the same order in which it comes in
  • Priority queue:¬†A¬†queue¬†in which the elements are given a predefined priority
  • Circular queue:¬†Similar to a simple queue, except that the back of the¬†queue¬†is followed by the front of the queue
  • Double ended queue(Dequeue): Similar to the simple¬†queue¬†but can add or remove elements from either the front or the back of the queue

Implementing APIs

Implementing an API is never as easy as it seems. When making generic classes, you can never predict what kind of situation your queue is going to be used in. Some of the most common operations that you can add to the queue are as follows:

  • add(): Pushes an¬†item¬†to the back of the queue
  • remove(): Removes an¬†item¬†from the start of the queue
  • peek(): Shows the last¬†item¬†added¬†to¬†the queue
  • front(): Returns the¬†item¬†at the front of the queue
  • clear(): Empties¬†the¬†queue
  • size(): Gets¬†the¬†current size of the queue

Creating a queue

Of the four types of queues discussed earlier, this article will teach you to implement a simple and priority queue.

A simple queue

To create a queue, use the following steps:

  1. Define a constructor():

  1. Use WeakMap()for in-memory data storage:

  1. Implement the methods described previously in the API:

You need to wrap the entire class inside an IIFE because you don’t want to make Queue¬†items accessible from the outside:

Testing a simple queue

To test this queue, you can simply instantiate it and add/remove some items to/from the queue:

As you can see in above code, all the elements are treated the same. Irrespective of the data they contain, elements are always treated in a FIFO fashion. Although that is a good approach, sometimes you may need something more: the ability to prioritize elements that are coming in and leaving the queue.

Priority Queue

A priority queue is operationally similar to a simple queue, that is, they support the same API, but there is a small addition to the data they hold. Along with the element (your data), they can also persist a priority, which is just a numerical value indicating the priority of your element in the queue.

Addition or removal of these elements from the queue is based on priority. You can either have a minimum priority queue¬†or a maximum priority queue, to help establish whether you are adding elements based on increasing priority or decreasing priority. Now let’s see how we can use the add() method in the simple queue:

Since you are accounting for the priority of the elements while they are being inserted into the stack, you do not have to concern yourself with priority while you remove elements from the queue. So, the remove() method is the same for both simple and priority queues. Other utility methods, such as front(), clear(), peek(), and size(), have no correlation with the type of data that is being saved in the queue, so they remain unchanged as well.

A smart move while creating a priority queue would be to optimize your code and decide whether you would like to determine the priority at the time of addition or removal. That way, you are not over calculating or analyzing your dataset at each step.

Testing a priority queue

First set up the data for testing the queue:

Visually, the preceding steps would generate a queue that looks as follows:

Note how when you add an element with a priority 2 it gets placed ahead of all the elements with priority 1:

And when you add an element with priority 1 (lowest), it gets added to the end of the queue:

In the above image, by adding the last element apply the lowest priority in the order, which makes it the last element of the queue, thus keeping all the elements ordered based on priority.

Now, remove the elements from the queue:

There you have it: the creation of simple and priority queue in JavaScript using WeakMap().

If you found this article interesting, you can explore Kashyap Mukkamala’s Hands-On Data Structures and Algorithms with JavaScript to increase your productivity by implementing complex data structures and algorithms. This book will help you gain the skills and expertise necessary to create and employ various data structures in a way that is demanded by your project or use case.

Leave a Reply