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 queue.
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 queues and stacks so that we can glean
the correct insights.
Let's talk about inserting values.
If we were to insert the values 1, 2, 3, 4, and 5 into a queue or into a stack,
the order is the exact same.
The queue would get 1, 2, 3, 4, 5, and
the stack would get 1, 2, 3, 4, 5.
So here we see insertion order does not
change between a queue 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 queue, we
remove it from the beginning.
So here we would, let's say, call pop on
our queue.
We'd pull out the 1.
If we were to call pop again, we would pull out the 2.
Similarly, if we were to call the pop methods on our stack, we would first get
the 5, and then we would get the 4.
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 1 and 2 out of the
stack, we would need the values at the very beginning.
And essentially the only way a stack that could achieve the same kind of value
extraction from a queue, if we're looking at the 1 and the 2, is such that if we
had a different stack with the values in reverse order, 5, 4, 3, 2, 1, here what
we notice is that this, when you call pop on a stack with this shape, you will end
up retrieving the 1 first, and then you would end up retrieving the 2 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 retrieve the
same values from a queue 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 1, 2,
3, 4, 5, into this stack that had the values 5, 4, 3, 2, and 1?
Remember, we have to use stacks.
So here I'm just going to say stack 2 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 2 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 5, 4, 3, 2, and 1.
Because we're popping from the end.
First the 5, then the 4, then the 3, then
the 2, then the 1.
And here what we notice about this order
is that it is the same order that we want elements to be inserted into stack 2.
Because if we pop the 5 and then insert the 5, well here in the second stack,
this 5 is now the first element.
Then we pop the 4 and we insert the 4.
We see that this is achieving the order that we were looking for right here.
Similarly with the 3, the 2, and the 1 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 leverage 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 2, just so that we're aware that we need to be running two stacks.
So once we pop these values from stack 1 into stack 2, we've removed these values
as well.
So in order for us to achieve that shape,
we see that we have an empty stack 1 and stack 2 is filled with the values that we
popped out of stack 1 and then inserted into stack 2.
But let's say that after we pop two values from stack 2 so that it matches
the same as the queue that we have.
So we popped out first the 1, then we
popped out the 2.
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 6 and 7 now into our queue and then into our stack.
So if we inserted 6 and then we inserted 7, what happens when we call pop three
more times?
We are popping 3, 4, 5 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 6 and 7 to insert into either of
these two stacks.
If we inserted 6 and 7 into stack 2,
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 queue
and a stack.
So we can only insert it into either
stack 2 or stack 1.
And inserting it into stack 2, what happens?
Well, now when we want to pop values 3, 4, 5, we now can't access these values
because we have to pop from the end of stack 2 first.
So what we see is that we would end up getting 7, 6, and then 3, which is not correct.
So let's try the other thing.
What if we were to insert 6 and 7 into
stack 1?
Well, here now, whenever we were to pop
from stack 2, 3, 4, 5, we would end up getting the values 3, 4, 5 from stack 2,
which is the exact same order that we want it to achieve with our queue.
So once we've popped these values out, what we'll notice is that we don't have
any values in stack 2 left.
So let's say we were to keep popping
values from both our queue and our 2 stack representation of our queue.
Let's say we pop 6 and we pop 7.
Well, at this point, we can't pop 6 and 7
from stack 2 because we have no values in stack 2.
And with stack 1, 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 2.
So by popping it out, first we pop out
the 7 and we insert it into stack 2.
Then we pop the 6 and we put it into
stack 2.
And once again, we now have achieved the
order that we want.
So now when I pop out from our stack 2,
we'll get 6.
And then when I pop again, we'll get 7.
So here we see that we've achieved this onQueue and dequeue method from our queue
using 2 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 2 and
we call the pop or the dequeue method on this queue represented by 2 stacks, we
want to pop values from stack 2 because it will be the order that we want it in.
It's only when stack 2 is empty that we want to do that whole reversal process of
popping values from stack 1 and then pushing them into stack 2 before we
continue popping those values off of stack 2 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 2 stack representation.
So that's really the key.
If you push values, you push them into
stack 1.
If you pop values, you pop them out of
stack 2 until this is empty.
Then you reverse stack 1 into stack 2 and
you continue popping values out of stack 2.
The two remaining methods is empty and
it's 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 stack 2, we just want to return a reference to the
last value that is inside of stack 2.
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 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 QueueWithStacks class implementation yourself.