Data structures are all about runtime complexity, so before reading this article, I suggest you read my previous blog on time runtime complexity and Big O notation, link.
What is Data Structures?
When it comes to answering this question, there are two big points we need to consider:
- Data structures are a way for organizing information by using an optimal “runtime complexity” which involve adding, editing or removing records.
- JavaScript offer natively several implementations of data structures. However, we still need to understand the “low level” one to be able to succeed in an interview.
Difference between an Array and a Queue
In the below image, I’m comparing what an array in JS is capable to do with what a queue can do.
We can say that the blue square is the capability of the JS array, and the small white square is the capability of the Queue. We can easily say that a JS array can definitely do whatever a queue can do plus a lot of more functionality. However, in an interview is really easy to be asked to implement a queue from scratch by considering all its limitation.
If you think about this concept, it doesn't make much sense. You may be wondering “I already have an array that can do whatever a queue can do, and you suppose to create a one our an array???”. Well, let see how we can give some sense to this interview question by building one and explain why a queue can be helpful in some situations.
What is a Queue?
A queue is like a container where data enter from one side and exit from the other side.
A better way to think of a queue is pretended like data are people waiting to access into the theatre and to do that they need to first enter into a queue and exit from the other side. Each person entering into the queue need to wait his turn to exit. In a queue, there is no concept of cutting or skipping the line, the order you enter into the queue also determine the order in which you exit.
When you add something to a queue is referred to as Enqueuing or adding, and we referred to the exit process as Dequeuing or removing.
The queue follows a concept called FIFO or “First In First Out”.
Let say we have Data A and Data B that need to access a queue, at the moment our queue is empty we start by adding A.
Now A is added tot he queue and we have 1 element inside, we need know to add Data B.
Now both elements are Enqueued, and the order appears as you can see in the picture we have first A and then B. Now we need to Dequeue the elements.
A is the first element to exit as per FIFO concept First element to enter is the first element to exit. As you can see B now will be the last element to exit.
As you can see, a Queue is a rudimental implementation of an array. In JS to Enqueue or Dequeue element form an array, we use some pre-build method.
Add to a queue or Enqueue:
array.unshift()Remove or Dequeue:
array.pop()Queue implementation
Now that we know what a queue is and which method in JS can replicate the same behaviour, the rest is pretty straight forward. We are going to create a Class and initialize it with an empty array which is going to be our queue. In a classic Array we have different methods exposed to it such as shift, unshift, push, pop, splice and slice, but in this case, the only two methods that we are going to make accessible are unshift to add to the queue, and pop to remove.
So why would we need to limit an array by building a limited version of it?. First, this can be asked in an interview question, and you should be able to recreate a queue. Second, imagine you are working on a real project, and you come out with an algorithm that uses a queue to and by doing this algorithm much performs much better. However, you want to avoid that some other engineering comes and start to mess up your algorithm by treating the algorithm like a classing array and drop the performance of your hard work. This can be a good way to limit access to some of the functionality of a classic array.
The code
The first step is to create a class and initialize this class with an empty array
Now we need to add some methods to our class to interact with it by adding and removing records/data like in a queue, here is where we going use our unshift and pop JS methods from the array.
As you can see the implementation is not too difficult. The first method is the function inside our class is “add” which takes an argument and add at the beginning of the array the data we passed to it.
The second method is the “remove”, and same we call our array using “pop” method to remove the last element in the array.
Now we have our queue implemented in a few line of code and ready to be used, I hope you enjoyed my article and see you next week with a new blog ;)
