So in order for us to come up with a solution to this problem, we need to think about the right approach
of implementing stacks in such a way that we can achieve a cue.
And the trick here is the fact that the question says stacks plural.
But we still need to think about how many stacks do we need to implement in order for this to work?
And also what is the configuration of these stacks and their methods that allow us to achieve the same
behavior as a queue.
So let's first think about the behavioral differences and similarities between Qs and stacks 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 cube or into a stack, the
order is the exact same.
The cube 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 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 were.
Let's say call pop on our Q we pull out the one.
If we were to call Pop again, we would pull out the two.
Similarily, if we were to call the 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 Q is the order of the elements that get removed.
What we noticed, 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 in 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 one first.
And then you would end up retrieving the two after.
Because we're we're moving 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 cue as we would from a stack is if the values were
in the reverse order that they were in the queue.
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 tax.
So here I'm just going to say that, too, 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.
Q 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.
Similarily 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 Q
So immediately here we know that we should probably will 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 to.
But let's say that after we pop two values from stack two so that it matches the same as the Q that
we have, so we popped up 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 insert a six and then we inserted 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 Q.
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 QUE.
We have six and seven to insert into either of these two stacks, if we inserted six and seven into
stack to 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 inserted into the stack to stack one and inserting and it's a stack to what happens.
We'll know 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 to first.
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 or 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 you'll notice is that we don't have any values
and stock to left.
So let's say we were to keep popping values from both our Q and R to 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 and stacked
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 stuck too.
Then we pop the six and we put 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 cue and dequeue method from our cue 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, too, and we call the pop or the dequeue 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 one stack two is empty that we want to do that whole reversal process of popping values,
some 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 and
stack two and you continue popping values out of stack to.
The two remaining method's is empty and its peak peak is pretty much the exact same as dequeue or the
pop method.
The only difference is that instead of actually removing the value from stock two, we just want to
return a reference to the last value that is inside of stock, too.
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 cube.
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 are unfamiliar with classes, I'm going to link a resource in your resources folder that will
teach you all about classes in 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 cube with stacks class implementation yourself.