So in order for us to come up with a solution to this problem, we need to think about the right approach
of implementing statutes in such a way that we can achieve a.
Q And the trick here is the fact that the question says Stax, plural, but we still need to think about
how many Stax do we need to implement in order for this to work?
And also, what is the configuration of the Stax and their methods that allow us to achieve the same
behavior as a Q?
So let's first think about the behavioral differences and similarities between Q's and Stax so that
we can glean the correct insights.
Let's talk about inserting values.
If we were to insert the values one, two, three, four and five into a Q or into a stack, the order
is the exact same.
The Q would get one, two, three, four, five, and the stack would get one, two, three, four,
five.
So here we see insertion order does not change between a Q and a stack.
That's the first thing.
The next thing we've got to think about then is popping.
What about removing values?
When we remove a value from a Q, we remove it from the beginning.
So here we would, let's say, call pop on our Q we'd pull out the one.
If we were to call Pop again, we would pull out the two.
Similarly, if we were to call the pop methods on our stack, we would first get the five.
And then we would get the four.
So here we see the differences between the stack and the queue is the order of the elements that get
removed.
What we notice, though, is that if we wanted the elements one and two out of the stack, we would
need the values of the very beginning.
And essentially the only way a stack that could achieve the same kind of value extraction from a Q if
we're looking at the one and the two is such that if we had a different stack with the values in reverse
order five, four, three, two, one here what we notice is that this when you call pop on a stack
with this shape.
You will end up retrieving the 1/1 and then you would end up retrieving the two after.
Because we're removing from the end of this stack.
So that's really the insight here, is that the only way we can achieve the same values from a Q as
we would from a stack is if the values were in the reverse order that they were in the Q.
That is one big insight.
So what is the way that we need to do to get this stack that had the values one, two, three, four,
five into this stack that had the values, five, four, three, two and one.
Remember, we have to use stacks.
So here I'm just going to say stack two is the stack that we are trying to achieve in order, at the
very least, for us to pop values in the same way as the queue.
How do we get this stack to become this stack?
Well, let's imagine that we had some second stack.
So here we're running two stacks and this stack two is the stack that we want to achieve.
This here is also a stack.
As we pop values from this first stack here, what is the order that they come out in?
They come out as five, four, three, two and one because we're popping from the end.
First the five, then the four, then the three, then the two, then the one.
And here what we notice about this order is that it is the same order that we want elements to be inserted
into Stack two, because if we pop the five and then insert the five, well here in the second stack,
this five is now the first element.
Then we pop the four and we insert the four.
We see that this is achieving the order that we were looking for right here.
Similarly, what?
The three, the two and the one finally.
So what we notice now is that this stack is in the correct shape that we need it to be in order for
us to pop elements from this stack so that it achieves the same order of elements popped from our queue.
So immediately here we know that we should probably average two stacks.
But is this enough?
What happens if we were to push values into our queue, and how does that reflect in these two stacks
that we have?
So here I'm just going to make this more clear because we've achieved what we wanted with this shape
example.
And I want to just explicitly call this second stack stack too, just so that we're aware that we need
to be running two stacks.
So once we pop these values from Stack one into Stack two, we've removed these values as well.
So in order for us to achieve that shape, we see that we have an empty stack one and stack two is filled
with the values that we popped out of Stack one and then inserted into Stack two.
But let's say that after we popped two values from Stack two so that it matches the same as the Q that
we have.
So we popped out first the one, then we popped out the two.
So here we notice that these two are now the same and these elements represent the same elements in
the respective data structures.
Let's say we were to insert values six and seven now into our Q and then into our stack.
So if we inserted six and then we insert it seven.
What happens when we call pop three more times?
We are popping three, four or five.
Because that's the order in which they appear inside of our queue.
But here, let's think about what we need to do with our two stacks that we have achieved here.
We want to try and manipulate this so that it works with the same order of operations as the queue.
We have six and seven to insert into either of these two stacks.
If we insert it six and seven into stack two, well, they would go in the same order.
We figured that out during our first insight when we realized that the order of insertion is the same
between a Q and a stack.
So we can only insert it into either stack two or stack one and inserting it into stack two.
What happens?
Well, now, when we want to pop values three, four or five, we now can access these values because
we have to pop from the end of stack 2/1.
So what we see is that we would end up getting seven, six and then three, which is not correct.
So let's try the other thing.
What if we were to insert six and seven into stack one?
Well here now whenever we were to pop from stack two, three, four, five, we would end up getting
the values three, four or five from stack two, which is the exact same order that we want it to achieve.
With our.
Q So once we've popped these values out, what we'll notice is that we don't have any values in Stack
two left.
So let's say we were to keep popping values from both our Q and our two stack representation of our
Q.
Let's say we pop six and we pop seven.
Well, at this point, we can't pop six and seven from stack two because we have no values in Stack
two.
And with Stack one, we see we have our original problem.
It's not in the order that we want, but we already know what to do when we need to achieve the reverse
order.
We push these values by popping them out and then pushing them into stack two.
So by popping it out first we pop out the seven and we insert it into stack two, then we pop the six
and we put it into Stack two, and once again we now have achieved the order that we want.
So now when I pop out from our stack two, we'll get six.
And then when I pop again, we'll get seven.
So here we see that we've achieved this on Q and DK method from our Q using two stacks.
The big thing that we also want to infer is that when we think about it, as long as there are values
inside of Stack and we call the pop or the DX Q method on this Q represented by two stacks, we want
to pop values from stack two because it will be the order that we want it in.
It's only when Stack two is empty that we want to do that whole reversal process of popping values from
Stack one and then pushing them into Stack two before we continue popping those values off of Stack
two to achieve that order.
This makes sense because while we push and pull values out of our queue, we want to be able to achieve
that same order with our two stack representation.
So that's really the key.
If you push values, you push them into stack one.
If you pop values, you pop them out of stack two until this is empty, then you reverse stack one into
stack two and you continue popping values out of stack two.
The two remaining methods is empty and its peak peak is pretty much the exact same as DX Q or the pop
method.
The only difference is that instead of actually removing the value from stack two, we just want to
return a reference to the last value that is inside of Stack two.
So I will leave you to figure out the implementation of that as well as empty, because they're actually
quite simple.
And I want you to think about it a little bit so that you really understand how these two stacks work
inside of this implementation of a queue.
And if you're familiar with implementing classes in your native language as well as in JavaScript,
definitely try and code it out yourself.
If you're unfamiliar with classes, I'm going to link a resource in your resources folder that will
teach you all about classes and JavaScript so that you can still take a crack at implementing it yourself.
After that, I'm going to show you in the next video how to do it yourself, but definitely take a strike
at trying to solve these four methods inside of our Q with stacks class implementation yourself.