Welcome back.
Now we need to implement a queue or a Fifo data structure using only two stacks.
And we have to write a my queue class.
And these are the four instance methods which is mentioned in the question push, pop, peek and empty
which we need to implement for the My Queue class.
And again the catch is that this is a Fifo or first in first out data structure.
Now how are we going to do this?
In the question it says that we can use two stacks.
All right.
So this is how we will implement this.
We will have two stacks.
Let's call one stack in stack.
So the first stack is in stack.
And again we are implementing a stack as just an array.
And let's call the second stack out stack.
So these are the two stacks that we have.
And initially they are just going to be two empty arrays.
Now let's see how we are going to do this.
Now if you are pushing a value to the queue we will just push to the in stack.
So we get a value over here.
So we have one over here.
Now let's say we push one more value.
So we have two over here.
And let's say we have another value pushed to the queue.
So we add three also to the in stack.
Now we will use the out stack when we want to pop or peek.
All right.
So let's try to understand how we do this.
Now we need two stacks because if we want to pop we cannot just pop from the end of the in stack and
return this right.
We cannot give this three because then it would not be Fifo or first in, first out.
The first element into the in stack or the queue in this case was one.
So when we pop, we have to return the first element one itself, because it has to be a Fifo data structure.
So let's see how we can do this.
So first we take a look at pop.
Pop over here.
And peek is going to be just similar to pop.
All right.
So what we will do is first we will check is the out stack empty when pop is called.
So over here we see that the out stack is empty.
So what we do is we are going to pop every element from the in stack and push it to our out stack.
So when we pop we take from the end of the in stack.
So we're going to take this three or pop it out from the in stack.
And we push it to our out stack.
Again our in stack is not yet empty.
So we pop again from the in stack.
That is, we take this element over here and we push it to our out stack.
Again, our in stack is not empty.
So we are going to pop from the in stack, which is this element over here.
And then we push it to our out stack.
All right.
So all these elements now are in our out stack.
And now we can see that if we pop from the out stack we will get this element over here.
And that's the correct element right.
To follow the Fifo property.
Because this was the element which was first inserted to the queue.
So now we will just pop from the out stack and return this element over here.
So this is how we will implement pop.
Now let's say we again push some more values to it.
So for example let's say we have just popped this value out.
So this is removed from the out stack.
Now let's say we are going to add four to the queue.
So we are going to again push it to our in stack.
And let's say we add five to the queue.
So we have five, four, five and three and two in our queue.
Now among these elements we know that two was the element that was first inserted.
So if we are going to pop we should be getting back two right.
So again let's say we call pop.
Now we see that the out stack is not empty.
So this is not empty.
So all we are going to do is we're just going to pop from the out stack and run it.
So this is going to be returned.
Now let's say we pop again.
So again we check is the out stack empty.
No it's not empty.
So we are just going to pop from the out stack.
And we are giving back three.
So you can see it's following the Fifo property because among three four and five three was inserted
first.
So that's the value that we will return.
And we will just pop from the out stack and return it.
Now let's say we again call pop.
Now at this point this is again empty.
So we are going to take the elements in the in stack and insert it to the out stack one at a time.
So we pop from the in stack and we push it to the out stack again.
We pop from the in stack and we push it to the out stack.
And after every element from the in stack is removed because now you can see it's empty.
We are just going to pop from the out stack, which will give the value four.
So again you can see it's following the Fifo property because among four and five, four was inserted
first.
So we are going to return the element which was first returned.
So this is how we will implement the pop function.
All right.
Now peak is going to be pretty much similar because we just need to return the last element in the out
stack.
We don't need to pop it, but we will just read that element and return it.
So it's it's the same thing.
Let's say we we add one and two to our stack in stack.
We push it and then let's say we are calling peak.
So first we will check is the out stack empty?
If it is empty, we will pop from the in stack and push it to the out stack till the in stack becomes
empty.
So two is inserted again.
This is not empty the in stack.
So we pop and we are pushing it to the out stack.
So we have two and one in the out stack.
Now.
Now when again we have called peak right.
So we are just going to return the last element over here.
The length of the out stack is three two at this point.
Right.
So we are going to return the element at index two minus one which is equal to one.
So this is index.
You know this is index one.
So we will just return the element at index one which is one.
So you can see that Pop and Peek operate in a similar manner.
All right.
So we have covered these three operations of instance methods.
Now let's take a look at the last instance method which is empty.
Now it's mentioned that if the queue is empty this should return true.
Otherwise this should return false.
So we can see that the elements in the queue will either be in the in stack or the out stack.
Right.
So we have seen push and pop.
So initially when we push we are pushing to the in stack.
And then when we are popping we are taking the elements from the in stack, putting to the out stack
and then popping from the out stack.
Right.
So you can see any element.
If it is there in the queue, it can be either in the in stack or in the out stack.
So if the queue is empty, all we need to check is if both the in stack and the out stack is empty.
So if both of them are empty, or if both of them are of are of length zero, then we will just return
true.
Otherwise we will just return false.
So this is how we will return.
Implement the empty function over here.
All right.
So we have discussed how we can implement these four functions.
All right now let's take a look at the complexity analysis of the solution.
Now pushing is just a constant time operation because we are just inserting the value to the in stack
right now when it comes to popping or peaking, it's going to be O of one time complexity amortized.
Now again why is that?
So if you are doing N operations, the time complexity is going to be O of N.
And then because we have done n operations, we can write o of n as n into o of one.
So on an average it's going to be an O of one operation.
So this is for n operations right.
So these two can cancel out.
So on an average it's going to be an O of one operation peaking and popping uh peaking and popping from
the um the queue.
All right.
Now again why is that.
So we have discussed that.
Let's say we have inserted the values one, two and three.
Now let's say we are doing three over here we have n operations right.
Let n be equal to three.
Let's say we are doing three pops.
All right.
So we are popping three times.
Now.
First, when we are popping, we have to do O of N operations because we have to take this three.
Put it over here.
Take this two.
Put it over here and take this one.
Put it over here so you can see one time it's taking O of n.
But then in all the other instances we're just taking the last element from the out stack array over
here, which is a constant time operation.
Right.
So in the second and third times it's just going to be an O of one operation.
So net it's an O of n operation or O of three operation.
I'm just writing it o of n as, as a general manner.
So for n operations it's o of n.
So that's why we can say the time complexity is O of one amortized or on average.
Now let's proceed.
What about the empty function over here for this.
Also we just need to check if the two stacks are empty.
That's it right.
And if both of them are empty we return true.
Otherwise we return false.
So you can see the empty instance method over here is also a constant time operation.
All right.
Now what about the space complexity.
The space complexity of this is going to be O of N, because we are making use of these two stacks to
implement our queue.
And if the queue has n elements, the n elements will either be over here or here.
Right.
So together we'll have n elements.
So that's why we can say that the space complexity, which is because of the because we are using the
two stacks, is going to be of the order of n.