Creating a well performing stack within JavaScript is super simple and you can pretty much get away by using the built in JavaScript array. However, the same is not true for creating a well performing queue within JavaScript. And in this lesson, we will look at the reason why and follow that up by creating your own high performance queue. So let's go. First, let's take a quick look at the built-in methods within JavaScript arrays that can be used for creating your own stacks and queues. Now to add items to an array one by one, the best method that we have available is the push method. Each call to push adds a new item at the end

of the JavaScript array. Now, if you want to remove the last item that we added, this will essentially give us a stack that is the last in first out, and we can do that with the JavaScript pop method. Now, JavaScript arrays have another method called Shift, which removes the first item within the array and shifts all the other elements one index down. However, because it has to update the index of all the other elements that will still be within the array, it is not exactly highly performant. Let's look at a quick demo to demonstrate this performance issue. Here we have a piece of code that creates a JavaScript array

and then simulates creating a bunch of JavaScript items and adding them to the array using the push method, and then removes these items in a last in first out order using the pop method. All of this code is wrapped in consult time, so we get a time notification of how much time this particular simulation is going to take. Now we can repeat the process in a first, in first out order, which is required by a queue using the JavaScript shift method. Now the performance difference over here is highly dependent on the number of iterations that we do, and over here we're doing a hundred thousand.

And you can see that the performance difference between pop versus shift is quite significant. It's five millisecond versus 389. Now, even though the performance difference in this particular case is quite aggressive for most real world applications, you probably wouldn't care. However, if you are working in a performance intensive application or are creating a library for someone who cares about performance, then this is a difference that you definitely should be aware of PAC and create our own Q data structure, which performs much better. First, we will lay down the structure of

what we want our Q data structure to be. It'll be a generic class, just like the built-in JavaScript array. It'll have an inq method which can add items in OF one. It'll have a DQ method which will remove items in the first, in first out order in OF one. And that's pretty much it. Now, if we didn't know any better, we would probably start off by creating a JavaScript array for the INQ method. We will push it at the end of the array and for the DQ method, we will remove it from the start of the array using the JavaScript shift method. But as we do know better, we know that shift is not exactly O fun.

So let's get rid of this naive implementation. Now, one observation that you can make over here is the fact that you need some form of O one data structure for your DQ operation. And whenever you have to think of O one, you should probably start thinking about hash maps. And the cheapest hash map that you can create within JavaScript is just using a JavaScript object. And that's exactly what we are going to do. Over here. We create this JavaScript object that we are going to index with a given number and the items within the object are going to be of the type T that we want to store within the queue. Now, the reason why we are using a number index

for this particular object is that we are going to track the items that have been queued and D queued from this particular object using two simple number variables. Now, before we jump into more code, let's look at a visualization to explain the strategy that we will have for these three variables. Think of the items that we are going to add as indexes represented by a line within this TETA object. We start off With both next inq index as well as next DQ index initialized to the value zero. As we add new item, we will increment the next INQ index

so that we can add more items to more portions of this line. And as we remove items, we will increment the next DQ index and essentially delete those items by deleting the index in the data object, which is represented by this line and start returning undefined. If the next DQ index ever catches up to the next inq index. As this means we have run out of items to dq. Now with that visualization out of the way, you can see that the code for the inq method is going to be pretty simple. We are going to store the item at the next inq index and then increment the next queue index

for the next inq operation. The DQ method is going to be a bit more involved, but nothing more complicated beyond basic programming. The first thing that we are going to do is to make sure that next DQ index has not caught up to the next inq index. If it has, then outside of the F block, the function is automatically going to return undefined. Otherwise, we grab The item that we plan to DQ using the next DQ index, Delete this item from the data to free up the memory, And then increment the next DQ index so it gets closer and closer to the next inq index.

And finally, return the item that we have successfully D queued. Now that's it for the vital required methods for the queue data structure, and we can add a lot more methods. For example, we can add a method called size that returns the number of items that are currently within the queue. And all that we have to do for this particular case is to simply return the difference of the next in queue index versus the next DQ index. Now let's jump back to a performance test to verify that all of this work is not a complete waste. We add a new test for the queue data structure. We queue items using inq, and then we dq them using dq.

And if we run this, you can see that the pop and the queue are quite similar in performance and shift is much, much slower. Now, even though for most particular applications, this implementation is going to be sufficient, there is one minor modification that we can still make. JavaScript has this value known as max safe integer, which is the maximum integer that can be safely represented within JavaScript anywhere greater than that might be clipped. For example, max Safe integer plus one and Max Safe integer plus two are both clipped to the same integer value and

therefore it is not safe to use values greater than max safe integer. Now this can be problematic as we are using a number index and we are implementing it arbitrarily, but take an easy fix in modern JavaScript. Instead of using the number type, we can use a big INT and index by the string representation of that big int. So we modify our data to use the string index, change our next inq index, as well as the next DQ index to big ins by adding the N suffix. And then whenever we want to index the data object,

we make sure to convert the next inq index as well as the next DQ index to the string representations. Now because theoretically this data structure can hold more than number, amount of items, we have to modify the return type of the size method to be big int. As always, you can find the code for this particular lesson on GitHub, and this is just one of the many ways that you can create your own queue data structure within JavaScript. And in fact, we looked at another method when we created our own W Link list. The objective of this particular lesson was to get you

to create your own queue in the simplest way possible.