1
00:00:00,690 --> 00:00:01,620
Welcome back.

2
00:00:01,620 --> 00:00:07,050
Let's now go ahead and code the solution, which we discussed in the previous video to implement a queue

3
00:00:07,080 --> 00:00:07,860
with stacks.

4
00:00:07,860 --> 00:00:08,250
Right.

5
00:00:08,250 --> 00:00:11,970
So for this we will write our class and let's call it My Queue.

6
00:00:12,890 --> 00:00:15,380
And over here we have the constructor.

7
00:00:15,740 --> 00:00:20,300
We don't pass anything to it and we're just going to initialize two empty stacks.

8
00:00:20,300 --> 00:00:22,700
So let's call one stack in stack.

9
00:00:23,720 --> 00:00:25,760
And the second stack can be called out.

10
00:00:25,760 --> 00:00:26,420
Stack.

11
00:00:28,140 --> 00:00:29,610
So these are just empty over here.

12
00:00:29,610 --> 00:00:32,100
And we are implementing a stack as an array over here.

13
00:00:32,490 --> 00:00:34,860
Now let's go ahead and write the instance methods.

14
00:00:34,860 --> 00:00:38,670
So we need an instance method to push a value to the queue.

15
00:00:39,300 --> 00:00:43,110
And then we need a method to pop from the queue.

16
00:00:43,110 --> 00:00:45,750
And then we need the peek function.

17
00:00:45,750 --> 00:00:47,340
And finally the empty function.

18
00:00:47,340 --> 00:00:50,310
So these are the four functions mentioned in the question.

19
00:00:50,310 --> 00:00:53,130
So let's get started with the push function over here.

20
00:00:53,130 --> 00:00:55,770
So we just need to push something to our queue.

21
00:00:55,770 --> 00:00:59,940
So we are going to push the value which is given to us to the in stack.

22
00:00:59,940 --> 00:01:00,210
All right.

23
00:01:00,210 --> 00:01:02,670
So that's just a constant time operation.

24
00:01:02,670 --> 00:01:08,610
So we can say in this dot in stack dot push and we are passing the value.

25
00:01:08,610 --> 00:01:09,360
So that's it.

26
00:01:09,360 --> 00:01:12,870
So this value over here will be inserted to the in stack.

27
00:01:13,430 --> 00:01:16,100
So that's about pushing a value to the queue.

28
00:01:16,130 --> 00:01:18,830
Now let's go ahead and write the pop function over here.

29
00:01:18,860 --> 00:01:19,910
Now over here.

30
00:01:19,910 --> 00:01:23,540
First we have to check if the out stack is empty.

31
00:01:23,570 --> 00:01:28,880
If the out stack is empty, as we discussed in the previous video, we have to take the elements from

32
00:01:28,880 --> 00:01:31,670
the in stack one at a time by popping from it.

33
00:01:31,670 --> 00:01:36,830
And then we will insert it to our out stack, and then we will pop from the end of the out stack.

34
00:01:36,830 --> 00:01:40,400
So this is to ensure the Fifo property because this is a queue.

35
00:01:40,400 --> 00:01:42,560
So let's go ahead and test this.

36
00:01:42,560 --> 00:01:45,260
So check first whether the out stack is empty.

37
00:01:45,260 --> 00:01:50,390
So if not this dot out stack dot length.

38
00:01:51,640 --> 00:01:54,520
So we know that zero is falsy in JavaScript.

39
00:01:54,520 --> 00:01:58,540
So if the length over here is equal to zero, then that's falsy.

40
00:01:58,540 --> 00:01:59,860
And then we have a nought over here.

41
00:01:59,860 --> 00:02:04,330
So that means if the length is zero this will become truthy.

42
00:02:04,330 --> 00:02:06,670
And we will come inside this if condition.

43
00:02:06,670 --> 00:02:10,570
And then we will just pop from the stack and push to the outer stack.

44
00:02:10,570 --> 00:02:11,470
So let's go ahead.

45
00:02:11,470 --> 00:02:12,880
For this we will use a while loop.

46
00:02:12,880 --> 00:02:16,180
So while this dot in stack.

47
00:02:17,370 --> 00:02:18,510
Dot length.

48
00:02:19,510 --> 00:02:22,570
That means as long as the length is not equal to zero.

49
00:02:22,660 --> 00:02:26,770
Now we're just going to say this dot out stack dot push.

50
00:02:27,280 --> 00:02:32,560
And the value that we want to push to the out stack is the value that we are going to pop from the in

51
00:02:32,560 --> 00:02:32,980
stack.

52
00:02:32,980 --> 00:02:36,850
So over here we can have this dot in stack dot pop.

53
00:02:38,710 --> 00:02:39,100
All right.

54
00:02:39,100 --> 00:02:42,730
So we are popping from the in stack and taking a value.

55
00:02:42,730 --> 00:02:45,340
And that value is pushed to the outside.

56
00:02:45,340 --> 00:02:47,020
So that's what is happening over here.

57
00:02:47,020 --> 00:02:53,530
Now once we are out of this we just need to return the value that we get when we pop from the out stack.

58
00:02:53,530 --> 00:02:57,610
So we can say return this dot out, stack dot pop.

59
00:02:58,470 --> 00:02:58,740
All right.

60
00:02:58,740 --> 00:03:02,520
So that that will give us the, uh, element which was inserted first.

61
00:03:02,520 --> 00:03:08,250
So again, we are doing this so that we maintain the Fifo property and we are implementing it in this

62
00:03:08,250 --> 00:03:13,830
manner so that we get an amortized constant time operation when we pop from the queue.

63
00:03:13,830 --> 00:03:14,370
All right.

64
00:03:14,400 --> 00:03:16,560
Now let's go ahead and write the remaining two functions.

65
00:03:16,560 --> 00:03:21,360
And then we will test the code that we have written and walk through the code to understand it in a

66
00:03:21,360 --> 00:03:21,900
better manner.

67
00:03:21,900 --> 00:03:22,950
So let's proceed.

68
00:03:22,950 --> 00:03:23,700
Now peak.

69
00:03:23,700 --> 00:03:29,040
In the case of the peak function, we don't want to pop from the queue, but we just want to see what

70
00:03:29,040 --> 00:03:32,130
is the element which is there in the queue which was inserted first.

71
00:03:32,130 --> 00:03:32,430
Right.

72
00:03:32,430 --> 00:03:35,310
So again it's going to be pretty much similar to pop.

73
00:03:35,310 --> 00:03:39,180
So let's just copy this over here and we will modify this.

74
00:03:39,180 --> 00:03:42,990
So in the case of peak also we will check if the out stack is empty.

75
00:03:42,990 --> 00:03:47,940
If it is empty we will take everything from the in stack one at a time by popping from it.

76
00:03:47,940 --> 00:03:50,280
And then we push that value to the out stack.

77
00:03:50,280 --> 00:03:55,950
Now once this is done, we just want to return the last element without popping it over.

78
00:03:55,950 --> 00:03:58,050
Here we can return this dot out stack.

79
00:03:58,050 --> 00:03:59,700
And then this is an array.

80
00:03:59,700 --> 00:04:01,590
We have implemented the stack as an array.

81
00:04:01,590 --> 00:04:04,350
So we just need to pass the index over here.

82
00:04:04,350 --> 00:04:09,030
So we can have this dot out stack dot length minus one.

83
00:04:09,030 --> 00:04:11,730
So this is the last index in the out stack array.

84
00:04:11,730 --> 00:04:13,620
So we are going to pass this index.

85
00:04:14,130 --> 00:04:17,160
This will give us the last element in the out stack.

86
00:04:17,160 --> 00:04:19,890
And that's the element which was first inserted right.

87
00:04:19,890 --> 00:04:22,620
So this is how we can implement the Peek method.

88
00:04:22,620 --> 00:04:25,080
And then finally we have the empty method over here.

89
00:04:25,080 --> 00:04:30,090
Now we know that elements in the queue are either stored in one of these two stacks.

90
00:04:30,090 --> 00:04:30,480
Right.

91
00:04:30,480 --> 00:04:36,570
So if both these stacks are empty then we can be sure that the queue is empty.

92
00:04:36,570 --> 00:04:38,550
So that is all that we need to check over here.

93
00:04:38,550 --> 00:04:40,410
So let's have two variables.

94
00:04:40,410 --> 00:04:42,900
Let's call it in stack length.

95
00:04:44,980 --> 00:04:47,170
Which is the length of the in stack.

96
00:04:47,170 --> 00:04:50,830
So this is equal to this dot in stack dot length.

97
00:04:51,310 --> 00:04:53,710
And then let's have out stack length.

98
00:04:56,110 --> 00:04:59,830
So this is equal to this dot out stack dot length.

99
00:05:00,070 --> 00:05:04,990
So if both of these are zero then we have to return true.

100
00:05:04,990 --> 00:05:05,200
Right.

101
00:05:05,200 --> 00:05:07,270
So if both of them are zero if both.

102
00:05:08,480 --> 00:05:11,660
R0, then we need to return true.

103
00:05:14,210 --> 00:05:19,610
So for this we can say return not in stack length.

104
00:05:21,690 --> 00:05:22,500
And.

105
00:05:23,240 --> 00:05:24,110
Not out.

106
00:05:24,110 --> 00:05:24,980
Stack length.

107
00:05:25,780 --> 00:05:29,050
But what happens over here if the stack length is equal to zero?

108
00:05:29,080 --> 00:05:30,940
This will be not of zero.

109
00:05:30,940 --> 00:05:35,590
So that would be truthy because we know zero is falsy so not of zero will be truthy.

110
00:05:35,590 --> 00:05:37,060
And then over here also right.

111
00:05:37,060 --> 00:05:38,740
If it is zero it will be truthy.

112
00:05:38,740 --> 00:05:42,010
So if both of these are true because we have an end condition over here.

113
00:05:42,100 --> 00:05:45,430
So if this is truthy and this is truthy we return true.

114
00:05:45,430 --> 00:05:48,700
And that would be the case when both the lengths are equal to zero.

115
00:05:48,700 --> 00:05:49,870
So that is it.

116
00:05:50,470 --> 00:05:53,320
We have completed writing the four instance methods.

117
00:05:53,320 --> 00:05:56,200
And this is implementing a queue with stacks.

118
00:05:56,200 --> 00:05:58,000
Now let's go ahead and test our code.

119
00:05:58,000 --> 00:05:59,350
So for this let's have an object.

120
00:05:59,350 --> 00:06:04,030
So I can say const queue is equal to new my queue.

121
00:06:05,240 --> 00:06:07,550
Now let us run our code.

122
00:06:08,730 --> 00:06:09,150
All right.

123
00:06:09,150 --> 00:06:11,340
So we have a queue object.

124
00:06:11,370 --> 00:06:14,130
Now let's define let's push something to our queue.

125
00:06:14,130 --> 00:06:16,890
So for example we can say queue dot push.

126
00:06:18,010 --> 00:06:18,850
One.

127
00:06:21,940 --> 00:06:24,580
And let me push another value, which is two.

128
00:06:24,610 --> 00:06:26,710
Let me push one more value, which is three.

129
00:06:27,220 --> 00:06:33,340
Now if I pop from the q so q dot pop, I should get back the element which was first inserted, which

130
00:06:33,340 --> 00:06:34,090
was one.

131
00:06:34,090 --> 00:06:34,420
Right.

132
00:06:34,420 --> 00:06:35,320
So let's do that.

133
00:06:35,320 --> 00:06:38,950
So when we do this you can see we get one, which is correct.

134
00:06:38,950 --> 00:06:40,960
If I pop again I should get two.

135
00:06:40,990 --> 00:06:42,580
If I pop again I should get three.

136
00:06:42,580 --> 00:06:45,970
Now if I pop again I don't get anything because the queue is empty now.

137
00:06:45,970 --> 00:06:48,160
Now push and pop is working.

138
00:06:48,160 --> 00:06:49,480
Now what about empty?

139
00:06:49,480 --> 00:06:51,070
So let's try Q dot empty.

140
00:06:52,850 --> 00:06:55,550
Now we know it's empty because we have popped everything from it.

141
00:06:55,550 --> 00:06:57,740
And yes, the queue is actually empty.

142
00:06:57,770 --> 00:06:59,810
Now again, let's push something to it.

143
00:06:59,810 --> 00:07:01,250
So Q dot, push one.

144
00:07:03,540 --> 00:07:05,910
Now if I call q dot empty.

145
00:07:05,940 --> 00:07:06,930
We are getting false.

146
00:07:06,930 --> 00:07:08,940
So empty is also working.

147
00:07:08,940 --> 00:07:10,800
Now let's again push some more values.

148
00:07:10,800 --> 00:07:11,820
So q dot push.

149
00:07:11,820 --> 00:07:14,520
Um let's have two.

150
00:07:16,440 --> 00:07:19,200
And let's push three to the cube.

151
00:07:19,350 --> 00:07:25,770
Now, if we do q dot peak, we should get back one right, which is the element which will would be

152
00:07:25,770 --> 00:07:26,910
returned if we pop.

153
00:07:26,910 --> 00:07:30,390
So that's the element which was first inserted which is there in our queue.

154
00:07:30,390 --> 00:07:31,560
So this is also working.

155
00:07:31,560 --> 00:07:33,270
So yes our code is working.

156
00:07:33,270 --> 00:07:36,780
Now let's take a look at the code that we have written and just walk through it.

157
00:07:36,780 --> 00:07:38,700
So for this let me grab a pen.

158
00:07:39,180 --> 00:07:39,660
All right.

159
00:07:39,660 --> 00:07:41,850
So over here we have these two stacks.

160
00:07:41,850 --> 00:07:43,260
So this is the in stack.

161
00:07:45,860 --> 00:07:48,500
And it's an empty array at this moment.

162
00:07:48,500 --> 00:07:50,480
And then we have the out stack.

163
00:07:52,450 --> 00:07:53,590
So this is also empty.

164
00:07:53,620 --> 00:07:58,840
So the way we are implementing the push function over here is that when we are calling this with a value,

165
00:07:58,840 --> 00:08:00,070
we're just pushing it to our stack.

166
00:08:00,070 --> 00:08:04,840
So when we inserted one, two and three what happened is when we insert one it comes over here.

167
00:08:04,840 --> 00:08:07,270
Then when we insert two we are adding at the end.

168
00:08:07,270 --> 00:08:08,470
So we get two over here.

169
00:08:08,470 --> 00:08:11,110
Then when we insert three it comes over here.

170
00:08:11,110 --> 00:08:13,360
Now let's take a look at the pop function.

171
00:08:13,540 --> 00:08:14,800
Now in the.

172
00:08:15,800 --> 00:08:16,580
Bob function.

173
00:08:16,580 --> 00:08:20,060
First, we are going to check if the out stack is empty.

174
00:08:20,060 --> 00:08:22,460
So at this point we see that it is empty.

175
00:08:22,460 --> 00:08:27,020
So what we are going to do is we are going to pop from the in stack.

176
00:08:27,020 --> 00:08:29,180
So this would pop this element right.

177
00:08:29,180 --> 00:08:31,730
So pop comes is is taking from the end.

178
00:08:31,730 --> 00:08:35,450
So we take this element and then we are going to push it to our out stack.

179
00:08:35,450 --> 00:08:36,740
So we get three over here.

180
00:08:36,740 --> 00:08:41,090
Then this will keep happening as long as there is something in the in stack.

181
00:08:41,090 --> 00:08:41,300
Right.

182
00:08:41,300 --> 00:08:44,720
As long as the length of the in stack is not equal to zero.

183
00:08:44,720 --> 00:08:48,050
So again we pop and then we are pushing it to our out stack.

184
00:08:48,050 --> 00:08:50,780
And we pop again and we push it to our out stack.

185
00:08:50,780 --> 00:08:55,010
Now once this is done we are going to return this dot out dot pop.

186
00:08:55,010 --> 00:08:58,760
So when we pop from here, you can see we are getting this element which is one.

187
00:08:58,760 --> 00:08:59,750
And that's true right.

188
00:08:59,750 --> 00:09:01,820
So this was the element which was inserted first.

189
00:09:01,820 --> 00:09:05,330
So you can see it's following the Fifo property first in first out.

190
00:09:05,360 --> 00:09:08,360
Now let's say we add again elements to it.

191
00:09:08,360 --> 00:09:10,100
So let's say we add the element four.

192
00:09:10,100 --> 00:09:11,810
So again it would be added over here.

193
00:09:11,810 --> 00:09:13,160
And then we add five.

194
00:09:13,160 --> 00:09:14,480
And then again we pop.

195
00:09:14,480 --> 00:09:16,190
So we have just popped this earlier right.

196
00:09:16,190 --> 00:09:19,820
So again when we pop we are going to get two again over here.

197
00:09:19,820 --> 00:09:22,310
When we come we see that the out stack is not empty.

198
00:09:22,310 --> 00:09:26,630
So directly we are going to come over here and we will just pop from the out stack and return this.

199
00:09:26,630 --> 00:09:27,860
So this would be returned.

200
00:09:27,860 --> 00:09:31,460
So you can see among two, four among two.

201
00:09:31,460 --> 00:09:32,600
And then what are the values.

202
00:09:32,600 --> 00:09:34,910
Two is there and one was popped.

203
00:09:34,910 --> 00:09:38,420
So we have three among three, two and four and five.

204
00:09:38,420 --> 00:09:40,940
Among these two is the one that was inserted latest.

205
00:09:40,940 --> 00:09:41,210
Right.

206
00:09:41,210 --> 00:09:42,800
So when we pop we are getting two.

207
00:09:42,800 --> 00:09:43,490
And that is correct.

208
00:09:43,490 --> 00:09:45,380
So it's following the Fifo property.

209
00:09:45,380 --> 00:09:47,240
So if we pop again we will get three.

210
00:09:47,240 --> 00:09:51,500
Now if we want to pop again when we come over here all these were already popped out.

211
00:09:51,500 --> 00:09:53,660
So we will see that the out stack is empty.

212
00:09:53,660 --> 00:09:58,700
So again we come inside over here and we are going to pop from here and we will insert it to our out

213
00:09:58,700 --> 00:09:58,910
stack.

214
00:09:58,910 --> 00:10:00,050
So this is our out stack.

215
00:10:00,050 --> 00:10:01,580
So this would be inserted over here.

216
00:10:01,580 --> 00:10:04,190
And then again we pop this one this four over here.

217
00:10:04,190 --> 00:10:06,110
And it will be inserted in our out stack.

218
00:10:06,110 --> 00:10:10,220
And then we come over here and we are going to pop from the out stack and return it.

219
00:10:10,220 --> 00:10:12,020
So this would be returned which is correct.

220
00:10:12,020 --> 00:10:12,230
Right.

221
00:10:12,230 --> 00:10:15,260
Among four and five we can see four was inserted first.

222
00:10:15,260 --> 00:10:17,510
So again it's following the Fifo property.

223
00:10:17,510 --> 00:10:20,060
So this is how the Pop function over here works.

224
00:10:20,090 --> 00:10:22,340
Now let's take a look at the peek function.

225
00:10:22,340 --> 00:10:24,440
Now the peek is also pretty much similar.

226
00:10:24,440 --> 00:10:26,540
Again let's say we have our in stack.

227
00:10:26,540 --> 00:10:27,710
So this is our in stack.

228
00:10:27,710 --> 00:10:30,500
And the values 123 were inserted.

229
00:10:30,500 --> 00:10:33,440
And then let's say we are peeking and the out stack is empty.

230
00:10:33,440 --> 00:10:36,440
At this point over here we will see that the out stack is empty.

231
00:10:36,440 --> 00:10:42,920
So we will take each element from the in stack and pop it and insert it to our out stack.

232
00:10:42,920 --> 00:10:43,940
So that's happening over here.

233
00:10:43,940 --> 00:10:44,990
We are popping over here.

234
00:10:44,990 --> 00:10:47,060
And then we are pushing to our out stack.

235
00:10:47,730 --> 00:10:48,060
Again.

236
00:10:48,060 --> 00:10:48,840
This happens.

237
00:10:48,840 --> 00:10:52,800
We pop, we push it to our out stack, we pop and we push it to our out stack.

238
00:10:52,800 --> 00:10:57,630
At this point, this is going to be falsy because the length has become zero, and zero is falsy in

239
00:10:57,630 --> 00:10:58,200
JavaScript.

240
00:10:58,200 --> 00:11:05,340
So we come out of this and then we are going to return the element in the out stack array at index of

241
00:11:05,340 --> 00:11:06,930
the length of the out stack minus one.

242
00:11:06,930 --> 00:11:08,340
So the length over here is three.

243
00:11:08,340 --> 00:11:10,200
So three minus one gives us two.

244
00:11:10,200 --> 00:11:11,760
And we know that this is index zero.

245
00:11:11,760 --> 00:11:13,230
This is one and this is two.

246
00:11:13,260 --> 00:11:16,980
So we are going to return the element at index two which is one.

247
00:11:16,980 --> 00:11:21,600
So we can see among one two and three this was the element that was inserted first.

248
00:11:21,600 --> 00:11:25,530
So yes this is the element that would be coming out of the queue first.

249
00:11:25,530 --> 00:11:28,110
So our peak function is working in this manner.

250
00:11:28,110 --> 00:11:31,530
And then finally we have the empty function over here.

251
00:11:31,530 --> 00:11:36,870
Now we can notice over here that elements are either stored in the in stack or the out stack.

252
00:11:36,870 --> 00:11:37,290
Right.

253
00:11:37,290 --> 00:11:39,090
So it would be either here or here.

254
00:11:39,090 --> 00:11:43,800
Now it would the the queue is empty only when both of these together are empty.

255
00:11:43,830 --> 00:11:44,130
Right.

256
00:11:44,130 --> 00:11:46,560
So over here we are getting the length of the in stack.

257
00:11:46,560 --> 00:11:48,960
And over here we are getting the length of the out stack.

258
00:11:48,960 --> 00:11:54,870
So this over here this return statement will be true only if these two lengths are equal to zero.

259
00:11:54,870 --> 00:11:56,940
So if this is zero and this is zero.

260
00:11:56,940 --> 00:11:58,500
So over here we have the naught.

261
00:11:58,500 --> 00:11:59,640
And over here also we have not.

262
00:11:59,640 --> 00:12:01,830
So not zero and and not zero.

263
00:12:01,830 --> 00:12:03,420
So zero is falsy.

264
00:12:03,420 --> 00:12:04,110
So not zero.

265
00:12:04,110 --> 00:12:05,280
This would become truthy.

266
00:12:05,280 --> 00:12:06,780
And this also is truthy.

267
00:12:06,780 --> 00:12:09,690
So when both of them are truthy we will return true.

268
00:12:09,690 --> 00:12:11,970
So that means there is nothing in both these stacks.

269
00:12:11,970 --> 00:12:13,680
So this is how the function works.

270
00:12:13,680 --> 00:12:17,190
Now let's take a quick look at the time and space complexity over here.

271
00:12:17,280 --> 00:12:20,040
Now first let's take a look at the time complexity.

272
00:12:20,070 --> 00:12:21,930
Now this push Val over here.

273
00:12:21,930 --> 00:12:24,090
This is just a constant time operation right.

274
00:12:24,090 --> 00:12:27,450
We're just pushing to the array over here which is the in stack array.

275
00:12:27,450 --> 00:12:28,980
So this is constant time.

276
00:12:28,980 --> 00:12:30,330
Now what about pop.

277
00:12:30,330 --> 00:12:31,770
Now pop and peek.

278
00:12:31,770 --> 00:12:34,380
Both of them are going to have the same time complexity.

279
00:12:34,380 --> 00:12:38,340
Now these which is pop and peep peek.

280
00:12:38,340 --> 00:12:41,670
They are going to have an amortized constant time operation.

281
00:12:41,670 --> 00:12:41,970
Right.

282
00:12:41,970 --> 00:12:47,250
So it's going to be O of one time complexity amortized or on average.

283
00:12:47,700 --> 00:12:48,300
Now why is that.

284
00:12:48,300 --> 00:12:50,490
So now let's take the example.

285
00:12:50,490 --> 00:12:52,620
Let's say we have 123 over here.

286
00:12:53,100 --> 00:12:54,900
And the out stack is empty.

287
00:12:55,260 --> 00:12:59,010
Now when we are peeking for the when we are let's say let's just take pop.

288
00:12:59,010 --> 00:13:02,580
So when we are popping the for the first time, we will see this is empty.

289
00:13:02,580 --> 00:13:07,800
So we will do N operations to get everything out from here and into our out stack.

290
00:13:07,800 --> 00:13:08,130
Right?

291
00:13:08,130 --> 00:13:09,870
So this is N operations.

292
00:13:10,230 --> 00:13:13,500
But then when we are and then we pop this one.

293
00:13:13,500 --> 00:13:14,850
So we have done N operations.

294
00:13:14,850 --> 00:13:19,980
But then when we pop the next time it's just a constant time operation because we can return this.

295
00:13:19,980 --> 00:13:22,200
And again if we pop we are just going to return this.

296
00:13:22,200 --> 00:13:27,750
So you can see when we are doing three operations, when we pop three times, we are going to do O of

297
00:13:27,750 --> 00:13:29,250
N operations, right?

298
00:13:29,250 --> 00:13:34,500
Because this happened because the first time this was empty and we had to do N operations, that is

299
00:13:34,500 --> 00:13:37,770
going through every element in the in stack and getting it to the out stack.

300
00:13:37,770 --> 00:13:43,620
So on average we can say it's going to take O of one time because this over here O of three or O of

301
00:13:43,620 --> 00:13:45,690
n is for n operations.

302
00:13:45,690 --> 00:13:50,280
So again this this O of n can be written as n into o of one.

303
00:13:50,820 --> 00:13:52,800
And again we did n operations over here.

304
00:13:52,800 --> 00:13:58,770
So that's why we can say for one operation on average it's going to be an O of one time operation.

305
00:13:58,770 --> 00:14:04,920
Or we can say the time complexity of pop and peak is going to be O of one amortized.

306
00:14:05,370 --> 00:14:05,760
All right.

307
00:14:05,790 --> 00:14:09,870
Now let's also take a look at the last function over here which is empty.

308
00:14:09,900 --> 00:14:12,900
Now again over here we just need to check both lengths.

309
00:14:12,900 --> 00:14:14,880
So these are constant time operations.

310
00:14:14,880 --> 00:14:16,440
And then we just have to return this.

311
00:14:16,440 --> 00:14:20,220
So again this over here is going to be a constant time operation.

312
00:14:20,520 --> 00:14:22,680
Now what about the space complexity.

313
00:14:22,680 --> 00:14:24,510
Let's take a look at that also.

314
00:14:25,590 --> 00:14:29,250
Now over here we are implementing the queue using stacks.

315
00:14:29,250 --> 00:14:31,140
And you can see we are using two stacks.

316
00:14:31,140 --> 00:14:31,500
Right.

317
00:14:31,500 --> 00:14:36,630
And then if you are having n elements these n elements would be either in one of these two stacks.

318
00:14:36,630 --> 00:14:41,580
So that's why we can say that the space complexity is going to be of the order of n.