Welcome back.
Now, in the previous video, we have seen that we can implement a queue by using push and shift and
with an array.
So let's try to see that over here.
Now let's take the console and let's say I have a queue and we can just say it's an array.
All right.
So it's going to be just uh const queue is equal to an empty array.
All right.
Now let's try to push something to it.
So we have queue dot push.
Let's say we push the value one to it.
And now we're going to push the value two to it.
And then let's push the value three to it.
All right.
Now our cue is having three elements.
So let's take a look at it.
So this is the array 123.
And we know that the order is that first one came in.
Then two came in and then three came in.
Now we know that queue is a Fifo or first in first out data structure.
So we should get one back first right.
So for this we are going to use shift.
So we can say queue dot shift.
And you can see we get back one which came in first.
Right.
So if we again shift, we get back two.
And if we again shift we get back three.
So this is how a queue works right?
So any time we stand in a queue to get a ticket, the person who came first is getting the ticket first
and hence he or she comes out first.
So this is how a queue works.
Now again, the problem is that the shift operation over here on an array is going to be an O of n operation
for with respect to time complexity.
So that's not efficient right.
So let's go ahead and implement our queue using a linked list.
And this is going to be efficient.
And we'll be able to add elements into our queue and take out the elements from the queue in constant
time and space.
So let's go ahead and implement our queue with the linked list.
Now again we will need our uh node class.
So we can say class node.
And then we have our constructor over here.
And we pass in the value when we call this.
And we're going to say this dot value is equal to the value which is passed to it, and this dot next.
Is equal to null.
Now let's go ahead and write the Q class.
So this is class Q.
And we have a constructor over here as well.
And we don't pass anything to it.
And then over here we're going to say this dot first is null.
And this dot last is null.
And the size at this moment is equal to zero, so it's empty when we create an object with this class.
All right.
Now inside this we are going to add two instance methods to add and to take out elements from the queue.
Now in the case of a queue addition is called in queuing.
So we can say in queue.
So this is going to be the function to add a value.
So we have to pass the value to it.
So I'm just having placeholders now and then to remove a value we call it DQ.
In the case of a queue we have DQ over here.
All right.
So this should give back the element which was added first.
Now in the case of a queue we are going to add at the end and remove from the beginning so that we can
implement the queue as a Fifo data structure.
First in first out.
So let's go ahead and write these two instance methods.
First let's write the in queue instance method.
So we have a value passed to it.
Now with this value we are going to create a node using the node class which we have written over here.
So we can say const node is equal to new node.
And then we pass the value to it.
So we have a node made with this value.
Now we are going to check is the singly linked list at this point empty.
So if not this dot first.
That means if it is null, if first is null and which means that the singly linked list is empty.
In this case we are just going to say this dot first is the node which we just now created.
And this node last is also going to be equal to the node itself.
Now if this is not the case then we are going to say this dot last dot next.
That is the previous last is going to point to the new node which we created because we are adding at
the end.
All right.
And then we have to modify the last.
So this dot last is going to be equal to node.
So we are setting the new node as the last node in this singly linked list.
Now because we have added a new node we have to increment the size.
So we can say this dot size plus plus.
And then let's say we just want to return the complete singly linked list.
So that would be returned this.
So this is how we can add a node at the end in the singly linked list.
And you can see that this is pretty much similar to what we have done in the linked list video, where
we designed our linked list.
All right.
Now let's go ahead and write the dequeue function also over here.
And then we'll go ahead and test our code.
Now if we dequeue we are going to remove from the beginning so that the Fifo property is followed.
Right.
We want to get out what was inserted first.
Now when we call the dequeue function or the dequeue method, first we are going to check if the singly
linked list is empty at this point.
So if not this dot first, if there is nothing then we will just return null.
All right.
So we cannot dequeue anything.
Now if this is not the case let's have a variable temp.
And this is going to be equal to this dot first.
And we are just storing this because we are going to remove the first element.
And finally we will return back temp.
So we are removing temp the first element.
And we will return back the element which we just now removed.
All right.
So temp is equal to this dot first.
Now let's go ahead and shift the first over here the first property to the next node.
So we can say this dot first is equal to this dot first dot next.
All right.
So the next element the second element is made the first.
And again we are tracking first and last over here.
So this dot first is equal to this dot first dot next.
So the second node now is made the first node.
And in this way we have removed the first node.
Now because we have removed one node we are going to decrement the size.
So we can say this dot size minus minus.
And that's it.
All right.
Now again, there is one more condition that we have to check over here.
Let's say the singly linked list only had one node.
So in this case we have modified the first two null.
But we have not yet modified the last also.
Right.
So if it has only one node then we have to modify last also to null.
So let's check that over here.
So after decrementing the size let's check if the size is equal to zero.
So if this dot size is equal to zero.
That means that the singly linked list now is empty.
So we can say this dot last is equal to null.
And that's it.
All right.
So over here we are returning the node which we have just now removed.
So this is how we have implemented our queue using a singly linked list.
Now let's go ahead and test our code.
So let's just have an object over here.
So I can say const queue is equal to new queue.
All right.
Again so that you don't get confused.
Let me just call this Q1.
So this is our object, and this is the name of the class that we have written over here, which is
this one over here.
All right.
Now let's go ahead and enqueue a few elements.
And again we are adding at the end.
All right.
So let's call the enqueue function or method.
So we have dot enqueue.
And then let's just pass in a values one.
And after this let's enqueue two.
So we'll make a node with value two and add it at the end.
Again let's enqueue another element or node with value three.
So let's go ahead and run our function.
All right.
So let's take a look at our Q.
And you can see that it has three nodes.
And we are always adding at the end.
So you can see the first one.
First node is value one, which was added first and then we have two.
And then we have three which points to null.
So this is how it looks like.
Now let's go ahead and dequeue from the queue.
So if we say queue dot dequeue.
Let's just check.
Okay.
It's not Q, it's Q one.
All right.
So that's why we have this error.
So it's q one dot d q.
And over here you can see we are getting one, which is the element which was inserted first.
So if we again dequeue we will get back two.
If we again dequeue will get back three.
If you dequeue again we get back null because there is nothing inside the queue.
So this is how we implement a queue with the linked list.
Now let's take a look at the code over here.
For this.
Let me grab a pen.
All right.
Now what's happening when we enqueue a value let's take a look.
So first over here we are making a new node.
Let's say the value is one.
So we make a node with the value one.
Then we are checking if the singly linked list is empty.
Let's say at this point it's empty.
So we have our node over here.
And we will say first and last is this node itself.
All right.
Now let's say we again enqueue a node with value two.
So we come over here we create a node with value two.
We check if the singly linked list is empty.
No it's not empty.
We have this node over here.
So we come to the else part.
And then we say this dot last which is this node over here dot next.
So this is going to point to the node which we created.
And then we are going to say this dot last is equal to the node.
So we're going to make this last.
This is known no longer last.
Now we are incrementing the size.
Now let's say we are again adding one more value and let's say the value is three.
So again we come over here we create this node.
And then we see it's not empty.
We come over here and then we say this dot last dot next is equal to node.
So this is going to point to the node which is three which we created.
And again we increment the size.
So this is how we are enqueuing elements.
So again notice that we are adding at the end.
Now let's take a look at dequeuing elements.
So let's just clean this up a little bit.
Now when we call the DQ method, we come over here.
And we are checking if the singly linked list is empty.
No, it's not empty at this point.
Now we are going to store this dot first in temp.
So this dot first is this node.
This is going to be equal to temp.
And then we are setting this dot first is equal to this dot first dot next.
So this dot first dot next is this node over here.
Now this is going to be set as first.
So in this way we have removed this node.
And then we are just returning this temp over here which is node one.
All right.
And again over here we are checking if the size became zero.
No it's not at zero.
All right.
Now let's say we again dequeue.
Now at this point this is first all right.
And this is last.
Again this is last.
When we added this this would have been made last.
All right.
So again we come over here we are checking whether it's empty.
No it's not empty.
Then we come over here and we say temp is equal to this dot first.
So this is going to be equal to temp.
And then we are saying this dot first is equal to this dot first dot next which is this node over here.
So this is made first.
And in that manner we have removed this node and we are returning temp over here.
Again the size is not equal to zero right.
So let's dequeue once more so that we get this condition.
True.
All right.
So let's just clean this up a little bit.
So currently it looks like this.
There is just one node in the queue.
And first and last is the same node itself.
All right.
Now again we are dequeuing.
We come over here, we check.
Is it empty?
No, it's not empty.
So we are going to store this dot first in temp.
So this is going to be temp.
And then we are going to say this dot first is equal to this dot first dot next.
Now this over here will be pointing to null.
So we are shifting first ahead.
So first is made null right.
So first is made null.
Now we come over here we decrement the size.
So the size becomes equal to zero because earlier it was one.
Right.
Now when we check this condition this dot size is equal to zero.
Therefore we are going to say this dot last is equal to null.
So last also is shifted from here to null.
All right.
So that's how we are implementing the dequeue instance method.
And then we're just returning temp over here.
All right.
And then again we have seen that we are adding at the end.
And we are removing from the beginning.
And we know that both of these operations, in the case of a singly linked list, is a constant time
and space operation.
So we have implemented our queue with the linked list over here, and then we are able to add elements
and remove elements from the queue in constant time and space.