1
00:00:00,610 --> 00:00:01,630
Welcome back.

2
00:00:01,630 --> 00:00:07,300
Now, in the previous video, we have seen that we can implement a queue by using push and shift and

3
00:00:07,300 --> 00:00:07,960
with an array.

4
00:00:07,960 --> 00:00:09,910
So let's try to see that over here.

5
00:00:09,910 --> 00:00:16,240
Now let's take the console and let's say I have a queue and we can just say it's an array.

6
00:00:16,240 --> 00:00:16,540
All right.

7
00:00:16,540 --> 00:00:23,800
So it's going to be just uh const queue is equal to an empty array.

8
00:00:25,150 --> 00:00:25,570
All right.

9
00:00:25,600 --> 00:00:28,150
Now let's try to push something to it.

10
00:00:28,150 --> 00:00:31,210
So we have queue dot push.

11
00:00:31,210 --> 00:00:33,580
Let's say we push the value one to it.

12
00:00:34,030 --> 00:00:36,700
And now we're going to push the value two to it.

13
00:00:36,700 --> 00:00:38,860
And then let's push the value three to it.

14
00:00:40,330 --> 00:00:40,600
All right.

15
00:00:40,600 --> 00:00:42,640
Now our cue is having three elements.

16
00:00:42,640 --> 00:00:44,530
So let's take a look at it.

17
00:00:45,340 --> 00:00:46,990
So this is the array 123.

18
00:00:46,990 --> 00:00:50,260
And we know that the order is that first one came in.

19
00:00:50,260 --> 00:00:52,600
Then two came in and then three came in.

20
00:00:52,600 --> 00:00:57,100
Now we know that queue is a Fifo or first in first out data structure.

21
00:00:57,100 --> 00:00:59,680
So we should get one back first right.

22
00:00:59,680 --> 00:01:01,480
So for this we are going to use shift.

23
00:01:01,480 --> 00:01:03,670
So we can say queue dot shift.

24
00:01:07,550 --> 00:01:10,280
And you can see we get back one which came in first.

25
00:01:10,280 --> 00:01:10,640
Right.

26
00:01:10,640 --> 00:01:12,410
So if we again shift, we get back two.

27
00:01:12,410 --> 00:01:14,300
And if we again shift we get back three.

28
00:01:14,300 --> 00:01:15,800
So this is how a queue works right?

29
00:01:15,800 --> 00:01:21,800
So any time we stand in a queue to get a ticket, the person who came first is getting the ticket first

30
00:01:21,800 --> 00:01:23,840
and hence he or she comes out first.

31
00:01:23,840 --> 00:01:25,370
So this is how a queue works.

32
00:01:25,370 --> 00:01:32,690
Now again, the problem is that the shift operation over here on an array is going to be an O of n operation

33
00:01:32,990 --> 00:01:34,940
for with respect to time complexity.

34
00:01:34,940 --> 00:01:36,260
So that's not efficient right.

35
00:01:36,260 --> 00:01:39,860
So let's go ahead and implement our queue using a linked list.

36
00:01:39,860 --> 00:01:41,420
And this is going to be efficient.

37
00:01:41,420 --> 00:01:47,960
And we'll be able to add elements into our queue and take out the elements from the queue in constant

38
00:01:47,960 --> 00:01:48,950
time and space.

39
00:01:48,950 --> 00:01:51,980
So let's go ahead and implement our queue with the linked list.

40
00:01:52,460 --> 00:01:55,370
Now again we will need our uh node class.

41
00:01:55,370 --> 00:01:57,110
So we can say class node.

42
00:01:57,470 --> 00:01:59,810
And then we have our constructor over here.

43
00:02:01,790 --> 00:02:04,670
And we pass in the value when we call this.

44
00:02:05,090 --> 00:02:11,180
And we're going to say this dot value is equal to the value which is passed to it, and this dot next.

45
00:02:13,370 --> 00:02:14,690
Is equal to null.

46
00:02:15,630 --> 00:02:18,810
Now let's go ahead and write the Q class.

47
00:02:18,810 --> 00:02:20,190
So this is class Q.

48
00:02:20,190 --> 00:02:22,530
And we have a constructor over here as well.

49
00:02:22,530 --> 00:02:24,300
And we don't pass anything to it.

50
00:02:24,300 --> 00:02:27,600
And then over here we're going to say this dot first is null.

51
00:02:29,210 --> 00:02:31,040
And this dot last is null.

52
00:02:32,500 --> 00:02:39,400
And the size at this moment is equal to zero, so it's empty when we create an object with this class.

53
00:02:39,400 --> 00:02:39,880
All right.

54
00:02:39,910 --> 00:02:46,570
Now inside this we are going to add two instance methods to add and to take out elements from the queue.

55
00:02:46,570 --> 00:02:50,230
Now in the case of a queue addition is called in queuing.

56
00:02:50,230 --> 00:02:52,030
So we can say in queue.

57
00:02:53,070 --> 00:02:55,740
So this is going to be the function to add a value.

58
00:02:55,740 --> 00:02:57,810
So we have to pass the value to it.

59
00:02:57,960 --> 00:03:02,730
So I'm just having placeholders now and then to remove a value we call it DQ.

60
00:03:02,730 --> 00:03:05,730
In the case of a queue we have DQ over here.

61
00:03:06,300 --> 00:03:06,660
All right.

62
00:03:06,660 --> 00:03:09,660
So this should give back the element which was added first.

63
00:03:09,900 --> 00:03:16,200
Now in the case of a queue we are going to add at the end and remove from the beginning so that we can

64
00:03:16,200 --> 00:03:18,900
implement the queue as a Fifo data structure.

65
00:03:18,900 --> 00:03:19,860
First in first out.

66
00:03:19,860 --> 00:03:22,650
So let's go ahead and write these two instance methods.

67
00:03:22,650 --> 00:03:25,530
First let's write the in queue instance method.

68
00:03:25,530 --> 00:03:27,600
So we have a value passed to it.

69
00:03:27,600 --> 00:03:32,670
Now with this value we are going to create a node using the node class which we have written over here.

70
00:03:32,670 --> 00:03:37,590
So we can say const node is equal to new node.

71
00:03:37,590 --> 00:03:39,450
And then we pass the value to it.

72
00:03:39,840 --> 00:03:42,210
So we have a node made with this value.

73
00:03:42,210 --> 00:03:46,830
Now we are going to check is the singly linked list at this point empty.

74
00:03:46,830 --> 00:03:49,500
So if not this dot first.

75
00:03:49,740 --> 00:03:55,530
That means if it is null, if first is null and which means that the singly linked list is empty.

76
00:03:55,530 --> 00:03:59,850
In this case we are just going to say this dot first is the node which we just now created.

77
00:04:00,570 --> 00:04:04,680
And this node last is also going to be equal to the node itself.

78
00:04:05,160 --> 00:04:10,680
Now if this is not the case then we are going to say this dot last dot next.

79
00:04:10,680 --> 00:04:17,010
That is the previous last is going to point to the new node which we created because we are adding at

80
00:04:17,010 --> 00:04:17,400
the end.

81
00:04:17,400 --> 00:04:18,000
All right.

82
00:04:18,510 --> 00:04:20,610
And then we have to modify the last.

83
00:04:20,610 --> 00:04:24,240
So this dot last is going to be equal to node.

84
00:04:24,240 --> 00:04:28,560
So we are setting the new node as the last node in this singly linked list.

85
00:04:28,560 --> 00:04:32,070
Now because we have added a new node we have to increment the size.

86
00:04:32,070 --> 00:04:35,010
So we can say this dot size plus plus.

87
00:04:35,010 --> 00:04:38,820
And then let's say we just want to return the complete singly linked list.

88
00:04:38,820 --> 00:04:41,070
So that would be returned this.

89
00:04:41,070 --> 00:04:45,720
So this is how we can add a node at the end in the singly linked list.

90
00:04:45,720 --> 00:04:50,850
And you can see that this is pretty much similar to what we have done in the linked list video, where

91
00:04:50,850 --> 00:04:52,350
we designed our linked list.

92
00:04:52,350 --> 00:04:52,860
All right.

93
00:04:52,860 --> 00:04:55,860
Now let's go ahead and write the dequeue function also over here.

94
00:04:55,860 --> 00:04:57,930
And then we'll go ahead and test our code.

95
00:04:57,930 --> 00:05:03,900
Now if we dequeue we are going to remove from the beginning so that the Fifo property is followed.

96
00:05:03,900 --> 00:05:04,140
Right.

97
00:05:04,140 --> 00:05:07,410
We want to get out what was inserted first.

98
00:05:07,410 --> 00:05:13,290
Now when we call the dequeue function or the dequeue method, first we are going to check if the singly

99
00:05:13,290 --> 00:05:15,000
linked list is empty at this point.

100
00:05:15,000 --> 00:05:19,470
So if not this dot first, if there is nothing then we will just return null.

101
00:05:19,470 --> 00:05:19,890
All right.

102
00:05:19,890 --> 00:05:21,900
So we cannot dequeue anything.

103
00:05:21,900 --> 00:05:26,040
Now if this is not the case let's have a variable temp.

104
00:05:26,040 --> 00:05:28,590
And this is going to be equal to this dot first.

105
00:05:28,890 --> 00:05:32,760
And we are just storing this because we are going to remove the first element.

106
00:05:32,760 --> 00:05:35,550
And finally we will return back temp.

107
00:05:35,550 --> 00:05:37,860
So we are removing temp the first element.

108
00:05:37,860 --> 00:05:41,250
And we will return back the element which we just now removed.

109
00:05:41,250 --> 00:05:41,640
All right.

110
00:05:41,640 --> 00:05:43,470
So temp is equal to this dot first.

111
00:05:43,470 --> 00:05:49,860
Now let's go ahead and shift the first over here the first property to the next node.

112
00:05:49,860 --> 00:05:56,790
So we can say this dot first is equal to this dot first dot next.

113
00:05:57,300 --> 00:05:57,630
All right.

114
00:05:57,630 --> 00:06:00,780
So the next element the second element is made the first.

115
00:06:00,780 --> 00:06:03,120
And again we are tracking first and last over here.

116
00:06:03,120 --> 00:06:06,000
So this dot first is equal to this dot first dot next.

117
00:06:06,000 --> 00:06:09,000
So the second node now is made the first node.

118
00:06:09,000 --> 00:06:11,550
And in this way we have removed the first node.

119
00:06:11,550 --> 00:06:15,120
Now because we have removed one node we are going to decrement the size.

120
00:06:15,120 --> 00:06:18,180
So we can say this dot size minus minus.

121
00:06:19,330 --> 00:06:20,020
And that's it.

122
00:06:20,020 --> 00:06:20,350
All right.

123
00:06:20,380 --> 00:06:23,440
Now again, there is one more condition that we have to check over here.

124
00:06:23,440 --> 00:06:26,440
Let's say the singly linked list only had one node.

125
00:06:26,440 --> 00:06:29,590
So in this case we have modified the first two null.

126
00:06:29,590 --> 00:06:32,440
But we have not yet modified the last also.

127
00:06:32,440 --> 00:06:32,680
Right.

128
00:06:32,680 --> 00:06:37,390
So if it has only one node then we have to modify last also to null.

129
00:06:37,390 --> 00:06:38,800
So let's check that over here.

130
00:06:38,800 --> 00:06:43,360
So after decrementing the size let's check if the size is equal to zero.

131
00:06:43,360 --> 00:06:46,390
So if this dot size is equal to zero.

132
00:06:47,610 --> 00:06:50,670
That means that the singly linked list now is empty.

133
00:06:50,670 --> 00:06:54,390
So we can say this dot last is equal to null.

134
00:06:55,750 --> 00:06:56,500
And that's it.

135
00:06:56,500 --> 00:06:56,920
All right.

136
00:06:56,920 --> 00:07:00,940
So over here we are returning the node which we have just now removed.

137
00:07:00,940 --> 00:07:05,830
So this is how we have implemented our queue using a singly linked list.

138
00:07:05,830 --> 00:07:07,870
Now let's go ahead and test our code.

139
00:07:07,870 --> 00:07:09,730
So let's just have an object over here.

140
00:07:09,730 --> 00:07:14,500
So I can say const queue is equal to new queue.

141
00:07:14,500 --> 00:07:15,130
All right.

142
00:07:16,450 --> 00:07:18,220
Again so that you don't get confused.

143
00:07:18,220 --> 00:07:19,780
Let me just call this Q1.

144
00:07:19,780 --> 00:07:24,340
So this is our object, and this is the name of the class that we have written over here, which is

145
00:07:24,340 --> 00:07:24,940
this one over here.

146
00:07:24,940 --> 00:07:25,390
All right.

147
00:07:25,420 --> 00:07:28,450
Now let's go ahead and enqueue a few elements.

148
00:07:28,450 --> 00:07:30,040
And again we are adding at the end.

149
00:07:30,040 --> 00:07:30,340
All right.

150
00:07:30,340 --> 00:07:34,210
So let's call the enqueue function or method.

151
00:07:34,210 --> 00:07:35,740
So we have dot enqueue.

152
00:07:35,740 --> 00:07:38,650
And then let's just pass in a values one.

153
00:07:38,650 --> 00:07:41,260
And after this let's enqueue two.

154
00:07:41,290 --> 00:07:45,250
So we'll make a node with value two and add it at the end.

155
00:07:45,400 --> 00:07:50,170
Again let's enqueue another element or node with value three.

156
00:07:50,170 --> 00:07:52,660
So let's go ahead and run our function.

157
00:07:53,560 --> 00:07:53,890
All right.

158
00:07:53,890 --> 00:07:56,080
So let's take a look at our Q.

159
00:07:59,290 --> 00:08:01,750
And you can see that it has three nodes.

160
00:08:03,110 --> 00:08:05,060
And we are always adding at the end.

161
00:08:05,060 --> 00:08:06,620
So you can see the first one.

162
00:08:06,620 --> 00:08:10,850
First node is value one, which was added first and then we have two.

163
00:08:12,130 --> 00:08:15,070
And then we have three which points to null.

164
00:08:15,100 --> 00:08:16,810
So this is how it looks like.

165
00:08:16,810 --> 00:08:19,960
Now let's go ahead and dequeue from the queue.

166
00:08:20,920 --> 00:08:25,120
So if we say queue dot dequeue.

167
00:08:34,050 --> 00:08:35,400
Let's just check.

168
00:08:36,860 --> 00:08:37,430
Okay.

169
00:08:37,430 --> 00:08:38,870
It's not Q, it's Q one.

170
00:08:38,870 --> 00:08:39,170
All right.

171
00:08:39,170 --> 00:08:40,880
So that's why we have this error.

172
00:08:40,880 --> 00:08:43,640
So it's q one dot d q.

173
00:08:46,310 --> 00:08:50,900
And over here you can see we are getting one, which is the element which was inserted first.

174
00:08:50,900 --> 00:08:53,900
So if we again dequeue we will get back two.

175
00:08:53,930 --> 00:08:56,030
If we again dequeue will get back three.

176
00:08:56,030 --> 00:09:00,050
If you dequeue again we get back null because there is nothing inside the queue.

177
00:09:00,050 --> 00:09:03,350
So this is how we implement a queue with the linked list.

178
00:09:03,380 --> 00:09:05,690
Now let's take a look at the code over here.

179
00:09:05,690 --> 00:09:05,990
For this.

180
00:09:05,990 --> 00:09:06,920
Let me grab a pen.

181
00:09:07,490 --> 00:09:08,180
All right.

182
00:09:08,180 --> 00:09:12,590
Now what's happening when we enqueue a value let's take a look.

183
00:09:12,590 --> 00:09:15,020
So first over here we are making a new node.

184
00:09:15,020 --> 00:09:16,490
Let's say the value is one.

185
00:09:16,490 --> 00:09:18,650
So we make a node with the value one.

186
00:09:18,650 --> 00:09:21,680
Then we are checking if the singly linked list is empty.

187
00:09:21,680 --> 00:09:23,510
Let's say at this point it's empty.

188
00:09:23,510 --> 00:09:25,040
So we have our node over here.

189
00:09:25,040 --> 00:09:28,790
And we will say first and last is this node itself.

190
00:09:29,330 --> 00:09:29,630
All right.

191
00:09:29,630 --> 00:09:33,500
Now let's say we again enqueue a node with value two.

192
00:09:33,500 --> 00:09:36,470
So we come over here we create a node with value two.

193
00:09:36,500 --> 00:09:38,480
We check if the singly linked list is empty.

194
00:09:38,510 --> 00:09:39,410
No it's not empty.

195
00:09:39,440 --> 00:09:40,820
We have this node over here.

196
00:09:41,180 --> 00:09:42,650
So we come to the else part.

197
00:09:42,650 --> 00:09:46,430
And then we say this dot last which is this node over here dot next.

198
00:09:46,430 --> 00:09:49,700
So this is going to point to the node which we created.

199
00:09:50,120 --> 00:09:52,850
And then we are going to say this dot last is equal to the node.

200
00:09:52,850 --> 00:09:54,830
So we're going to make this last.

201
00:09:55,500 --> 00:09:57,390
This is known no longer last.

202
00:09:57,420 --> 00:09:59,040
Now we are incrementing the size.

203
00:09:59,040 --> 00:10:03,090
Now let's say we are again adding one more value and let's say the value is three.

204
00:10:03,090 --> 00:10:05,490
So again we come over here we create this node.

205
00:10:05,490 --> 00:10:07,440
And then we see it's not empty.

206
00:10:07,470 --> 00:10:11,520
We come over here and then we say this dot last dot next is equal to node.

207
00:10:11,520 --> 00:10:14,580
So this is going to point to the node which is three which we created.

208
00:10:14,580 --> 00:10:16,290
And again we increment the size.

209
00:10:16,290 --> 00:10:18,450
So this is how we are enqueuing elements.

210
00:10:18,450 --> 00:10:21,120
So again notice that we are adding at the end.

211
00:10:21,120 --> 00:10:23,610
Now let's take a look at dequeuing elements.

212
00:10:24,700 --> 00:10:27,190
So let's just clean this up a little bit.

213
00:10:28,810 --> 00:10:32,860
Now when we call the DQ method, we come over here.

214
00:10:33,960 --> 00:10:37,740
And we are checking if the singly linked list is empty.

215
00:10:37,770 --> 00:10:39,480
No, it's not empty at this point.

216
00:10:39,510 --> 00:10:42,510
Now we are going to store this dot first in temp.

217
00:10:42,510 --> 00:10:44,310
So this dot first is this node.

218
00:10:44,310 --> 00:10:45,930
This is going to be equal to temp.

219
00:10:46,470 --> 00:10:50,940
And then we are setting this dot first is equal to this dot first dot next.

220
00:10:50,940 --> 00:10:53,730
So this dot first dot next is this node over here.

221
00:10:53,730 --> 00:10:55,740
Now this is going to be set as first.

222
00:10:55,740 --> 00:10:57,990
So in this way we have removed this node.

223
00:10:57,990 --> 00:11:01,770
And then we are just returning this temp over here which is node one.

224
00:11:01,770 --> 00:11:02,160
All right.

225
00:11:02,160 --> 00:11:04,950
And again over here we are checking if the size became zero.

226
00:11:04,950 --> 00:11:06,150
No it's not at zero.

227
00:11:06,150 --> 00:11:06,510
All right.

228
00:11:06,540 --> 00:11:08,160
Now let's say we again dequeue.

229
00:11:08,160 --> 00:11:10,230
Now at this point this is first all right.

230
00:11:10,230 --> 00:11:11,250
And this is last.

231
00:11:11,250 --> 00:11:12,180
Again this is last.

232
00:11:12,180 --> 00:11:14,400
When we added this this would have been made last.

233
00:11:14,400 --> 00:11:14,790
All right.

234
00:11:14,790 --> 00:11:17,640
So again we come over here we are checking whether it's empty.

235
00:11:17,670 --> 00:11:18,990
No it's not empty.

236
00:11:18,990 --> 00:11:22,140
Then we come over here and we say temp is equal to this dot first.

237
00:11:22,140 --> 00:11:24,090
So this is going to be equal to temp.

238
00:11:25,480 --> 00:11:30,460
And then we are saying this dot first is equal to this dot first dot next which is this node over here.

239
00:11:30,460 --> 00:11:31,810
So this is made first.

240
00:11:31,810 --> 00:11:36,190
And in that manner we have removed this node and we are returning temp over here.

241
00:11:36,190 --> 00:11:38,290
Again the size is not equal to zero right.

242
00:11:38,290 --> 00:11:41,410
So let's dequeue once more so that we get this condition.

243
00:11:41,410 --> 00:11:41,800
True.

244
00:11:41,800 --> 00:11:42,190
All right.

245
00:11:42,190 --> 00:11:44,230
So let's just clean this up a little bit.

246
00:11:44,230 --> 00:11:46,330
So currently it looks like this.

247
00:11:46,330 --> 00:11:48,580
There is just one node in the queue.

248
00:11:51,020 --> 00:11:53,780
And first and last is the same node itself.

249
00:11:53,780 --> 00:11:54,260
All right.

250
00:11:54,260 --> 00:11:55,910
Now again we are dequeuing.

251
00:11:55,910 --> 00:11:57,710
We come over here, we check.

252
00:11:57,710 --> 00:11:58,250
Is it empty?

253
00:11:58,280 --> 00:11:59,240
No, it's not empty.

254
00:11:59,240 --> 00:12:02,000
So we are going to store this dot first in temp.

255
00:12:02,000 --> 00:12:03,440
So this is going to be temp.

256
00:12:03,440 --> 00:12:07,580
And then we are going to say this dot first is equal to this dot first dot next.

257
00:12:07,580 --> 00:12:09,800
Now this over here will be pointing to null.

258
00:12:09,800 --> 00:12:12,020
So we are shifting first ahead.

259
00:12:12,020 --> 00:12:13,850
So first is made null right.

260
00:12:13,850 --> 00:12:15,380
So first is made null.

261
00:12:15,920 --> 00:12:18,200
Now we come over here we decrement the size.

262
00:12:18,200 --> 00:12:21,590
So the size becomes equal to zero because earlier it was one.

263
00:12:21,590 --> 00:12:21,860
Right.

264
00:12:21,890 --> 00:12:26,210
Now when we check this condition this dot size is equal to zero.

265
00:12:26,210 --> 00:12:29,510
Therefore we are going to say this dot last is equal to null.

266
00:12:29,510 --> 00:12:32,600
So last also is shifted from here to null.

267
00:12:32,600 --> 00:12:33,050
All right.

268
00:12:33,050 --> 00:12:37,100
So that's how we are implementing the dequeue instance method.

269
00:12:37,100 --> 00:12:38,900
And then we're just returning temp over here.

270
00:12:38,900 --> 00:12:39,530
All right.

271
00:12:39,530 --> 00:12:42,980
And then again we have seen that we are adding at the end.

272
00:12:44,960 --> 00:12:47,240
And we are removing from the beginning.

273
00:12:47,690 --> 00:12:53,660
And we know that both of these operations, in the case of a singly linked list, is a constant time

274
00:12:53,660 --> 00:12:55,130
and space operation.

275
00:12:56,010 --> 00:13:01,110
So we have implemented our queue with the linked list over here, and then we are able to add elements

276
00:13:01,110 --> 00:13:05,250
and remove elements from the queue in constant time and space.