1
00:00:00,790 --> 00:00:01,630
Hi everyone.

2
00:00:01,630 --> 00:00:05,560
In this question we're going to learn how to design a stack.

3
00:00:05,560 --> 00:00:07,000
Now let's read the question.

4
00:00:07,000 --> 00:00:09,610
Implement a stack using an array.

5
00:00:09,610 --> 00:00:13,360
And secondly with the stack class using a linked list.

6
00:00:13,360 --> 00:00:16,210
So we're going to implement a stack in these two ways.

7
00:00:16,210 --> 00:00:21,670
One should be able to add to the stack and remove from the stack following the LFO property.

8
00:00:21,670 --> 00:00:28,060
Remember we have discussed that a stack is a data structure where LFO stands for last in first out.

9
00:00:28,060 --> 00:00:30,370
That is all which is important about a stack.

10
00:00:30,370 --> 00:00:35,260
So you should be able to add things to the stack and remove from the stack following the LFO.

11
00:00:35,590 --> 00:00:37,690
Um order last in first out.

12
00:00:37,690 --> 00:00:43,540
Now remember, in JavaScript there is no inbuilt stack, so we can either implement a stack using an

13
00:00:43,540 --> 00:00:44,740
array or a linked list.

14
00:00:44,740 --> 00:00:47,350
So there are multiple ways in which we can implement a stack.

15
00:00:47,350 --> 00:00:48,640
So let's get started.

16
00:00:48,640 --> 00:00:51,130
First we are going to implement a stack with an array.

17
00:00:51,130 --> 00:00:54,490
Now let's say we have an array and we call it a r r r.

18
00:00:54,490 --> 00:00:56,920
So we can say const r is equal to new array.

19
00:00:56,920 --> 00:00:58,270
So we have an array over here.

20
00:00:58,270 --> 00:01:01,960
And then now we need to be able to add to this and remove from this.

21
00:01:01,960 --> 00:01:04,300
And we have to follow last in first out.

22
00:01:04,300 --> 00:01:08,020
So that's what a stack is about when we implement a stack with an array.

23
00:01:08,020 --> 00:01:12,460
Now for adding to this array we will use push which will add to its end.

24
00:01:12,460 --> 00:01:16,270
And for removing we will use pop which will remove from its end.

25
00:01:16,270 --> 00:01:18,490
Now let's try to see how this works out.

26
00:01:18,490 --> 00:01:20,800
So let's say the array is empty at this point.

27
00:01:20,830 --> 00:01:23,890
Now we're going to use push to add a value to the array.

28
00:01:23,890 --> 00:01:26,050
So let's say we push three into the array.

29
00:01:26,080 --> 00:01:28,000
Now we are going to push four to it.

30
00:01:28,000 --> 00:01:30,490
Now notice that pushing is adding at the end.

31
00:01:30,490 --> 00:01:33,010
Now let's say we again push five also to the array.

32
00:01:33,070 --> 00:01:38,770
Now you can see that three is the element that was first added in, then four and then five.

33
00:01:38,770 --> 00:01:40,810
Now we are going to pop from the array.

34
00:01:40,840 --> 00:01:46,240
Now if we pop from the array we will get back the element which was added last in.

35
00:01:46,240 --> 00:01:47,500
So this was last in.

36
00:01:47,500 --> 00:01:49,750
So this was the element which was added last.

37
00:01:49,750 --> 00:01:50,170
Right.

38
00:01:50,170 --> 00:01:52,060
And this is going to be first out.

39
00:01:52,060 --> 00:01:58,570
So when we do R dot pop and we call the pop method we are going to get five which is the element which

40
00:01:58,570 --> 00:01:59,710
was added in last.

41
00:01:59,710 --> 00:02:02,890
So you can see that it is following the LFO property.

42
00:02:02,890 --> 00:02:09,070
And in this manner by just using push and pop, we have implemented a stack by just using an array.

43
00:02:09,070 --> 00:02:09,520
All right.

44
00:02:09,550 --> 00:02:14,710
Now we know that pushing into an array is a constant time operation, and popping also from an array

45
00:02:14,710 --> 00:02:16,330
is a constant time operation.

46
00:02:16,330 --> 00:02:19,210
So this is how we can implement a stack with an array.

47
00:02:19,210 --> 00:02:20,920
Now this is very useful.

48
00:02:20,920 --> 00:02:26,350
You will see that especially in, in uh things like implementing a depth first search etc., which we

49
00:02:26,350 --> 00:02:32,650
will see in the latter part of this course, we will use a stack when we do a DFS or depth, first search

50
00:02:32,650 --> 00:02:35,410
in a graph, etc., in an iterative manner.

51
00:02:35,410 --> 00:02:36,640
So we will see that later.

52
00:02:36,640 --> 00:02:41,890
But again we have implemented a stack using an array and it's pretty straightforward and we are getting

53
00:02:41,890 --> 00:02:43,120
good performance also.

54
00:02:43,120 --> 00:02:49,540
Now let's go ahead and see how we can build our own stack from the from scratch using a linked list.

55
00:02:49,540 --> 00:02:53,620
Now we could either use a singly linked list or a doubly linked list.

56
00:02:53,620 --> 00:02:56,500
Now over here in this video we are going to use a singly linked list.

57
00:02:56,500 --> 00:03:00,160
And if you want, you can go ahead and implement it with a doubly linked list also.

58
00:03:00,160 --> 00:03:02,110
And there would be just minor changes.

59
00:03:02,110 --> 00:03:02,620
All right.

60
00:03:02,650 --> 00:03:03,730
Now let's go ahead.

61
00:03:03,730 --> 00:03:08,350
Now what we will do is we will have a node class and we will have a stack class.

62
00:03:08,350 --> 00:03:08,770
All right.

63
00:03:08,770 --> 00:03:16,150
Now using the node class every element which is added again is going to have a value and a next property.

64
00:03:16,150 --> 00:03:20,140
So this is pretty much similar to what we have seen in the linked list section.

65
00:03:20,140 --> 00:03:22,300
And then we have this stack class.

66
00:03:22,300 --> 00:03:23,350
We have a constructor.

67
00:03:23,350 --> 00:03:28,180
And in the case of a linked list we called the first element head and the last element tail.

68
00:03:28,180 --> 00:03:30,760
But over here we are just calling it first and last.

69
00:03:30,760 --> 00:03:33,760
And then we are tracking the size of the linked list as well.

70
00:03:33,760 --> 00:03:40,000
Now over here in this stack class we are going to have two instance methods, one to add at the beginning

71
00:03:40,000 --> 00:03:42,460
and the second one to remove from the beginning.

72
00:03:42,460 --> 00:03:42,880
All right.

73
00:03:42,880 --> 00:03:46,660
So this is how we will implement a stack with a linked list.

74
00:03:46,660 --> 00:03:50,800
Now notice over here that we are adding at the beginning and removing at the beginning.

75
00:03:50,800 --> 00:03:53,200
Now this will follow the LFO property.

76
00:03:53,200 --> 00:03:58,720
But even if we were adding at the end and removing from the end, it would still follow the LFO property,

77
00:03:58,720 --> 00:04:04,090
but then removing from the end in the case of a singly linked list is an O of N operation.

78
00:04:04,090 --> 00:04:06,190
So that is why we are not doing it in that manner.

79
00:04:06,190 --> 00:04:10,840
We know that removing from the beginning is an O of one operation or a constant time operation.

80
00:04:10,840 --> 00:04:16,180
In the case of a singly linked list, and adding at the beginning is also a constant time operation

81
00:04:16,180 --> 00:04:17,860
in the case of a singly linked list.

82
00:04:17,890 --> 00:04:21,520
Now, if we were using a doubly linked list, then it would not matter.

83
00:04:21,520 --> 00:04:27,190
So we can either add and remove from the beginning, or add and remove from the end, and it would just

84
00:04:27,190 --> 00:04:28,690
work in constant time.

85
00:04:28,690 --> 00:04:29,140
All right.

86
00:04:29,140 --> 00:04:32,380
So to recap we have this node class.

87
00:04:32,380 --> 00:04:37,090
So every element which is added to the singly linked list will be a node.

88
00:04:37,090 --> 00:04:39,340
And then we have the stack class.

89
00:04:39,340 --> 00:04:43,180
And we are tracking the first and last element in the linked list and the size.

90
00:04:43,180 --> 00:04:47,770
And then we're going to write these two instance methods to add and remove from the beginning.

91
00:04:47,770 --> 00:04:53,230
And the reason why we are adding and removing from the beginning is that if we were to choose removal

92
00:04:53,230 --> 00:04:59,200
and addition at the end, in that case, removing from the end is a O of n operation which is not efficient.

93
00:04:59,200 --> 00:05:00,190
So to make the.

94
00:05:00,780 --> 00:05:01,380
Efficient.

95
00:05:01,380 --> 00:05:06,270
We are adding and removing at the beginning, especially because we are using a singly linked list.

96
00:05:06,300 --> 00:05:06,810
All right.

97
00:05:06,840 --> 00:05:10,560
Now let's go ahead and see how we add and remove from the beginning.

98
00:05:10,560 --> 00:05:12,060
In the case of a singly linked list.

99
00:05:12,060 --> 00:05:15,240
So this is something that we have just we have already discussed previously.

100
00:05:15,240 --> 00:05:17,280
But let's just quickly revise it over here.

101
00:05:17,280 --> 00:05:21,270
So let's say we have one node currently in the singly linked list.

102
00:05:21,270 --> 00:05:23,190
Now we are going to add one more node.

103
00:05:23,190 --> 00:05:25,050
Let's say we it has the value b.

104
00:05:25,050 --> 00:05:26,910
And we are going to add at the beginning.

105
00:05:26,910 --> 00:05:28,500
So we are going to have b over here.

106
00:05:28,500 --> 00:05:29,940
And b points to A.

107
00:05:29,940 --> 00:05:32,400
And then let's add one more node at the beginning.

108
00:05:32,400 --> 00:05:33,480
So let's say that c.

109
00:05:33,510 --> 00:05:36,360
So c is going to point to b and b points to a.

110
00:05:36,390 --> 00:05:41,160
Now if you want to remove from the beginning we will get back this c over here.

111
00:05:41,160 --> 00:05:45,570
And you can notice that this was the element which was added latest.

112
00:05:45,570 --> 00:05:45,810
Right.

113
00:05:45,810 --> 00:05:48,870
This was the last in element to the singly linked list.

114
00:05:48,870 --> 00:05:54,180
So yes we can see that it is following the lifting property or last in first out.

115
00:05:54,180 --> 00:05:57,240
And that is the property which has to be followed by a stack.

116
00:05:57,890 --> 00:06:01,460
Now let's also see how we can implement this in code.

117
00:06:01,460 --> 00:06:03,530
So let's say this is our singly linked list.

118
00:06:03,560 --> 00:06:09,650
Now if we want to add at the beginning we'll just have a new node created using the node class.

119
00:06:09,650 --> 00:06:13,010
And then we will make this node point to the previous head.

120
00:06:13,010 --> 00:06:15,800
And then we will make this node over here the head.

121
00:06:15,800 --> 00:06:17,240
In the case of a singly linked list.

122
00:06:17,240 --> 00:06:19,670
And over here we are just calling the head first.

123
00:06:19,670 --> 00:06:21,950
So it's just a terminology difference.

124
00:06:21,950 --> 00:06:24,530
So instead of head we will just call it first over here.

125
00:06:24,680 --> 00:06:26,930
So this is how we are adding at the beginning.

126
00:06:26,930 --> 00:06:32,300
Now if you want to remove from the beginning all that we have to do is we will move the head to the

127
00:06:32,300 --> 00:06:33,050
next node.

128
00:06:33,050 --> 00:06:35,120
And then in that way we are just removing.

129
00:06:35,120 --> 00:06:35,300
Right.

130
00:06:35,300 --> 00:06:40,550
So to remove this we are just removing the head or the first to the next node.

131
00:06:40,550 --> 00:06:41,000
All right.

132
00:06:41,000 --> 00:06:42,530
So this is going to be first.

133
00:06:42,530 --> 00:06:45,380
So that means the singly linked list starts from here.

134
00:06:45,380 --> 00:06:47,150
And this node has been removed.

135
00:06:47,150 --> 00:06:48,380
And then we can track this.

136
00:06:48,380 --> 00:06:51,200
We can store this somewhere before removing and return it.

137
00:06:51,200 --> 00:06:56,750
Because typically when we have a remove instance method we return the node or the value that is being

138
00:06:56,750 --> 00:06:57,170
removed.

139
00:06:57,170 --> 00:07:00,530
So this is how we will implement our stack with linked list.

140
00:07:00,530 --> 00:07:06,080
And again remember the space and time complexity of both the add at beginning and remove at beginning

141
00:07:06,080 --> 00:07:08,450
instance methods is going to be o of one.