1
00:00:00,500 --> 00:00:01,460
Welcome back.

2
00:00:01,460 --> 00:00:07,460
Now we need to implement a queue or a Fifo data structure using only two stacks.

3
00:00:07,460 --> 00:00:09,980
And we have to write a my queue class.

4
00:00:09,980 --> 00:00:14,930
And these are the four instance methods which is mentioned in the question push, pop, peek and empty

5
00:00:14,930 --> 00:00:18,020
which we need to implement for the My Queue class.

6
00:00:18,020 --> 00:00:22,370
And again the catch is that this is a Fifo or first in first out data structure.

7
00:00:22,370 --> 00:00:24,170
Now how are we going to do this?

8
00:00:24,200 --> 00:00:26,750
In the question it says that we can use two stacks.

9
00:00:26,750 --> 00:00:27,140
All right.

10
00:00:27,140 --> 00:00:28,910
So this is how we will implement this.

11
00:00:28,940 --> 00:00:30,140
We will have two stacks.

12
00:00:30,140 --> 00:00:32,030
Let's call one stack in stack.

13
00:00:32,030 --> 00:00:33,590
So the first stack is in stack.

14
00:00:33,590 --> 00:00:36,290
And again we are implementing a stack as just an array.

15
00:00:36,290 --> 00:00:38,960
And let's call the second stack out stack.

16
00:00:39,500 --> 00:00:41,270
So these are the two stacks that we have.

17
00:00:41,270 --> 00:00:44,360
And initially they are just going to be two empty arrays.

18
00:00:44,390 --> 00:00:46,580
Now let's see how we are going to do this.

19
00:00:46,580 --> 00:00:50,900
Now if you are pushing a value to the queue we will just push to the in stack.

20
00:00:50,900 --> 00:00:51,980
So we get a value over here.

21
00:00:51,980 --> 00:00:53,060
So we have one over here.

22
00:00:53,330 --> 00:00:55,100
Now let's say we push one more value.

23
00:00:55,100 --> 00:00:56,330
So we have two over here.

24
00:00:56,330 --> 00:00:59,300
And let's say we have another value pushed to the queue.

25
00:00:59,300 --> 00:01:01,700
So we add three also to the in stack.

26
00:01:01,700 --> 00:01:06,110
Now we will use the out stack when we want to pop or peek.

27
00:01:06,170 --> 00:01:06,500
All right.

28
00:01:06,500 --> 00:01:08,510
So let's try to understand how we do this.

29
00:01:08,510 --> 00:01:15,260
Now we need two stacks because if we want to pop we cannot just pop from the end of the in stack and

30
00:01:15,260 --> 00:01:16,040
return this right.

31
00:01:16,040 --> 00:01:20,330
We cannot give this three because then it would not be Fifo or first in, first out.

32
00:01:20,330 --> 00:01:24,260
The first element into the in stack or the queue in this case was one.

33
00:01:24,260 --> 00:01:30,290
So when we pop, we have to return the first element one itself, because it has to be a Fifo data structure.

34
00:01:30,290 --> 00:01:31,970
So let's see how we can do this.

35
00:01:31,970 --> 00:01:34,160
So first we take a look at pop.

36
00:01:34,160 --> 00:01:35,120
Pop over here.

37
00:01:35,120 --> 00:01:37,340
And peek is going to be just similar to pop.

38
00:01:37,340 --> 00:01:37,760
All right.

39
00:01:37,760 --> 00:01:43,250
So what we will do is first we will check is the out stack empty when pop is called.

40
00:01:43,250 --> 00:01:46,130
So over here we see that the out stack is empty.

41
00:01:46,130 --> 00:01:52,370
So what we do is we are going to pop every element from the in stack and push it to our out stack.

42
00:01:52,370 --> 00:01:54,890
So when we pop we take from the end of the in stack.

43
00:01:54,890 --> 00:01:57,860
So we're going to take this three or pop it out from the in stack.

44
00:01:57,860 --> 00:01:59,810
And we push it to our out stack.

45
00:01:59,810 --> 00:02:02,060
Again our in stack is not yet empty.

46
00:02:02,060 --> 00:02:04,400
So we pop again from the in stack.

47
00:02:04,400 --> 00:02:08,510
That is, we take this element over here and we push it to our out stack.

48
00:02:08,510 --> 00:02:10,490
Again, our in stack is not empty.

49
00:02:10,490 --> 00:02:13,670
So we are going to pop from the in stack, which is this element over here.

50
00:02:13,670 --> 00:02:16,100
And then we push it to our out stack.

51
00:02:16,100 --> 00:02:16,490
All right.

52
00:02:16,490 --> 00:02:19,430
So all these elements now are in our out stack.

53
00:02:19,430 --> 00:02:24,110
And now we can see that if we pop from the out stack we will get this element over here.

54
00:02:24,110 --> 00:02:25,820
And that's the correct element right.

55
00:02:25,820 --> 00:02:27,320
To follow the Fifo property.

56
00:02:27,320 --> 00:02:30,320
Because this was the element which was first inserted to the queue.

57
00:02:30,320 --> 00:02:34,790
So now we will just pop from the out stack and return this element over here.

58
00:02:34,790 --> 00:02:37,010
So this is how we will implement pop.

59
00:02:37,010 --> 00:02:39,650
Now let's say we again push some more values to it.

60
00:02:39,650 --> 00:02:43,040
So for example let's say we have just popped this value out.

61
00:02:43,040 --> 00:02:45,500
So this is removed from the out stack.

62
00:02:45,500 --> 00:02:49,310
Now let's say we are going to add four to the queue.

63
00:02:49,310 --> 00:02:51,440
So we are going to again push it to our in stack.

64
00:02:51,440 --> 00:02:53,360
And let's say we add five to the queue.

65
00:02:53,360 --> 00:02:56,750
So we have five, four, five and three and two in our queue.

66
00:02:56,750 --> 00:03:01,310
Now among these elements we know that two was the element that was first inserted.

67
00:03:01,310 --> 00:03:04,610
So if we are going to pop we should be getting back two right.

68
00:03:04,610 --> 00:03:06,650
So again let's say we call pop.

69
00:03:06,650 --> 00:03:09,290
Now we see that the out stack is not empty.

70
00:03:09,290 --> 00:03:10,400
So this is not empty.

71
00:03:10,400 --> 00:03:14,600
So all we are going to do is we're just going to pop from the out stack and run it.

72
00:03:14,600 --> 00:03:15,950
So this is going to be returned.

73
00:03:15,950 --> 00:03:17,510
Now let's say we pop again.

74
00:03:17,510 --> 00:03:19,700
So again we check is the out stack empty.

75
00:03:19,730 --> 00:03:20,660
No it's not empty.

76
00:03:20,660 --> 00:03:23,030
So we are just going to pop from the out stack.

77
00:03:23,030 --> 00:03:24,320
And we are giving back three.

78
00:03:24,320 --> 00:03:29,300
So you can see it's following the Fifo property because among three four and five three was inserted

79
00:03:29,300 --> 00:03:29,660
first.

80
00:03:29,660 --> 00:03:31,760
So that's the value that we will return.

81
00:03:31,760 --> 00:03:34,790
And we will just pop from the out stack and return it.

82
00:03:34,790 --> 00:03:36,710
Now let's say we again call pop.

83
00:03:36,710 --> 00:03:39,020
Now at this point this is again empty.

84
00:03:39,020 --> 00:03:44,180
So we are going to take the elements in the in stack and insert it to the out stack one at a time.

85
00:03:44,180 --> 00:03:48,290
So we pop from the in stack and we push it to the out stack again.

86
00:03:48,290 --> 00:03:51,050
We pop from the in stack and we push it to the out stack.

87
00:03:51,050 --> 00:03:55,100
And after every element from the in stack is removed because now you can see it's empty.

88
00:03:55,130 --> 00:03:58,970
We are just going to pop from the out stack, which will give the value four.

89
00:03:58,970 --> 00:04:04,700
So again you can see it's following the Fifo property because among four and five, four was inserted

90
00:04:04,700 --> 00:04:05,060
first.

91
00:04:05,060 --> 00:04:07,910
So we are going to return the element which was first returned.

92
00:04:07,910 --> 00:04:11,270
So this is how we will implement the pop function.

93
00:04:11,270 --> 00:04:11,840
All right.

94
00:04:12,320 --> 00:04:18,560
Now peak is going to be pretty much similar because we just need to return the last element in the out

95
00:04:18,560 --> 00:04:18,770
stack.

96
00:04:18,770 --> 00:04:22,430
We don't need to pop it, but we will just read that element and return it.

97
00:04:22,430 --> 00:04:23,840
So it's it's the same thing.

98
00:04:23,840 --> 00:04:27,470
Let's say we we add one and two to our stack in stack.

99
00:04:27,470 --> 00:04:29,960
We push it and then let's say we are calling peak.

100
00:04:29,960 --> 00:04:32,420
So first we will check is the out stack empty?

101
00:04:32,420 --> 00:04:38,270
If it is empty, we will pop from the in stack and push it to the out stack till the in stack becomes

102
00:04:38,270 --> 00:04:38,690
empty.

103
00:04:38,690 --> 00:04:40,280
So two is inserted again.

104
00:04:40,280 --> 00:04:41,690
This is not empty the in stack.

105
00:04:41,690 --> 00:04:44,120
So we pop and we are pushing it to the out stack.

106
00:04:44,120 --> 00:04:45,860
So we have two and one in the out stack.

107
00:04:45,860 --> 00:04:46,310
Now.

108
00:04:46,310 --> 00:04:49,160
Now when again we have called peak right.

109
00:04:49,160 --> 00:04:51,560
So we are just going to return the last element over here.

110
00:04:51,560 --> 00:04:54,020
The length of the out stack is three two at this point.

111
00:04:54,020 --> 00:04:54,290
Right.

112
00:04:54,290 --> 00:04:59,240
So we are going to return the element at index two minus one which is equal to one.

113
00:04:59,240 --> 00:05:00,050
So this is index.

114
00:05:00,170 --> 00:05:01,220
You know this is index one.

115
00:05:01,220 --> 00:05:04,610
So we will just return the element at index one which is one.

116
00:05:04,610 --> 00:05:07,940
So you can see that Pop and Peek operate in a similar manner.

117
00:05:07,940 --> 00:05:08,330
All right.

118
00:05:08,330 --> 00:05:11,450
So we have covered these three operations of instance methods.

119
00:05:11,450 --> 00:05:15,170
Now let's take a look at the last instance method which is empty.

120
00:05:15,290 --> 00:05:19,700
Now it's mentioned that if the queue is empty this should return true.

121
00:05:19,700 --> 00:05:21,620
Otherwise this should return false.

122
00:05:21,620 --> 00:05:27,230
So we can see that the elements in the queue will either be in the in stack or the out stack.

123
00:05:27,230 --> 00:05:27,500
Right.

124
00:05:27,500 --> 00:05:29,030
So we have seen push and pop.

125
00:05:29,030 --> 00:05:31,520
So initially when we push we are pushing to the in stack.

126
00:05:31,520 --> 00:05:35,990
And then when we are popping we are taking the elements from the in stack, putting to the out stack

127
00:05:35,990 --> 00:05:37,520
and then popping from the out stack.

128
00:05:37,520 --> 00:05:37,790
Right.

129
00:05:37,790 --> 00:05:39,350
So you can see any element.

130
00:05:39,350 --> 00:05:44,510
If it is there in the queue, it can be either in the in stack or in the out stack.

131
00:05:44,510 --> 00:05:51,140
So if the queue is empty, all we need to check is if both the in stack and the out stack is empty.

132
00:05:51,140 --> 00:05:56,390
So if both of them are empty, or if both of them are of are of length zero, then we will just return

133
00:05:56,390 --> 00:05:56,870
true.

134
00:05:56,870 --> 00:05:59,000
Otherwise we will just return false.

135
00:05:59,000 --> 00:06:00,440
So this is how we will return.

136
00:06:00,530 --> 00:06:02,540
Implement the empty function over here.

137
00:06:02,540 --> 00:06:03,080
All right.

138
00:06:03,080 --> 00:06:06,650
So we have discussed how we can implement these four functions.

139
00:06:06,650 --> 00:06:10,220
All right now let's take a look at the complexity analysis of the solution.

140
00:06:10,220 --> 00:06:15,950
Now pushing is just a constant time operation because we are just inserting the value to the in stack

141
00:06:15,950 --> 00:06:22,220
right now when it comes to popping or peaking, it's going to be O of one time complexity amortized.

142
00:06:22,250 --> 00:06:23,510
Now again why is that?

143
00:06:23,510 --> 00:06:28,460
So if you are doing N operations, the time complexity is going to be O of N.

144
00:06:28,460 --> 00:06:33,470
And then because we have done n operations, we can write o of n as n into o of one.

145
00:06:33,470 --> 00:06:37,040
So on an average it's going to be an O of one operation.

146
00:06:37,040 --> 00:06:38,540
So this is for n operations right.

147
00:06:38,540 --> 00:06:40,070
So these two can cancel out.

148
00:06:40,070 --> 00:06:46,460
So on an average it's going to be an O of one operation peaking and popping uh peaking and popping from

149
00:06:46,460 --> 00:06:48,260
the um the queue.

150
00:06:48,260 --> 00:06:48,770
All right.

151
00:06:48,770 --> 00:06:49,760
Now again why is that.

152
00:06:49,760 --> 00:06:50,720
So we have discussed that.

153
00:06:50,720 --> 00:06:53,750
Let's say we have inserted the values one, two and three.

154
00:06:53,780 --> 00:06:57,650
Now let's say we are doing three over here we have n operations right.

155
00:06:57,650 --> 00:06:58,880
Let n be equal to three.

156
00:06:58,880 --> 00:07:01,040
Let's say we are doing three pops.

157
00:07:01,070 --> 00:07:01,580
All right.

158
00:07:01,580 --> 00:07:03,500
So we are popping three times.

159
00:07:04,360 --> 00:07:04,990
Now.

160
00:07:04,990 --> 00:07:09,910
First, when we are popping, we have to do O of N operations because we have to take this three.

161
00:07:09,910 --> 00:07:10,660
Put it over here.

162
00:07:10,660 --> 00:07:11,350
Take this two.

163
00:07:11,350 --> 00:07:13,030
Put it over here and take this one.

164
00:07:13,030 --> 00:07:16,210
Put it over here so you can see one time it's taking O of n.

165
00:07:16,210 --> 00:07:21,640
But then in all the other instances we're just taking the last element from the out stack array over

166
00:07:21,640 --> 00:07:23,380
here, which is a constant time operation.

167
00:07:23,380 --> 00:07:23,620
Right.

168
00:07:23,620 --> 00:07:28,150
So in the second and third times it's just going to be an O of one operation.

169
00:07:28,150 --> 00:07:32,320
So net it's an O of n operation or O of three operation.

170
00:07:32,320 --> 00:07:35,560
I'm just writing it o of n as, as a general manner.

171
00:07:35,560 --> 00:07:37,780
So for n operations it's o of n.

172
00:07:37,780 --> 00:07:44,380
So that's why we can say the time complexity is O of one amortized or on average.

173
00:07:44,680 --> 00:07:45,790
Now let's proceed.

174
00:07:45,790 --> 00:07:48,640
What about the empty function over here for this.

175
00:07:48,640 --> 00:07:51,340
Also we just need to check if the two stacks are empty.

176
00:07:51,340 --> 00:07:52,090
That's it right.

177
00:07:52,090 --> 00:07:54,760
And if both of them are empty we return true.

178
00:07:54,760 --> 00:07:56,110
Otherwise we return false.

179
00:07:56,110 --> 00:08:01,630
So you can see the empty instance method over here is also a constant time operation.

180
00:08:01,630 --> 00:08:02,140
All right.

181
00:08:02,170 --> 00:08:04,270
Now what about the space complexity.

182
00:08:04,270 --> 00:08:10,690
The space complexity of this is going to be O of N, because we are making use of these two stacks to

183
00:08:10,690 --> 00:08:11,860
implement our queue.

184
00:08:11,860 --> 00:08:16,570
And if the queue has n elements, the n elements will either be over here or here.

185
00:08:16,570 --> 00:08:16,840
Right.

186
00:08:16,840 --> 00:08:18,940
So together we'll have n elements.

187
00:08:18,940 --> 00:08:24,400
So that's why we can say that the space complexity, which is because of the because we are using the

188
00:08:24,400 --> 00:08:27,340
two stacks, is going to be of the order of n.