1
00:00:00,250 --> 00:00:04,060
So in order for us to come up with a
solution to this problem, we need to

2
00:00:04,070 --> 00:00:09,000
think about the right approach of
implementing stacks in such a way that we

3
00:00:09,010 --> 00:00:10,000
can achieve a queue.

4
00:00:10,450 --> 00:00:12,140
And the trick here is the fact that the

5
00:00:12,150 --> 00:00:14,600
question says stacks plural.

6
00:00:15,270 --> 00:00:16,760
But we still need to think about how many

7
00:00:16,770 --> 00:00:20,300
stacks do we need to implement in order
for this to work, and also what is the

8
00:00:20,310 --> 00:00:25,420
configuration of these stacks and their
methods that allow us to achieve the same

9
00:00:25,430 --> 00:00:26,720
behavior as a queue.

10
00:00:26,730 --> 00:00:29,420
So let's first think about the behavioral

11
00:00:29,430 --> 00:00:33,660
differences and similarities between
queues and stacks so that we can glean

12
00:00:33,670 --> 00:00:34,920
the correct insights.

13
00:00:35,430 --> 00:00:37,500
Let's talk about inserting values.

14
00:00:37,890 --> 00:00:44,900
If we were to insert the values 1, 2, 3,
4, and 5 into a queue or into a stack,

15
00:00:45,430 --> 00:00:47,380
the order is the exact same.

16
00:00:47,710 --> 00:00:50,900
The queue would get 1, 2, 3, 4, 5, and

17
00:00:50,910 --> 00:00:53,480
the stack would get 1, 2, 3, 4, 5.

18
00:00:53,490 --> 00:00:56,700
So here we see insertion order does not

19
00:00:56,710 --> 00:00:58,320
change between a queue and a stack.

20
00:00:58,470 --> 00:00:59,320
That's the first thing.

21
00:00:59,850 --> 00:01:02,500
The next thing we got to think about then
is popping.

22
00:01:02,830 --> 00:01:04,240
What about removing values?

23
00:01:04,770 --> 00:01:07,120
When we remove a value from a queue, we

24
00:01:07,130 --> 00:01:08,140
remove it from the beginning.

25
00:01:08,490 --> 00:01:10,640
So here we would, let's say, call pop on

26
00:01:10,650 --> 00:01:11,020
our queue.

27
00:01:11,230 --> 00:01:12,160
We'd pull out the 1.

28
00:01:13,690 --> 00:01:17,180
If we were to call pop again, we would
pull out the 2.

29
00:01:19,850 --> 00:01:24,380
Similarly, if we were to call the pop
methods on our stack, we would first get

30
00:01:24,390 --> 00:01:27,960
the 5, and then we would get the 4.

31
00:01:29,590 --> 00:01:32,200
So here we see the differences between

32
00:01:32,210 --> 00:01:35,680
the stack and the queue is the order of
the elements that get removed.

33
00:01:36,610 --> 00:01:41,380
What we notice though is that if we
wanted the elements 1 and 2 out of the

34
00:01:41,390 --> 00:01:45,020
stack, we would need the values at the
very beginning.

35
00:01:45,030 --> 00:01:50,320
And essentially the only way a stack that
could achieve the same kind of value

36
00:01:50,330 --> 00:01:54,840
extraction from a queue, if we're looking
at the 1 and the 2, is such that if we

37
00:01:54,850 --> 00:02:03,060
had a different stack with the values in
reverse order, 5, 4, 3, 2, 1, here what

38
00:02:03,070 --> 00:02:10,440
we notice is that this, when you call pop
on a stack with this shape, you will end

39
00:02:10,450 --> 00:02:16,420
up retrieving the 1 first, and then you
would end up retrieving the 2 after,

40
00:02:17,470 --> 00:02:20,440
because we're removing from the end of
this stack.

41
00:02:20,830 --> 00:02:24,580
So that's really the insight here, is
that the only way we can retrieve the

42
00:02:24,590 --> 00:02:30,600
same values from a queue as we would from
a stack, is if the values were in the

43
00:02:30,610 --> 00:02:33,340
reverse order that they were in the queue.

44
00:02:34,290 --> 00:02:36,220
That is one big insight.

45
00:02:37,150 --> 00:02:44,440
So what is the way that we need to do to
get this stack that had the values 1, 2,

46
00:02:44,570 --> 00:02:51,720
3, 4, 5, into this stack that had the
values 5, 4, 3, 2, and 1?

47
00:02:52,130 --> 00:02:54,300
Remember, we have to use stacks.

48
00:02:54,670 --> 00:02:56,980
So here I'm just going to say stack 2 is

49
00:02:56,990 --> 00:02:59,020
the stack that we are trying to achieve.

50
00:02:59,450 --> 00:03:01,440
In order at the very least for us to pop

51
00:03:01,450 --> 00:03:03,380
values in the same way as the queue.

52
00:03:03,390 --> 00:03:07,120
How do we get this stack to become this stack?

53
00:03:07,870 --> 00:03:12,580
Well, let's imagine that we had some
second stack.

54
00:03:12,790 --> 00:03:14,540
So here we're running two stacks.

55
00:03:15,070 --> 00:03:17,180
And this stack 2 is the stack that we

56
00:03:17,190 --> 00:03:17,800
want to achieve.

57
00:03:18,190 --> 00:03:19,840
This here is also a stack.

58
00:03:20,790 --> 00:03:26,260
As we pop values from this first stack
here, what is the order that they come

59
00:03:26,270 --> 00:03:26,620
out in?

60
00:03:26,630 --> 00:03:31,940
They come out as 5, 4, 3, 2, and 1.

61
00:03:32,290 --> 00:03:33,620
Because we're popping from the end.

62
00:03:33,850 --> 00:03:36,660
First the 5, then the 4, then the 3, then

63
00:03:36,670 --> 00:03:37,820
the 2, then the 1.

64
00:03:38,470 --> 00:03:40,540
And here what we notice about this order

65
00:03:40,550 --> 00:03:47,140
is that it is the same order that we want
elements to be inserted into stack 2.

66
00:03:47,730 --> 00:03:53,080
Because if we pop the 5 and then insert
the 5, well here in the second stack,

67
00:03:53,350 --> 00:03:55,840
this 5 is now the first element.

68
00:03:55,850 --> 00:03:58,980
Then we pop the 4 and we insert the 4.

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

70
00:04:05,230 --> 00:04:09,040
Similarly with the 3, the 2, and the 1 finally.

71
00:04:09,870 --> 00:04:12,940
So what we notice now is that this stack

72
00:04:12,950 --> 00:04:19,240
is in the correct shape that we need it
to be in order for us to pop elements

73
00:04:19,250 --> 00:04:24,860
from this stack so that it achieves the
same order of elements popped from our queue.

74
00:04:24,870 --> 00:04:30,260
So immediately here we know that we
should probably leverage two stacks.

75
00:04:30,790 --> 00:04:32,160
But is this enough?

76
00:04:32,690 --> 00:04:35,560
What happens if we were to push values

77
00:04:35,570 --> 00:04:40,320
into our queue and how does that reflect
in these two stacks that we have?

78
00:04:40,830 --> 00:04:43,960
So here I'm just going to make this more
clear because we've achieved what we

79
00:04:43,970 --> 00:04:46,160
wanted with this shape example.

80
00:04:46,550 --> 00:04:48,840
And I want to just explicitly call this

81
00:04:48,850 --> 00:04:53,760
second stack, stack 2, just so that we're
aware that we need to be running two stacks.

82
00:04:54,870 --> 00:05:01,260
So once we pop these values from stack 1
into stack 2, we've removed these values

83
00:05:01,270 --> 00:05:01,660
as well.

84
00:05:02,050 --> 00:05:04,200
So in order for us to achieve that shape,

85
00:05:04,290 --> 00:05:08,760
we see that we have an empty stack 1 and
stack 2 is filled with the values that we

86
00:05:08,770 --> 00:05:11,600
popped out of stack 1 and then inserted
into stack 2.

87
00:05:12,570 --> 00:05:17,620
But let's say that after we pop two
values from stack 2 so that it matches

88
00:05:17,630 --> 00:05:19,920
the same as the queue that we have.

89
00:05:20,070 --> 00:05:22,100
So we popped out first the 1, then we

90
00:05:22,110 --> 00:05:22,900
popped out the 2.

91
00:05:22,910 --> 00:05:25,580
So here we notice that these two are now

92
00:05:25,590 --> 00:05:30,900
the same and these elements represent the
same elements in the respective data structures.

93
00:05:31,570 --> 00:05:37,900
Let's say we were to insert values 6 and
7 now into our queue and then into our stack.

94
00:05:38,290 --> 00:05:45,000
So if we inserted 6 and then we inserted
7, what happens when we call pop three

95
00:05:45,010 --> 00:05:45,580
more times?

96
00:05:46,110 --> 00:05:50,340
We are popping 3, 4, 5 because that's the

97
00:05:50,350 --> 00:05:54,420
order in which they appear inside of our queue.

98
00:05:55,650 --> 00:05:58,440
But here, let's think about what we need

99
00:05:58,450 --> 00:06:01,480
to do with our two stacks that we have
achieved here.

100
00:06:01,810 --> 00:06:06,680
We want to try and manipulate this so
that it works with the same order of

101
00:06:06,690 --> 00:06:08,180
operations as the queue.

102
00:06:09,310 --> 00:06:12,640
We have 6 and 7 to insert into either of

103
00:06:12,650 --> 00:06:13,380
these two stacks.

104
00:06:13,790 --> 00:06:17,220
If we inserted 6 and 7 into stack 2,

105
00:06:17,230 --> 00:06:19,280
well, they would go in the same order.

106
00:06:19,410 --> 00:06:21,240
We figured that out during our first

107
00:06:21,250 --> 00:06:26,600
insight when we realized that the order
of insertion is the same between a queue

108
00:06:26,610 --> 00:06:27,100
and a stack.

109
00:06:27,630 --> 00:06:29,360
So we can only insert it into either

110
00:06:29,370 --> 00:06:30,420
stack 2 or stack 1.

111
00:06:30,830 --> 00:06:32,760
And inserting it into stack 2, what happens?

112
00:06:33,430 --> 00:06:39,080
Well, now when we want to pop values 3,
4, 5, we now can't access these values

113
00:06:39,090 --> 00:06:41,440
because we have to pop from the end of
stack 2 first.

114
00:06:41,750 --> 00:06:47,600
So what we see is that we would end up
getting 7, 6, and then 3, which is not correct.

115
00:06:48,530 --> 00:06:50,260
So let's try the other thing.

116
00:06:50,670 --> 00:06:53,900
What if we were to insert 6 and 7 into

117
00:06:53,910 --> 00:06:54,620
stack 1?

118
00:06:55,570 --> 00:06:57,620
Well, here now, whenever we were to pop

119
00:06:57,630 --> 00:07:03,480
from stack 2, 3, 4, 5, we would end up
getting the values 3, 4, 5 from stack 2,

120
00:07:03,550 --> 00:07:10,300
which is the exact same order that we
want it to achieve with our queue.

121
00:07:11,090 --> 00:07:17,080
So once we've popped these values out,
what we'll notice is that we don't have

122
00:07:17,090 --> 00:07:18,380
any values in stack 2 left.

123
00:07:18,850 --> 00:07:20,740
So let's say we were to keep popping

124
00:07:20,750 --> 00:07:24,920
values from both our queue and our 2
stack representation of our queue.

125
00:07:25,730 --> 00:07:28,100
Let's say we pop 6 and we pop 7.

126
00:07:30,160 --> 00:07:32,930
Well, at this point, we can't pop 6 and 7

127
00:07:32,940 --> 00:07:35,130
from stack 2 because we have no values in
stack 2.

128
00:07:35,600 --> 00:07:38,410
And with stack 1, we see we have our
original problem.

129
00:07:38,540 --> 00:07:40,050
It's not in the order that we want.

130
00:07:40,200 --> 00:07:41,690
But we already know what to do when we

131
00:07:41,700 --> 00:07:43,090
need to achieve the reverse order.

132
00:07:43,100 --> 00:07:46,410
We push these values by popping them out

133
00:07:46,420 --> 00:07:47,890
and then pushing them into stack 2.

134
00:07:48,420 --> 00:07:50,190
So by popping it out, first we pop out

135
00:07:50,200 --> 00:07:52,450
the 7 and we insert it into stack 2.

136
00:07:52,560 --> 00:07:55,170
Then we pop the 6 and we put it into

137
00:07:55,180 --> 00:07:55,750
stack 2.

138
00:07:56,120 --> 00:07:58,210
And once again, we now have achieved the

139
00:07:58,220 --> 00:07:59,350
order that we want.

140
00:07:59,560 --> 00:08:02,690
So now when I pop out from our stack 2,

141
00:08:03,220 --> 00:08:04,190
we'll get 6.

142
00:08:04,320 --> 00:08:06,750
And then when I pop again, we'll get 7.

143
00:08:07,640 --> 00:08:13,590
So here we see that we've achieved this
onQueue and dequeue method from our queue

144
00:08:13,600 --> 00:08:14,970
using 2 stacks.

145
00:08:15,940 --> 00:08:18,550
The big thing that we also want to infer

146
00:08:18,560 --> 00:08:23,170
is that when we think about it, as long
as there are values inside of stack 2 and

147
00:08:23,180 --> 00:08:30,390
we call the pop or the dequeue method on
this queue represented by 2 stacks, we

148
00:08:30,400 --> 00:08:35,530
want to pop values from stack 2 because
it will be the order that we want it in.

149
00:08:35,540 --> 00:08:41,330
It's only when stack 2 is empty that we
want to do that whole reversal process of

150
00:08:41,340 --> 00:08:45,250
popping values from stack 1 and then
pushing them into stack 2 before we

151
00:08:45,260 --> 00:08:49,470
continue popping those values off of
stack 2 to achieve that order.

152
00:08:49,860 --> 00:08:55,630
This makes sense because while we push
and pull values out of our queue, we want

153
00:08:55,640 --> 00:08:58,930
to be able to achieve that same order
with our 2 stack representation.

154
00:08:59,560 --> 00:09:00,610
So that's really the key.

155
00:09:00,960 --> 00:09:02,650
If you push values, you push them into

156
00:09:02,660 --> 00:09:03,150
stack 1.

157
00:09:03,160 --> 00:09:05,290
If you pop values, you pop them out of

158
00:09:05,300 --> 00:09:06,670
stack 2 until this is empty.

159
00:09:06,920 --> 00:09:09,190
Then you reverse stack 1 into stack 2 and

160
00:09:09,200 --> 00:09:10,970
you continue popping values out of stack 2.

161
00:09:12,060 --> 00:09:16,150
The two remaining methods is empty and

162
00:09:16,160 --> 00:09:17,270
it's peak.

163
00:09:17,740 --> 00:09:20,390
Peak is pretty much the exact same as

164
00:09:20,400 --> 00:09:22,590
dequeue or the pop method.

165
00:09:22,920 --> 00:09:24,050
The only difference is that instead of

166
00:09:24,060 --> 00:09:28,850
actually removing the value from stack 2,
we just want to return a reference to the

167
00:09:28,860 --> 00:09:31,370
last value that is inside of stack 2.

168
00:09:31,380 --> 00:09:33,870
So I will leave you to figure out the

169
00:09:33,880 --> 00:09:38,190
implementation of that as well as empty
because they're actually quite simple and

170
00:09:38,200 --> 00:09:41,970
I want you to think about it a little bit
so that you really understand how these

171
00:09:41,980 --> 00:09:45,670
two stacks work inside of this
implementation of a queue.

172
00:09:46,880 --> 00:09:50,490
And if you're familiar with implementing
classes in your native language as well

173
00:09:50,500 --> 00:09:53,150
as in JavaScript, definitely try and code
it out yourself.

174
00:09:53,320 --> 00:09:57,850
If you are unfamiliar with classes, I'm
going to link a resource in your

175
00:09:57,860 --> 00:10:02,350
resources folder that will teach you all
about classes in JavaScript so that you

176
00:10:02,360 --> 00:10:05,770
can still take a crack at implementing it yourself.

177
00:10:06,800 --> 00:10:08,350
After that, I'm going to show you in the

178
00:10:08,360 --> 00:10:12,950
next video how to do it yourself but
definitely take a strike at trying to

179
00:10:12,960 --> 00:10:17,870
solve these four methods inside of our
QueueWithStacks class implementation yourself.