1
00:00:00,550 --> 00:00:05,710
So in order for us to come up with a solution to this problem, we need to think about the right approach

2
00:00:05,710 --> 00:00:10,180
of implementing stacks in such a way that we can achieve a cue.

3
00:00:10,510 --> 00:00:14,890
And the trick here is the fact that the question says stacks plural.

4
00:00:15,340 --> 00:00:18,910
But we still need to think about how many stacks do we need to implement in order for this to work?

5
00:00:18,910 --> 00:00:25,510
And also what is the configuration of these stacks and their methods that allow us to achieve the same

6
00:00:25,510 --> 00:00:26,880
behavior as a queue.

7
00:00:27,430 --> 00:00:33,010
So let's first think about the behavioral differences and similarities between Qs and stacks so that

8
00:00:33,010 --> 00:00:35,090
we can glean the correct insights.

9
00:00:35,710 --> 00:00:37,660
Let's talk about inserting values.

10
00:00:37,930 --> 00:00:45,880
If we were to insert the values one, two, three, four and five into a cube or into a stack, the

11
00:00:45,880 --> 00:00:47,500
order is the exact same.

12
00:00:47,680 --> 00:00:53,140
The cube would get one, two, three, four, five, and the stack would get one, two, three, four,

13
00:00:53,170 --> 00:00:53,560
five.

14
00:00:54,190 --> 00:00:58,480
So here we see insertion order does not change between a Q and A stack.

15
00:00:58,510 --> 00:00:59,440
That's the first thing.

16
00:01:00,100 --> 00:01:02,740
The next thing we got to think about then is popping.

17
00:01:02,890 --> 00:01:04,420
What about removing values?

18
00:01:04,870 --> 00:01:08,410
When we remove a value from a Q, we remove it from the beginning.

19
00:01:08,440 --> 00:01:09,280
So here we were.

20
00:01:09,580 --> 00:01:12,310
Let's say call pop on our Q we pull out the one.

21
00:01:13,870 --> 00:01:17,380
If we were to call Pop again, we would pull out the two.

22
00:01:19,990 --> 00:01:25,090
Similarily, if we were to call the methods on our stack, we would first get the five.

23
00:01:26,460 --> 00:01:28,110
And then we would get the four.

24
00:01:29,890 --> 00:01:35,900
So here we see the differences between the stack and the Q is the order of the elements that get removed.

25
00:01:36,970 --> 00:01:43,090
What we noticed, though, is that if we wanted the elements one and two out of the stack, we would

26
00:01:43,090 --> 00:01:45,220
need the values of the very beginning.

27
00:01:45,580 --> 00:01:51,730
And essentially the only way a stack that could achieve the same kind of value extraction from a Q if

28
00:01:51,730 --> 00:01:58,990
we're looking at the one in the two, is such that if we had a different stack with the values in reverse

29
00:01:58,990 --> 00:02:06,910
order, five, four, three, two, one here, what we notice is that this when you call pop on a stack

30
00:02:06,910 --> 00:02:08,350
with this shape.

31
00:02:09,810 --> 00:02:12,510
You will end up retrieving the one first.

32
00:02:13,360 --> 00:02:16,630
And then you would end up retrieving the two after.

33
00:02:17,790 --> 00:02:23,160
Because we're we're moving from the end of this stack, so that's really the insight here, is that

34
00:02:23,160 --> 00:02:30,180
the only way we can achieve the same values from a cue as we would from a stack is if the values were

35
00:02:30,180 --> 00:02:33,510
in the reverse order that they were in the queue.

36
00:02:34,590 --> 00:02:36,360
That is one big insight.

37
00:02:37,420 --> 00:02:45,240
So what is the way that we need to do to get this stack that had the values one, two, three, four,

38
00:02:45,250 --> 00:02:51,840
five into this stack that had the values five, four, three, two and one.

39
00:02:52,240 --> 00:02:54,520
Remember, we have to use tax.

40
00:02:54,640 --> 00:03:00,340
So here I'm just going to say that, too, is the stack that we are trying to achieve in order at the

41
00:03:00,340 --> 00:03:03,160
very least for us to pop values in the same way as the.

42
00:03:03,160 --> 00:03:07,240
Q How do we get this stack to become this stack?

43
00:03:08,220 --> 00:03:16,110
Well, let's imagine that we had some second stack, so here we're running two stacks and this stack

44
00:03:16,110 --> 00:03:17,910
two is the stack that we want to achieve.

45
00:03:18,360 --> 00:03:19,980
This here is also a stack.

46
00:03:20,990 --> 00:03:26,690
As we pop values from this first stack here, what is the order that they come out in?

47
00:03:27,330 --> 00:03:33,740
They come out as five, four, three, two and one because we're popping from the end.

48
00:03:33,740 --> 00:03:37,940
First the five, then the four, then the three, then the two, then the one.

49
00:03:38,480 --> 00:03:45,500
And here, what we notice about this order is that it is the same order that we want elements to be

50
00:03:45,500 --> 00:03:52,580
inserted into stack two, because if we pop the five and then insert the five, well, here in the second

51
00:03:52,580 --> 00:03:56,030
stack, this five is now the first element.

52
00:03:56,360 --> 00:03:59,140
Then we pop the four and we insert the four.

53
00:03:59,720 --> 00:04:05,120
We see that this is achieving the order that we were looking for right here.

54
00:04:05,240 --> 00:04:06,080
Similarily what?

55
00:04:06,080 --> 00:04:09,200
The three, the two and the one finally.

56
00:04:10,070 --> 00:04:17,750
So what we notice now is that this stack is in the correct shape that we need it to be in order for

57
00:04:17,750 --> 00:04:25,070
us to pop elements from this stack so that it achieves the same order of elements popped from our Q

58
00:04:25,640 --> 00:04:30,470
So immediately here we know that we should probably will average two stacks.

59
00:04:31,010 --> 00:04:32,300
But is this enough?

60
00:04:32,810 --> 00:04:39,830
What happens if we were to push values into our queue and how does that reflect in these two stacks

61
00:04:39,830 --> 00:04:40,400
that we have?

62
00:04:40,880 --> 00:04:45,710
So here I'm just going to make this more clear because we've achieved what we wanted with this shape

63
00:04:45,710 --> 00:04:46,400
example.

64
00:04:46,880 --> 00:04:52,430
And I want to just explicitly call this second stack stack, too, just so that we're aware that we

65
00:04:52,430 --> 00:04:53,930
need to be running two stacks.

66
00:04:55,060 --> 00:05:01,790
So once we pop these values from stack one into stack two, we've removed these values as well.

67
00:05:02,410 --> 00:05:07,930
So in order for us to achieve that shape, we see that we have an empty stack one and stack two is filled

68
00:05:07,930 --> 00:05:11,710
with the values that we popped out of stack one and then inserted into stack to.

69
00:05:12,940 --> 00:05:19,480
But let's say that after we pop two values from stack two so that it matches the same as the Q that

70
00:05:19,480 --> 00:05:23,050
we have, so we popped up first the one, then we popped out the two.

71
00:05:23,360 --> 00:05:28,630
So here we notice that these two are now the same and these elements represent the same elements in

72
00:05:28,630 --> 00:05:31,080
the respective data structures.

73
00:05:31,840 --> 00:05:38,030
Let's say we were to insert values six and seven now into our Q and then into our stack.

74
00:05:38,650 --> 00:05:41,830
So if we insert a six and then we inserted seven.

75
00:05:42,910 --> 00:05:48,430
What happens when we call pop three more times, we are popping three, four or five.

76
00:05:49,530 --> 00:05:54,570
Because that's the order in which they appear inside of our Q.

77
00:05:55,750 --> 00:06:02,140
But here, let's think about what we need to do with our two stacks that we have achieved here, we

78
00:06:02,140 --> 00:06:08,320
want to try and manipulate this so that it works with the same order of operations as the QUE.

79
00:06:09,340 --> 00:06:16,630
We have six and seven to insert into either of these two stacks, if we inserted six and seven into

80
00:06:16,630 --> 00:06:19,400
stack to well, they would go in the same order.

81
00:06:19,420 --> 00:06:26,110
We figured that out during our first insight when we realized that the order of insertion is the same

82
00:06:26,110 --> 00:06:27,250
between a Q and A stack.

83
00:06:27,820 --> 00:06:32,940
So we can only inserted into the stack to stack one and inserting and it's a stack to what happens.

84
00:06:33,430 --> 00:06:36,840
We'll know when we want to pop values three, four or five.

85
00:06:37,270 --> 00:06:41,590
We now can access these values because we have to pop from the end of stack to first.

86
00:06:41,920 --> 00:06:47,770
So what we see is that we would end up getting seven, six and then three, which is not correct.

87
00:06:48,940 --> 00:06:50,360
So let's try the other thing.

88
00:06:50,680 --> 00:06:54,760
What if we were to insert six and seven into stack one?

89
00:06:55,680 --> 00:07:01,200
Well, here now, whenever we were to pop from stack two, three, four or five, we would end up getting

90
00:07:01,200 --> 00:07:08,010
the values three, four or five from stack two, which is the exact same order that we want it to achieve.

91
00:07:09,020 --> 00:07:17,600
With our Q So once we've popped these values out, what you'll notice is that we don't have any values

92
00:07:17,600 --> 00:07:18,530
and stock to left.

93
00:07:18,890 --> 00:07:25,040
So let's say we were to keep popping values from both our Q and R to stack representation of our Q,

94
00:07:25,940 --> 00:07:28,250
let's say we pop six and we pop seven.

95
00:07:30,240 --> 00:07:35,010
Well, at this point, we can't pop six and seven from stack two because we have no values and stacked

96
00:07:35,010 --> 00:07:38,550
two and with stack one, we see we have our original problem.

97
00:07:38,550 --> 00:07:41,460
It's not in the order that we want, but we already know what to do.

98
00:07:41,460 --> 00:07:47,160
When we need to achieve the reverse order, we push these values by popping them out and then pushing

99
00:07:47,160 --> 00:07:48,030
them into stack two.

100
00:07:48,480 --> 00:07:52,640
So by popping it out first, we pop out the seven and we insert it into stuck too.

101
00:07:52,680 --> 00:07:55,890
Then we pop the six and we put into stack two.

102
00:07:56,220 --> 00:07:59,500
And once again, we now have achieved the order that we want.

103
00:07:59,610 --> 00:08:06,900
So now when I pop out from our stack two, we'll get six, and then when I pop again, we'll get seven.

104
00:08:08,110 --> 00:08:15,250
So here we see that we've achieved this on cue and dequeue method from our cue using two stacks.

105
00:08:16,420 --> 00:08:21,700
The big thing that we also want to infer is that when we think about it, as long as there are values

106
00:08:21,700 --> 00:08:27,280
inside of Stack, too, and we call the pop or the dequeue method on this.

107
00:08:27,430 --> 00:08:34,990
Q represented by two stacks, we want to pop values from stack two because it will be the order that

108
00:08:34,990 --> 00:08:35,620
we want it in.

109
00:08:36,100 --> 00:08:42,230
It's only one stack two is empty that we want to do that whole reversal process of popping values,

110
00:08:42,230 --> 00:08:47,830
some stack one and then pushing them into stack two before we continue popping those values off of stack

111
00:08:47,830 --> 00:08:49,640
two to achieve that order.

112
00:08:50,020 --> 00:08:56,620
This makes sense because while we push and pull values out of our queue, we want to be able to achieve

113
00:08:56,620 --> 00:08:59,520
that same order with our two stack representation.

114
00:08:59,530 --> 00:09:00,760
So that's really the key.

115
00:09:00,940 --> 00:09:03,280
If you push values, you push them into stack one.

116
00:09:03,460 --> 00:09:08,410
If you pop values, you pop them out of stack two until this is empty, then you reverse stack one and

117
00:09:08,410 --> 00:09:11,110
stack two and you continue popping values out of stack to.

118
00:09:12,390 --> 00:09:21,870
The two remaining method's is empty and its peak peak is pretty much the exact same as dequeue or the

119
00:09:21,870 --> 00:09:22,740
pop method.

120
00:09:22,950 --> 00:09:27,540
The only difference is that instead of actually removing the value from stock two, we just want to

121
00:09:27,540 --> 00:09:31,520
return a reference to the last value that is inside of stock, too.

122
00:09:32,190 --> 00:09:37,320
So I will leave you to figure out the implementation of that as well as empty, because they're actually

123
00:09:37,320 --> 00:09:38,100
quite simple.

124
00:09:38,100 --> 00:09:43,110
And I want you to think about it a little bit so that you really understand how these two stacks work

125
00:09:43,560 --> 00:09:45,870
inside of this implementation of a cube.

126
00:09:46,850 --> 00:09:51,440
And if you're familiar with implementing classes in your native language as well as in JavaScript,

127
00:09:51,710 --> 00:09:53,330
definitely try and code it out yourself.

128
00:09:53,630 --> 00:09:59,540
If you are unfamiliar with classes, I'm going to link a resource in your resources folder that will

129
00:09:59,540 --> 00:10:05,950
teach you all about classes in JavaScript so that you can still take a crack at implementing it yourself.

130
00:10:06,860 --> 00:10:11,960
After that, I'm going to show you in the next video how to do it yourself, but definitely take a strike

131
00:10:12,110 --> 00:10:18,020
at trying to solve these four methods inside of our cube with stacks class implementation yourself.