Welcome back.
Let's now go ahead and code the solution, which we discussed in the previous video to implement a queue
with stacks.
Right.
So for this we will write our class and let's call it My Queue.
And over here we have the constructor.
We don't pass anything to it and we're just going to initialize two empty stacks.
So let's call one stack in stack.
And the second stack can be called out.
Stack.
So these are just empty over here.
And we are implementing a stack as an array over here.
Now let's go ahead and write the instance methods.
So we need an instance method to push a value to the queue.
And then we need a method to pop from the queue.
And then we need the peek function.
And finally the empty function.
So these are the four functions mentioned in the question.
So let's get started with the push function over here.
So we just need to push something to our queue.
So we are going to push the value which is given to us to the in stack.
All right.
So that's just a constant time operation.
So we can say in this dot in stack dot push and we are passing the value.
So that's it.
So this value over here will be inserted to the in stack.
So that's about pushing a value to the queue.
Now let's go ahead and write the pop function over here.
Now over here.
First we have to check if the out stack is empty.
If the out stack is empty, as we discussed in the previous video, we have to take the elements from
the in stack one at a time by popping from it.
And then we will insert it to our out stack, and then we will pop from the end of the out stack.
So this is to ensure the Fifo property because this is a queue.
So let's go ahead and test this.
So check first whether the out stack is empty.
So if not this dot out stack dot length.
So we know that zero is falsy in JavaScript.
So if the length over here is equal to zero, then that's falsy.
And then we have a nought over here.
So that means if the length is zero this will become truthy.
And we will come inside this if condition.
And then we will just pop from the stack and push to the outer stack.
So let's go ahead.
For this we will use a while loop.
So while this dot in stack.
Dot length.
That means as long as the length is not equal to zero.
Now we're just going to say this dot out stack dot push.
And the value that we want to push to the out stack is the value that we are going to pop from the in
stack.
So over here we can have this dot in stack dot pop.
All right.
So we are popping from the in stack and taking a value.
And that value is pushed to the outside.
So that's what is happening over here.
Now once we are out of this we just need to return the value that we get when we pop from the out stack.
So we can say return this dot out, stack dot pop.
All right.
So that that will give us the, uh, element which was inserted first.
So again, we are doing this so that we maintain the Fifo property and we are implementing it in this
manner so that we get an amortized constant time operation when we pop from the queue.
All right.
Now let's go ahead and write the remaining two functions.
And then we will test the code that we have written and walk through the code to understand it in a
better manner.
So let's proceed.
Now peak.
In the case of the peak function, we don't want to pop from the queue, but we just want to see what
is the element which is there in the queue which was inserted first.
Right.
So again it's going to be pretty much similar to pop.
So let's just copy this over here and we will modify this.
So in the case of peak also we will check if the out stack is empty.
If it is empty we will take everything from the in stack one at a time by popping from it.
And then we push that value to the out stack.
Now once this is done, we just want to return the last element without popping it over.
Here we can return this dot out stack.
And then this is an array.
We have implemented the stack as an array.
So we just need to pass the index over here.
So we can have this dot out stack dot length minus one.
So this is the last index in the out stack array.
So we are going to pass this index.
This will give us the last element in the out stack.
And that's the element which was first inserted right.
So this is how we can implement the Peek method.
And then finally we have the empty method over here.
Now we know that elements in the queue are either stored in one of these two stacks.
Right.
So if both these stacks are empty then we can be sure that the queue is empty.
So that is all that we need to check over here.
So let's have two variables.
Let's call it in stack length.
Which is the length of the in stack.
So this is equal to this dot in stack dot length.
And then let's have out stack length.
So this is equal to this dot out stack dot length.
So if both of these are zero then we have to return true.
Right.
So if both of them are zero if both.
R0, then we need to return true.
So for this we can say return not in stack length.
And.
Not out.
Stack length.
But what happens over here if the stack length is equal to zero?
This will be not of zero.
So that would be truthy because we know zero is falsy so not of zero will be truthy.
And then over here also right.
If it is zero it will be truthy.
So if both of these are true because we have an end condition over here.
So if this is truthy and this is truthy we return true.
And that would be the case when both the lengths are equal to zero.
So that is it.
We have completed writing the four instance methods.
And this is implementing a queue with stacks.
Now let's go ahead and test our code.
So for this let's have an object.
So I can say const queue is equal to new my queue.
Now let us run our code.
All right.
So we have a queue object.
Now let's define let's push something to our queue.
So for example we can say queue dot push.
One.
And let me push another value, which is two.
Let me push one more value, which is three.
Now if I pop from the q so q dot pop, I should get back the element which was first inserted, which
was one.
Right.
So let's do that.
So when we do this you can see we get one, which is correct.
If I pop again I should get two.
If I pop again I should get three.
Now if I pop again I don't get anything because the queue is empty now.
Now push and pop is working.
Now what about empty?
So let's try Q dot empty.
Now we know it's empty because we have popped everything from it.
And yes, the queue is actually empty.
Now again, let's push something to it.
So Q dot, push one.
Now if I call q dot empty.
We are getting false.
So empty is also working.
Now let's again push some more values.
So q dot push.
Um let's have two.
And let's push three to the cube.
Now, if we do q dot peak, we should get back one right, which is the element which will would be
returned if we pop.
So that's the element which was first inserted which is there in our queue.
So this is also working.
So yes our code is working.
Now let's take a look at the code that we have written and just walk through it.
So for this let me grab a pen.
All right.
So over here we have these two stacks.
So this is the in stack.
And it's an empty array at this moment.
And then we have the out stack.
So this is also empty.
So the way we are implementing the push function over here is that when we are calling this with a value,
we're just pushing it to our stack.
So when we inserted one, two and three what happened is when we insert one it comes over here.
Then when we insert two we are adding at the end.
So we get two over here.
Then when we insert three it comes over here.
Now let's take a look at the pop function.
Now in the.
Bob function.
First, we are going to check if the out stack is empty.
So at this point we see that it is empty.
So what we are going to do is we are going to pop from the in stack.
So this would pop this element right.
So pop comes is is taking from the end.
So we take this element and then we are going to push it to our out stack.
So we get three over here.
Then this will keep happening as long as there is something in the in stack.
Right.
As long as the length of the in stack is not equal to zero.
So again we pop and then we are pushing it to our out stack.
And we pop again and we push it to our out stack.
Now once this is done we are going to return this dot out dot pop.
So when we pop from here, you can see we are getting this element which is one.
And that's true right.
So this was the element which was inserted first.
So you can see it's following the Fifo property first in first out.
Now let's say we add again elements to it.
So let's say we add the element four.
So again it would be added over here.
And then we add five.
And then again we pop.
So we have just popped this earlier right.
So again when we pop we are going to get two again over here.
When we come we see that the out stack is not empty.
So directly we are going to come over here and we will just pop from the out stack and return this.
So this would be returned.
So you can see among two, four among two.
And then what are the values.
Two is there and one was popped.
So we have three among three, two and four and five.
Among these two is the one that was inserted latest.
Right.
So when we pop we are getting two.
And that is correct.
So it's following the Fifo property.
So if we pop again we will get three.
Now if we want to pop again when we come over here all these were already popped out.
So we will see that the out stack is empty.
So again we come inside over here and we are going to pop from here and we will insert it to our out
stack.
So this is our out stack.
So this would be inserted over here.
And then again we pop this one this four over here.
And it will be inserted in our out stack.
And then we come over here and we are going to pop from the out stack and return it.
So this would be returned which is correct.
Right.
Among four and five we can see four was inserted first.
So again it's following the Fifo property.
So this is how the Pop function over here works.
Now let's take a look at the peek function.
Now the peek is also pretty much similar.
Again let's say we have our in stack.
So this is our in stack.
And the values 123 were inserted.
And then let's say we are peeking and the out stack is empty.
At this point over here we will see that the out stack is empty.
So we will take each element from the in stack and pop it and insert it to our out stack.
So that's happening over here.
We are popping over here.
And then we are pushing to our out stack.
Again.
This happens.
We pop, we push it to our out stack, we pop and we push it to our out stack.
At this point, this is going to be falsy because the length has become zero, and zero is falsy in
JavaScript.
So we come out of this and then we are going to return the element in the out stack array at index of
the length of the out stack minus one.
So the length over here is three.
So three minus one gives us two.
And we know that this is index zero.
This is one and this is two.
So we are going to return the element at index two which is one.
So we can see among one two and three this was the element that was inserted first.
So yes this is the element that would be coming out of the queue first.
So our peak function is working in this manner.
And then finally we have the empty function over here.
Now we can notice over here that elements are either stored in the in stack or the out stack.
Right.
So it would be either here or here.
Now it would the the queue is empty only when both of these together are empty.
Right.
So over here we are getting the length of the in stack.
And over here we are getting the length of the out stack.
So this over here this return statement will be true only if these two lengths are equal to zero.
So if this is zero and this is zero.
So over here we have the naught.
And over here also we have not.
So not zero and and not zero.
So zero is falsy.
So not zero.
This would become truthy.
And this also is truthy.
So when both of them are truthy we will return true.
So that means there is nothing in both these stacks.
So this is how the function works.
Now let's take a quick look at the time and space complexity over here.
Now first let's take a look at the time complexity.
Now this push Val over here.
This is just a constant time operation right.
We're just pushing to the array over here which is the in stack array.
So this is constant time.
Now what about pop.
Now pop and peek.
Both of them are going to have the same time complexity.
Now these which is pop and peep peek.
They are going to have an amortized constant time operation.
Right.
So it's going to be O of one time complexity amortized or on average.
Now why is that.
So now let's take the example.
Let's say we have 123 over here.
And the out stack is empty.
Now when we are peeking for the when we are let's say let's just take pop.
So when we are popping the for the first time, we will see this is empty.
So we will do N operations to get everything out from here and into our out stack.
Right?
So this is N operations.
But then when we are and then we pop this one.
So we have done N operations.
But then when we pop the next time it's just a constant time operation because we can return this.
And again if we pop we are just going to return this.
So you can see when we are doing three operations, when we pop three times, we are going to do O of
N operations, right?
Because this happened because the first time this was empty and we had to do N operations, that is
going through every element in the in stack and getting it to the out stack.
So on average we can say it's going to take O of one time because this over here O of three or O of
n is for n operations.
So again this this O of n can be written as n into o of one.
And again we did n operations over here.
So that's why we can say for one operation on average it's going to be an O of one time operation.
Or we can say the time complexity of pop and peak is going to be O of one amortized.
All right.
Now let's also take a look at the last function over here which is empty.
Now again over here we just need to check both lengths.
So these are constant time operations.
And then we just have to return this.
So again this over here is going to be a constant time operation.
Now what about the space complexity.
Let's take a look at that also.
Now over here we are implementing the queue using stacks.
And you can see we are using two stacks.
Right.
And then if you are having n elements these n elements would be either in one of these two stacks.
So that's why we can say that the space complexity is going to be of the order of n.