Hi everyone.
In this question we are going to design a queue.
Now let's read it.
Implement a queue first using an array and in the second part with the queue class using a linked list.
Now we can implement a queue in multiple ways.
In this question, we are going to see how we can implement or design a queue first using an array and
then using a linked list.
One should be able to add to the queue and remove from the queue following the Fifo property which is
first in first out.
Now a queue is a Fifo data structure, as we have seen previously, and Fifo stands for first in, first
out.
So that is what we also see in real life, right?
You may be standing in a queue for buying a ticket.
So the first person who came into the queue is the first one who comes out of the queue.
Now in JavaScript there is no inbuilt queue data structure.
So that's why in the ideal case, we will be implementing a queue with the linked list to get the optimum
performance.
Let's see why that is the case in the future part in this video.
Now let's first try to understand how we can implement a queue with a simple array.
Now let's say we have an array.
So we can say const r is equal to new array.
So this is our array.
Now we need to be able to add to the array and remove from the array following the Fifo property first
in first out.
Now for this we are going to use the push and shift methods of the array.
These are inbuilt methods.
Now again remember shift is the method used to remove from the beginning of an array.
Now let's look at an example.
So let's say this is our empty array.
And let's push in a few values into the array.
So we push in one over here.
And we are going to push in two and three as well.
So first one was pushed in then two and then three.
All right.
Now again remember pushing adds to the end of the array.
Now when we are going to shift we will be taking the first element out again.
Shifting is removing from the beginning.
So we will get back this one over here.
And that's what entered the array first.
So that's why this follows the Fifo property.
Now push over here in the case of an array is a constant time operation.
So that's efficient.
But shifting from an array which is removing from the beginning is a o of n operation.
The time complexity is O of n.
That's because we have to reindex the remaining elements in the array.
So this is not efficient.
So that's why let's see how we can implement a queue with a linked list.
Now we can either use a singly linked list or a doubly linked list.
In this video we are going to use a singly linked list.
Now you can implement it with a doubly linked list also if you want.
And it's just going to be minor changes from what we are going to see over here.
Now let's continue.
Now we are going to have a node class and a queue class.
Now we will use the node class to create our nodes.
Now this is a this is just like what you've seen in the case of a singly linked list.
So every value that we are going to insert into the queue will be made a node and added as a node.
All right.
Now in the case of a queue adding an element is called n queue.
So that's just the nomenclature.
And removing from a queue is called d queuing.
All right.
So we will be using these words.
So enqueue and dequeue.
And over here we have our queue class.
And then we have our constructor.
And we are tracking first and last.
And both are initialized to null.
When we first create an object for this class.
And the size is equal to zero.
Now we need to implement this as a Fifo data structure.
First in first out.
For this, we will be adding at the end of the queue or of the linked list.
All right.
So this is again a linked list and removing from the beginning of the linked list.
So this is how we are going to implement our queue using a linked list and adding at the end in a linked
list and removing from the beginning in a linked list in a singly linked list is a constant time operation.
So that's why implementing our queue with a linked list is efficient compared to using an array.
All right.
Now let's go ahead and see how we are going to implement this.
Now again first we are going to have a node.
Let's say this is our first node.
So this is inserted into our queue or our singly linked list.
And then we add the second node at the end.
So let's say two is the second node.
So this is going to be added at the end.
Now let's add one more element to this singly linked list.
Again it's added at the end.
Now when we are removing from the beginning we will get back this node over here.
And you can see that by removing from the beginning we are getting back what was first added in.
So that's why adding at the end and removing from the beginning in the case of a linked list gives us
a queue data structure because it follows the Fifo property.
All right.
And again it's it's it's operating both both of these are constant time operations.
So we are getting an efficient queue.
Now let's go ahead and see how we will be implementing this in code.
Now this is going to be pretty much similar to how we wrote our instance methods for the singly linked
list design question.
So let's say this is our singly linked list.
Now we need to add at the end.
So let's say a value is given.
So we make a node out of that with that particular value.
So this node.
Over here will be pointing to null and the value of this node will be passed to it.
And then we will take the previous last node, and we will make it point to the new node which we just
now created.
And then we will reassign last from here to here.
Previously this was the last node.
And that is going to be reassigned to the node that we have now created.
So this is how we will add at the end in the singly linked list.
And to remove from the beginning all we need to do is first.
Previously is over here.
This is going to be shifted to the next node.
So that is how we will remove from the beginning.
And the node which is removed will just be returned.
So this is how we will implement our queue with the linked list.
Now again remember adding at the end in the case of a singly linked list is a constant time operation
and constant space operation and removing from the beginning also with respect to complexity is constant
time and constant space.