Hi everyone.
In this question we're going to learn how to design a stack.
Now let's read the question.
Implement a stack using an array.
And secondly with the stack class using a linked list.
So we're going to implement a stack in these two ways.
One should be able to add to the stack and remove from the stack following the LFO property.
Remember we have discussed that a stack is a data structure where LFO stands for last in first out.
That is all which is important about a stack.
So you should be able to add things to the stack and remove from the stack following the LFO.
Um order last in first out.
Now remember, in JavaScript there is no inbuilt stack, so we can either implement a stack using an
array or a linked list.
So there are multiple ways in which we can implement a stack.
So let's get started.
First we are going to implement a stack with an array.
Now let's say we have an array and we call it a r r r.
So we can say const r is equal to new array.
So we have an array over here.
And then now we need to be able to add to this and remove from this.
And we have to follow last in first out.
So that's what a stack is about when we implement a stack with an array.
Now for adding to this array we will use push which will add to its end.
And for removing we will use pop which will remove from its end.
Now let's try to see how this works out.
So let's say the array is empty at this point.
Now we're going to use push to add a value to the array.
So let's say we push three into the array.
Now we are going to push four to it.
Now notice that pushing is adding at the end.
Now let's say we again push five also to the array.
Now you can see that three is the element that was first added in, then four and then five.
Now we are going to pop from the array.
Now if we pop from the array we will get back the element which was added last in.
So this was last in.
So this was the element which was added last.
Right.
And this is going to be first out.
So when we do R dot pop and we call the pop method we are going to get five which is the element which
was added in last.
So you can see that it is following the LFO property.
And in this manner by just using push and pop, we have implemented a stack by just using an array.
All right.
Now we know that pushing into an array is a constant time operation, and popping also from an array
is a constant time operation.
So this is how we can implement a stack with an array.
Now this is very useful.
You will see that especially in, in uh things like implementing a depth first search etc., which we
will see in the latter part of this course, we will use a stack when we do a DFS or depth, first search
in a graph, etc., in an iterative manner.
So we will see that later.
But again we have implemented a stack using an array and it's pretty straightforward and we are getting
good performance also.
Now let's go ahead and see how we can build our own stack from the from scratch using a linked list.
Now we could either use a singly linked list or a doubly linked list.
Now over here in this video we are going to use a singly linked list.
And if you want, you can go ahead and implement it with a doubly linked list also.
And there would be just minor changes.
All right.
Now let's go ahead.
Now what we will do is we will have a node class and we will have a stack class.
All right.
Now using the node class every element which is added again is going to have a value and a next property.
So this is pretty much similar to what we have seen in the linked list section.
And then we have this stack class.
We have a constructor.
And in the case of a linked list we called the first element head and the last element tail.
But over here we are just calling it first and last.
And then we are tracking the size of the linked list as well.
Now over here in this stack class we are going to have two instance methods, one to add at the beginning
and the second one to remove from the beginning.
All right.
So this is how we will implement a stack with a linked list.
Now notice over here that we are adding at the beginning and removing at the beginning.
Now this will follow the LFO property.
But even if we were adding at the end and removing from the end, it would still follow the LFO property,
but then removing from the end in the case of a singly linked list is an O of N operation.
So that is why we are not doing it in that manner.
We know that removing from the beginning is an O of one operation or a constant time operation.
In the case of a singly linked list, and adding at the beginning is also a constant time operation
in the case of a singly linked list.
Now, if we were using a doubly linked list, then it would not matter.
So we can either add and remove from the beginning, or add and remove from the end, and it would just
work in constant time.
All right.
So to recap we have this node class.
So every element which is added to the singly linked list will be a node.
And then we have the stack class.
And we are tracking the first and last element in the linked list and the size.
And then we're going to write these two instance methods to add and remove from the beginning.
And the reason why we are adding and removing from the beginning is that if we were to choose removal
and addition at the end, in that case, removing from the end is a O of n operation which is not efficient.
So to make the.
Efficient.
We are adding and removing at the beginning, especially because we are using a singly linked list.
All right.
Now let's go ahead and see how we add and remove from the beginning.
In the case of a singly linked list.
So this is something that we have just we have already discussed previously.
But let's just quickly revise it over here.
So let's say we have one node currently in the singly linked list.
Now we are going to add one more node.
Let's say we it has the value b.
And we are going to add at the beginning.
So we are going to have b over here.
And b points to A.
And then let's add one more node at the beginning.
So let's say that c.
So c is going to point to b and b points to a.
Now if you want to remove from the beginning we will get back this c over here.
And you can notice that this was the element which was added latest.
Right.
This was the last in element to the singly linked list.
So yes we can see that it is following the lifting property or last in first out.
And that is the property which has to be followed by a stack.
Now let's also see how we can implement this in code.
So let's say this is our singly linked list.
Now if we want to add at the beginning we'll just have a new node created using the node class.
And then we will make this node point to the previous head.
And then we will make this node over here the head.
In the case of a singly linked list.
And over here we are just calling the head first.
So it's just a terminology difference.
So instead of head we will just call it first over here.
So this is how we are adding at the beginning.
Now if you want to remove from the beginning all that we have to do is we will move the head to the
next node.
And then in that way we are just removing.
Right.
So to remove this we are just removing the head or the first to the next node.
All right.
So this is going to be first.
So that means the singly linked list starts from here.
And this node has been removed.
And then we can track this.
We can store this somewhere before removing and return it.
Because typically when we have a remove instance method we return the node or the value that is being
removed.
So this is how we will implement our stack with linked list.
And again remember the space and time complexity of both the add at beginning and remove at beginning
instance methods is going to be o of one.