Welcome back.
Now first let's take a look at how to implement a stack using an array.
So over here we have our console.
Now let's say I have an array.
So I can just say const.
R is equal to new array.
Now we are going to use Push and Pop to implement the LFO data structure stack, as we have seen in
the previous video.
So let's just push something into this array.
So I have r dot push and let's push in the value one.
And then we push in the value two.
And let's then push in the value three.
Now, if you take a look at the array, we have one, two and three over here.
Now we know that one was pushed in first, then second, then two, then three.
But now we're going to pop from it.
And first we are going to get three, which was inserted at the end, right.
Which was the last to go in.
So last in first out.
So this is how the stack is implemented.
So stack is a data structure.
Now if I again pop I'll get two.
If I pop again I'll get one.
And then if I pop it's going to be undefined because nothing is there in the array.
So this is how we can use an array to implement a stack.
All right.
And we have seen that push and pop is constant time in the case of an array.
Now let's go ahead and see how we can build our own stack using a linked list.
Now this is going to be very much similar to how we implemented the singly linked list.
So we are going to have a node class.
And inside this we have our constructor.
And we pass the value to it.
And then over here we are going to say this dot value is equal to the value which is passed over here.
And then we'll say this dot next is equal to null.
All right.
Now again let's go ahead and write the stack class.
And inside this we're going to have our constructor.
And over here we'll just say this dot first is equal to null.
And this dot last.
Is equal to null and this dot size.
Is equal to zero.
Now, in the case of a linked list, we used head and tail.
But over here, because we are saying stack is a data structure.
Last in first out.
That's why we have the terminology last and first over here.
Now inside the class the stack class, we will write instance methods to add and remove values from
the stack.
So these are the two important functions or properties methods that we need for the stack.
And we will be adding at the beginning.
So let me just write that over here.
Add at the beginning and we will also remove from the beginning.
So this will ensure that the element which was added the in in the as the last element will be removed
first because we are removing from the beginning.
All right.
And again, the reason why we are doing this is that we want constant time removal from from the beginning.
So we could add at the end and remove from the end.
But removing from the end in the case of a singly linked list is going to be an O of n operation.
So removing from the beginning is an O of one operation, and adding at the beginning is an O of one
operation.
So that's why we are doing it in this manner.
Now let's go ahead and write these two instance methods.
So let's call one method add at beginning.
And we have to pass in the value over here.
And the second method that we have to write over here is remove from the beginning.
All right.
Now let's go ahead and first write this method, which is the add at the beginning.
And we have to pass a value.
So what we do inside this instance method is we're going to create a node using our node class over
here.
So we can say const node is equal to new node.
And then we are passing the value over here.
So we have created a node with this value.
And then now let's just check if the singly linked list at this point is empty.
So we can check if not this dot first.
That is, it's just empty.
In that case, we are going to say this dot first is equal to the node which we just now created.
And this dot last is also going to be equal to the node which we created.
Now if this is not the case, that is if there are already nodes inside the singly linked list, then
let's have a temporary variable.
So we can say let temp is equal to this dot first.
And then we will just say this dot first is equal to the node which we just now created.
So this dot first is going to be equal to the node.
And then we will say node dot next is equal to temp.
Or we can just say this dot first dot next right.
So this dot first is now node.
And this dot first dot next is going to be the temp which is what we have stored over here.
Now we could do it in either way you can say no dot next.
So you can say this dot first dot next is equal to temp.
Now once we are out of this because we have added a node and we are tracking the size of the singly
linked list, let's just increment this so we can say this dot size plus plus.
And that's it.
Now let's say after adding the node we want to return the complete singly linked list.
So we can say return this.
All right.
So this should work.
So we have returned the instance method to add at the beginning.
Now let's go ahead and write the instance method to remove from the beginning.
And then we will check or test our code.
So let's go ahead and do this now.
So over here, what we will do is once we are inside the function, once this is called, let's just
check if the singly linked list is null or empty.
So if not this dot first, then we have nothing to remove and we'll just return null.
Now, if this is not the case, let's have a temp variable.
And let's say we want to return the node that we are removing.
So we have a temp variable over here.
And this is going to be equal to this dot first.
And then finally we will just return the temp variable because we are removing this particular node.
Right.
So we are storing the node to temp.
Now once we have done this we just need to shift the first this dot first of this particular singly
linked list to the next node.
So we can say this dot first is equal to this dot first dot next.
So the next node is made the first or the head of the singly linked list.
And then we will just decrement the size.
So this dot size minus minus.
And if we remove the node which was the only node in the singly linked list.
In that case we have to set the last.
Also because we have two properties over here first and last.
So in that case we have to set the last also to null.
So let's just check that over here.
So if this dot size.
Is equal to zero.
Then we will say this dot last is equal to null and that's it.
So we have completed both the instance methods, the method to add at the beginning and the method to
remove from the beginning.
Now you will notice that this is pretty much similar to what we did when we designed our singly linked
list.
Now let's go ahead and test our code.
Now let's have an object with this stack class.
So let's say over here we can say const stack.
Let's just call it stack itself.
Is equal to new stack.
All right.
Now we can call these functions and let's just add some values to it.
So I'm going to add let's just do it in the console itself so we can see it.
So let's clear the console.
And we have run our code.
Now we can say stack dot add at beginning.
And let's say we want to add the value one.
All right.
And again let's add another node with value two at the beginning.
And let's add one more node with the value three at the beginning.
Now let's take a look at how the stack looks like.
So over here you can see the stack has.
As the first node, the node which we entered at the last right, which is three, and then three is
pointing to two, and that is pointing to one, which is pointing to null.
So this is how it looks now.
Now let's go ahead and remove from the beginning.
All right.
So let's call the instance method which we have written.
So remove from the beginning.
And now when we do this, you will see that we are getting the node with value three, which is the
node that was inserted last.
Right.
So it's last in first out.
So we're getting this first out.
Now if you are again calling the remove from if you again call the remove from beginning function,
we get two.
If you do it again we get one.
And if we do it again we get null because there is nothing in the stack.
So yes, our code is working.
Now let's just walk through it and see what's happening over here.
And again, you will notice that this is pretty much similar to what we did in the case of a singly
linked list.
So let's just grab a pen.
And you will see that when we call the add at beginning method and we pass in a value over here, we
are creating a node with that value.
For example we want to insert one.
So let's say the value is one.
And let's say the singly linked list now is empty.
So we are making a node over here with the value one.
And this is going to point to null.
All right.
So that's used using the constructor which is there in our class node.
And then over here we will see that this dot first is actually null because let's say the singly linked
list is null at this point.
So we are going to have we are going to take this node and we will make it the first and last.
So first is also going to be this node.
And last is also going to be this node.
Let's say we are again inserting another value.
And at this time let it be the value two.
So what happens is we make a node with value two.
Then we come over here we see that first is not null.
So there is something in the singly linked list.
So we come over here.
Then we say that temp is going to be equal to this dot.
First is going to be this node over here.
So this is write that.
So temp.
Is this node.
Then we come over here and we are going to say this dot first is equal to node, which is the node that
we created.
So we are making this node the first node.
And then we are saying this dot first dot next that is this is going to point to temp.
So this will point to one.
And this is already pointing to null.
So in this way we have added at the beginning.
All right.
And among these two this is the latest inserted right.
So this is last in.
All right.
And we call this first.
And this is last at this moment.
All right.
In our singly linked list.
Now we are going to take this out.
When we take out we're going to remove from the beginning.
So we're going to take this out which is first out.
So last in first out.
And that's why this is a leaf data structure.
And again a stack is a leaf data structure.
So let's see this code also.
Now over here we have the code to remove from the beginning.
So let me just clear this up.
So let's say we call this.
Now we come over here we see that first is not null.
Then we come over here.
And then we're going to say temp is equal to this dot first.
So this over here is going to be temp.
And then we say this dot first is equal to this dot first dot next.
Now this dot first dot next is this node over here.
So this is going to be made first.
So in that way we have removed this node right from the singly linked list.
And then we are reducing the size.
And we are returning this over here which is the temp.
So we will get back to.
So you can see we are removing from the beginning.
So the node which was added latest is going to be returned first.
So this is how we have implemented a stack with a linked list.
And you can see that adding at the beginning and removing from the beginning both is constant space
and time.
So the time and space complexity of this is O of one.