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:
- Define a constructor():
|
1 2 3 4 5 6 7 8 9 |
class Queue { constructor() { } } |
- Use WeakMap()for in-memory data storage:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
const qKey = {}; const items = new WeakMap(); class Queue { constructor() { } } |
- Implement the methods described previously in the API:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
var Queue = (() => { const qKey = {}; const items = new WeakMap(); class Queue { constructor() { items.set(qKey, []); } add(element) { let queue = items.get(qKey); queue.push(element); } remove() { let queue = items.get(qKey); return queue.shift(); } peek() { let queue = items.get(qKey); return queue[queue.length - 1]; } front() { let queue = items.get(qKey); return queue[0]; } clear() { items.set(qKey, []); } size() { return items.get(qKey).length; } } return Queue; })(); |
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:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
var simpleQueue = new Queue(); simpleQueue.add(10); simpleQueue.add(20); console.log(simpleQueue.items); // prints undefined console.log(simpleQueue.size()); // prints 2 console.log(simpleQueue.remove()); // prints 10 console.log(simpleQueue.size()); // prints 1 simpleQueue.clear(); console.log(simpleQueue.size()); // prints 0 |
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:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
add(newEl) { let queue = items.get(pqkey); let newElPosition = queue.length; if(!queue.length) { queue.push(newEl); return; } for (let [i,v] of queue.entries()) { if(newEl.priority > v.priority) { newElPosition = i; break; } } queue.splice(newElPosition, 0, newEl); } |
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:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 |
var priorityQueue = new PriorityQueue(); priorityQueue.add({ el : 1, priority: 1}); // state of Queue // [1] // ^ priorityQueue.add({ el : 2, priority: 2}); // state of Queue // [2, 1] // ^ priorityQueue.add({ el : 3, priority: 3}); // state of Queue // [3, 2, 1] // ^ priorityQueue.add({ el : 4, priority: 3}); // state of Queue // [3, 4, 2, 1] // ^ priorityQueue.add({ el : 5, priority: 2}); // state of Queue // [3, 4, 2, 5, 1] // ^ |
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:
|
1 2 3 4 5 6 7 8 9 |
priorityQueue.add({ el : 6, priority: 1}); // state of Queue // [3, 4, 2, 5, 1, 6] // ^ |
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:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 |
console.log(priorityQueue.remove()); // prints { el: 3, priority: 3} // state of Queue // [4, 2, 5, 1, 6] console.log(priorityQueue.remove()); // prints { el: 4, priority: 3 } // state of Queue // [2, 5, 1, 6] console.log(priorityQueue.remove()); // prints { el: 2, priority: 2 } // state of Queue // [5, 1, 6] priorityQueue.print(); // prints { el: 5, priority: 2 } { el: 1, priority: 1 } { el: 6, priority: 1 } |
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