1
00:00:00,600 --> 00:00:01,560
Welcome back.

2
00:00:01,560 --> 00:00:06,390
Now first let's take a look at how to implement a stack using an array.

3
00:00:06,390 --> 00:00:08,370
So over here we have our console.

4
00:00:08,370 --> 00:00:09,810
Now let's say I have an array.

5
00:00:09,810 --> 00:00:11,970
So I can just say const.

6
00:00:12,970 --> 00:00:14,920
R is equal to new array.

7
00:00:17,660 --> 00:00:24,560
Now we are going to use Push and Pop to implement the LFO data structure stack, as we have seen in

8
00:00:24,560 --> 00:00:25,520
the previous video.

9
00:00:25,520 --> 00:00:27,200
So let's just push something into this array.

10
00:00:27,200 --> 00:00:31,010
So I have r dot push and let's push in the value one.

11
00:00:31,940 --> 00:00:34,610
And then we push in the value two.

12
00:00:35,060 --> 00:00:37,190
And let's then push in the value three.

13
00:00:37,830 --> 00:00:42,030
Now, if you take a look at the array, we have one, two and three over here.

14
00:00:42,060 --> 00:00:47,010
Now we know that one was pushed in first, then second, then two, then three.

15
00:00:47,010 --> 00:00:48,900
But now we're going to pop from it.

16
00:00:50,370 --> 00:00:54,600
And first we are going to get three, which was inserted at the end, right.

17
00:00:54,600 --> 00:00:55,950
Which was the last to go in.

18
00:00:55,950 --> 00:00:57,600
So last in first out.

19
00:00:57,600 --> 00:01:00,180
So this is how the stack is implemented.

20
00:01:00,180 --> 00:01:02,160
So stack is a data structure.

21
00:01:02,160 --> 00:01:04,080
Now if I again pop I'll get two.

22
00:01:04,110 --> 00:01:05,580
If I pop again I'll get one.

23
00:01:05,580 --> 00:01:09,810
And then if I pop it's going to be undefined because nothing is there in the array.

24
00:01:09,810 --> 00:01:12,810
So this is how we can use an array to implement a stack.

25
00:01:12,810 --> 00:01:13,140
All right.

26
00:01:13,140 --> 00:01:17,010
And we have seen that push and pop is constant time in the case of an array.

27
00:01:17,040 --> 00:01:21,780
Now let's go ahead and see how we can build our own stack using a linked list.

28
00:01:22,080 --> 00:01:26,610
Now this is going to be very much similar to how we implemented the singly linked list.

29
00:01:26,610 --> 00:01:28,920
So we are going to have a node class.

30
00:01:28,920 --> 00:01:31,830
And inside this we have our constructor.

31
00:01:31,830 --> 00:01:33,870
And we pass the value to it.

32
00:01:33,870 --> 00:01:39,900
And then over here we are going to say this dot value is equal to the value which is passed over here.

33
00:01:39,900 --> 00:01:43,890
And then we'll say this dot next is equal to null.

34
00:01:44,370 --> 00:01:44,820
All right.

35
00:01:44,850 --> 00:01:48,330
Now again let's go ahead and write the stack class.

36
00:01:49,410 --> 00:01:52,290
And inside this we're going to have our constructor.

37
00:01:54,260 --> 00:01:58,130
And over here we'll just say this dot first is equal to null.

38
00:02:00,210 --> 00:02:01,950
And this dot last.

39
00:02:04,110 --> 00:02:07,740
Is equal to null and this dot size.

40
00:02:08,470 --> 00:02:09,670
Is equal to zero.

41
00:02:09,670 --> 00:02:12,700
Now, in the case of a linked list, we used head and tail.

42
00:02:12,700 --> 00:02:16,060
But over here, because we are saying stack is a data structure.

43
00:02:16,060 --> 00:02:17,770
Last in first out.

44
00:02:17,770 --> 00:02:20,890
That's why we have the terminology last and first over here.

45
00:02:20,890 --> 00:02:27,700
Now inside the class the stack class, we will write instance methods to add and remove values from

46
00:02:27,700 --> 00:02:28,330
the stack.

47
00:02:28,330 --> 00:02:32,950
So these are the two important functions or properties methods that we need for the stack.

48
00:02:32,950 --> 00:02:35,080
And we will be adding at the beginning.

49
00:02:35,080 --> 00:02:36,400
So let me just write that over here.

50
00:02:36,400 --> 00:02:40,000
Add at the beginning and we will also remove from the beginning.

51
00:02:41,500 --> 00:02:47,710
So this will ensure that the element which was added the in in the as the last element will be removed

52
00:02:47,710 --> 00:02:49,960
first because we are removing from the beginning.

53
00:02:49,960 --> 00:02:50,410
All right.

54
00:02:50,410 --> 00:02:56,140
And again, the reason why we are doing this is that we want constant time removal from from the beginning.

55
00:02:56,140 --> 00:02:58,480
So we could add at the end and remove from the end.

56
00:02:58,480 --> 00:03:03,430
But removing from the end in the case of a singly linked list is going to be an O of n operation.

57
00:03:03,430 --> 00:03:07,960
So removing from the beginning is an O of one operation, and adding at the beginning is an O of one

58
00:03:07,960 --> 00:03:08,350
operation.

59
00:03:08,350 --> 00:03:10,390
So that's why we are doing it in this manner.

60
00:03:10,390 --> 00:03:13,060
Now let's go ahead and write these two instance methods.

61
00:03:13,060 --> 00:03:15,790
So let's call one method add at beginning.

62
00:03:18,490 --> 00:03:20,890
And we have to pass in the value over here.

63
00:03:20,890 --> 00:03:25,240
And the second method that we have to write over here is remove from the beginning.

64
00:03:29,390 --> 00:03:29,840
All right.

65
00:03:29,840 --> 00:03:33,680
Now let's go ahead and first write this method, which is the add at the beginning.

66
00:03:33,680 --> 00:03:35,300
And we have to pass a value.

67
00:03:35,300 --> 00:03:41,090
So what we do inside this instance method is we're going to create a node using our node class over

68
00:03:41,090 --> 00:03:41,450
here.

69
00:03:41,450 --> 00:03:45,860
So we can say const node is equal to new node.

70
00:03:45,860 --> 00:03:47,990
And then we are passing the value over here.

71
00:03:48,440 --> 00:03:50,930
So we have created a node with this value.

72
00:03:50,930 --> 00:03:56,240
And then now let's just check if the singly linked list at this point is empty.

73
00:03:56,240 --> 00:03:59,780
So we can check if not this dot first.

74
00:04:00,770 --> 00:04:02,180
That is, it's just empty.

75
00:04:02,180 --> 00:04:07,580
In that case, we are going to say this dot first is equal to the node which we just now created.

76
00:04:07,580 --> 00:04:11,270
And this dot last is also going to be equal to the node which we created.

77
00:04:11,270 --> 00:04:17,150
Now if this is not the case, that is if there are already nodes inside the singly linked list, then

78
00:04:17,150 --> 00:04:18,590
let's have a temporary variable.

79
00:04:18,590 --> 00:04:22,160
So we can say let temp is equal to this dot first.

80
00:04:23,470 --> 00:04:28,540
And then we will just say this dot first is equal to the node which we just now created.

81
00:04:28,540 --> 00:04:31,300
So this dot first is going to be equal to the node.

82
00:04:31,300 --> 00:04:34,990
And then we will say node dot next is equal to temp.

83
00:04:34,990 --> 00:04:39,370
Or we can just say this dot first dot next right.

84
00:04:39,370 --> 00:04:41,380
So this dot first is now node.

85
00:04:41,380 --> 00:04:46,030
And this dot first dot next is going to be the temp which is what we have stored over here.

86
00:04:46,030 --> 00:04:48,790
Now we could do it in either way you can say no dot next.

87
00:04:48,790 --> 00:04:51,700
So you can say this dot first dot next is equal to temp.

88
00:04:51,700 --> 00:04:56,830
Now once we are out of this because we have added a node and we are tracking the size of the singly

89
00:04:56,830 --> 00:05:01,450
linked list, let's just increment this so we can say this dot size plus plus.

90
00:05:02,170 --> 00:05:02,980
And that's it.

91
00:05:02,980 --> 00:05:08,410
Now let's say after adding the node we want to return the complete singly linked list.

92
00:05:08,410 --> 00:05:10,000
So we can say return this.

93
00:05:10,630 --> 00:05:11,020
All right.

94
00:05:11,020 --> 00:05:11,830
So this should work.

95
00:05:11,830 --> 00:05:15,220
So we have returned the instance method to add at the beginning.

96
00:05:15,220 --> 00:05:18,910
Now let's go ahead and write the instance method to remove from the beginning.

97
00:05:18,910 --> 00:05:21,010
And then we will check or test our code.

98
00:05:21,010 --> 00:05:22,720
So let's go ahead and do this now.

99
00:05:23,990 --> 00:05:28,970
So over here, what we will do is once we are inside the function, once this is called, let's just

100
00:05:28,970 --> 00:05:32,120
check if the singly linked list is null or empty.

101
00:05:32,120 --> 00:05:38,240
So if not this dot first, then we have nothing to remove and we'll just return null.

102
00:05:39,850 --> 00:05:43,390
Now, if this is not the case, let's have a temp variable.

103
00:05:43,390 --> 00:05:46,780
And let's say we want to return the node that we are removing.

104
00:05:46,780 --> 00:05:48,430
So we have a temp variable over here.

105
00:05:48,430 --> 00:05:50,770
And this is going to be equal to this dot first.

106
00:05:51,460 --> 00:05:57,190
And then finally we will just return the temp variable because we are removing this particular node.

107
00:05:57,190 --> 00:05:57,790
Right.

108
00:05:57,790 --> 00:06:00,220
So we are storing the node to temp.

109
00:06:00,220 --> 00:06:06,430
Now once we have done this we just need to shift the first this dot first of this particular singly

110
00:06:06,430 --> 00:06:08,140
linked list to the next node.

111
00:06:08,140 --> 00:06:15,190
So we can say this dot first is equal to this dot first dot next.

112
00:06:16,000 --> 00:06:21,070
So the next node is made the first or the head of the singly linked list.

113
00:06:21,070 --> 00:06:23,440
And then we will just decrement the size.

114
00:06:23,440 --> 00:06:25,870
So this dot size minus minus.

115
00:06:26,950 --> 00:06:31,720
And if we remove the node which was the only node in the singly linked list.

116
00:06:31,720 --> 00:06:34,240
In that case we have to set the last.

117
00:06:34,240 --> 00:06:37,090
Also because we have two properties over here first and last.

118
00:06:37,090 --> 00:06:40,090
So in that case we have to set the last also to null.

119
00:06:40,090 --> 00:06:41,770
So let's just check that over here.

120
00:06:41,770 --> 00:06:45,040
So if this dot size.

121
00:06:46,090 --> 00:06:47,560
Is equal to zero.

122
00:06:49,470 --> 00:06:55,380
Then we will say this dot last is equal to null and that's it.

123
00:06:55,380 --> 00:07:01,380
So we have completed both the instance methods, the method to add at the beginning and the method to

124
00:07:01,380 --> 00:07:02,430
remove from the beginning.

125
00:07:02,430 --> 00:07:08,640
Now you will notice that this is pretty much similar to what we did when we designed our singly linked

126
00:07:08,640 --> 00:07:09,000
list.

127
00:07:09,030 --> 00:07:11,130
Now let's go ahead and test our code.

128
00:07:11,130 --> 00:07:14,910
Now let's have an object with this stack class.

129
00:07:14,910 --> 00:07:18,690
So let's say over here we can say const stack.

130
00:07:18,690 --> 00:07:20,310
Let's just call it stack itself.

131
00:07:21,850 --> 00:07:23,890
Is equal to new stack.

132
00:07:25,910 --> 00:07:26,270
All right.

133
00:07:26,270 --> 00:07:30,590
Now we can call these functions and let's just add some values to it.

134
00:07:30,590 --> 00:07:35,030
So I'm going to add let's just do it in the console itself so we can see it.

135
00:07:35,030 --> 00:07:37,910
So let's clear the console.

136
00:07:37,910 --> 00:07:39,470
And we have run our code.

137
00:07:39,470 --> 00:07:43,100
Now we can say stack dot add at beginning.

138
00:07:43,100 --> 00:07:45,380
And let's say we want to add the value one.

139
00:07:46,130 --> 00:07:46,880
All right.

140
00:07:46,880 --> 00:07:50,780
And again let's add another node with value two at the beginning.

141
00:07:50,780 --> 00:07:53,810
And let's add one more node with the value three at the beginning.

142
00:07:53,930 --> 00:07:57,080
Now let's take a look at how the stack looks like.

143
00:07:59,310 --> 00:08:01,770
So over here you can see the stack has.

144
00:08:02,330 --> 00:08:08,480
As the first node, the node which we entered at the last right, which is three, and then three is

145
00:08:08,480 --> 00:08:12,320
pointing to two, and that is pointing to one, which is pointing to null.

146
00:08:12,320 --> 00:08:13,700
So this is how it looks now.

147
00:08:13,730 --> 00:08:17,360
Now let's go ahead and remove from the beginning.

148
00:08:17,360 --> 00:08:17,840
All right.

149
00:08:17,840 --> 00:08:20,690
So let's call the instance method which we have written.

150
00:08:20,690 --> 00:08:22,310
So remove from the beginning.

151
00:08:23,110 --> 00:08:27,640
And now when we do this, you will see that we are getting the node with value three, which is the

152
00:08:27,640 --> 00:08:29,740
node that was inserted last.

153
00:08:29,740 --> 00:08:29,950
Right.

154
00:08:29,950 --> 00:08:31,690
So it's last in first out.

155
00:08:31,690 --> 00:08:33,430
So we're getting this first out.

156
00:08:33,430 --> 00:08:38,590
Now if you are again calling the remove from if you again call the remove from beginning function,

157
00:08:38,590 --> 00:08:39,520
we get two.

158
00:08:39,550 --> 00:08:41,200
If you do it again we get one.

159
00:08:41,200 --> 00:08:44,620
And if we do it again we get null because there is nothing in the stack.

160
00:08:44,620 --> 00:08:46,180
So yes, our code is working.

161
00:08:46,180 --> 00:08:49,030
Now let's just walk through it and see what's happening over here.

162
00:08:49,030 --> 00:08:53,440
And again, you will notice that this is pretty much similar to what we did in the case of a singly

163
00:08:53,440 --> 00:08:53,980
linked list.

164
00:08:54,490 --> 00:08:56,260
So let's just grab a pen.

165
00:08:57,830 --> 00:09:03,710
And you will see that when we call the add at beginning method and we pass in a value over here, we

166
00:09:03,710 --> 00:09:05,240
are creating a node with that value.

167
00:09:05,240 --> 00:09:07,580
For example we want to insert one.

168
00:09:07,580 --> 00:09:09,230
So let's say the value is one.

169
00:09:09,230 --> 00:09:11,360
And let's say the singly linked list now is empty.

170
00:09:11,360 --> 00:09:14,480
So we are making a node over here with the value one.

171
00:09:14,480 --> 00:09:16,220
And this is going to point to null.

172
00:09:16,880 --> 00:09:17,240
All right.

173
00:09:17,240 --> 00:09:21,140
So that's used using the constructor which is there in our class node.

174
00:09:21,140 --> 00:09:26,090
And then over here we will see that this dot first is actually null because let's say the singly linked

175
00:09:26,090 --> 00:09:27,500
list is null at this point.

176
00:09:27,500 --> 00:09:31,730
So we are going to have we are going to take this node and we will make it the first and last.

177
00:09:31,730 --> 00:09:34,130
So first is also going to be this node.

178
00:09:34,280 --> 00:09:36,620
And last is also going to be this node.

179
00:09:36,620 --> 00:09:38,660
Let's say we are again inserting another value.

180
00:09:38,660 --> 00:09:40,610
And at this time let it be the value two.

181
00:09:40,640 --> 00:09:43,760
So what happens is we make a node with value two.

182
00:09:43,790 --> 00:09:46,820
Then we come over here we see that first is not null.

183
00:09:46,820 --> 00:09:48,560
So there is something in the singly linked list.

184
00:09:48,560 --> 00:09:49,760
So we come over here.

185
00:09:49,760 --> 00:09:52,670
Then we say that temp is going to be equal to this dot.

186
00:09:52,670 --> 00:09:55,400
First is going to be this node over here.

187
00:09:55,400 --> 00:09:57,350
So this is write that.

188
00:09:57,350 --> 00:09:58,160
So temp.

189
00:09:59,800 --> 00:10:00,730
Is this node.

190
00:10:00,760 --> 00:10:05,740
Then we come over here and we are going to say this dot first is equal to node, which is the node that

191
00:10:05,740 --> 00:10:06,430
we created.

192
00:10:06,430 --> 00:10:09,400
So we are making this node the first node.

193
00:10:09,550 --> 00:10:14,560
And then we are saying this dot first dot next that is this is going to point to temp.

194
00:10:14,560 --> 00:10:15,910
So this will point to one.

195
00:10:15,910 --> 00:10:18,010
And this is already pointing to null.

196
00:10:18,010 --> 00:10:20,050
So in this way we have added at the beginning.

197
00:10:20,050 --> 00:10:20,470
All right.

198
00:10:20,470 --> 00:10:23,500
And among these two this is the latest inserted right.

199
00:10:23,500 --> 00:10:25,090
So this is last in.

200
00:10:26,390 --> 00:10:26,750
All right.

201
00:10:26,750 --> 00:10:28,130
And we call this first.

202
00:10:28,130 --> 00:10:30,200
And this is last at this moment.

203
00:10:31,070 --> 00:10:31,370
All right.

204
00:10:31,370 --> 00:10:32,450
In our singly linked list.

205
00:10:32,480 --> 00:10:34,130
Now we are going to take this out.

206
00:10:34,130 --> 00:10:36,620
When we take out we're going to remove from the beginning.

207
00:10:36,620 --> 00:10:39,320
So we're going to take this out which is first out.

208
00:10:39,680 --> 00:10:41,540
So last in first out.

209
00:10:41,540 --> 00:10:43,880
And that's why this is a leaf data structure.

210
00:10:43,880 --> 00:10:46,790
And again a stack is a leaf data structure.

211
00:10:46,790 --> 00:10:48,500
So let's see this code also.

212
00:10:48,500 --> 00:10:52,040
Now over here we have the code to remove from the beginning.

213
00:10:52,040 --> 00:10:53,510
So let me just clear this up.

214
00:10:53,510 --> 00:10:55,190
So let's say we call this.

215
00:10:55,190 --> 00:10:58,790
Now we come over here we see that first is not null.

216
00:10:58,790 --> 00:10:59,870
Then we come over here.

217
00:10:59,870 --> 00:11:02,300
And then we're going to say temp is equal to this dot first.

218
00:11:02,300 --> 00:11:04,190
So this over here is going to be temp.

219
00:11:05,880 --> 00:11:10,080
And then we say this dot first is equal to this dot first dot next.

220
00:11:10,080 --> 00:11:12,870
Now this dot first dot next is this node over here.

221
00:11:12,870 --> 00:11:15,060
So this is going to be made first.

222
00:11:15,450 --> 00:11:19,110
So in that way we have removed this node right from the singly linked list.

223
00:11:19,110 --> 00:11:20,760
And then we are reducing the size.

224
00:11:20,760 --> 00:11:23,430
And we are returning this over here which is the temp.

225
00:11:23,430 --> 00:11:24,750
So we will get back to.

226
00:11:24,780 --> 00:11:27,000
So you can see we are removing from the beginning.

227
00:11:27,000 --> 00:11:31,260
So the node which was added latest is going to be returned first.

228
00:11:32,320 --> 00:11:35,770
So this is how we have implemented a stack with a linked list.

229
00:11:35,770 --> 00:11:41,740
And you can see that adding at the beginning and removing from the beginning both is constant space

230
00:11:41,740 --> 00:11:42,160
and time.

231
00:11:42,160 --> 00:11:45,820
So the time and space complexity of this is O of one.