1
00:00:00,000 --> 00:00:07,866
[No Audio]

2
00:00:07,867 --> 00:00:10,366
Let us look at a business problem. There is

3
00:00:10,367 --> 00:00:12,266
some business with different kinds of stocks.

4
00:00:12,400 --> 00:00:14,300
They have information about your week wise

5
00:00:14,301 --> 00:00:16,600
values, they are interested in a feature of

6
00:00:16,601 --> 00:00:18,733
grabbing the highest value the stock may have

7
00:00:18,734 --> 00:00:22,466
ever reached at any week. They may also want

8
00:00:22,467 --> 00:00:24,266
to go back sequentially week wise, and

9
00:00:24,267 --> 00:00:26,133
determine the highest value of stocks.

10
00:00:26,866 --> 00:00:29,100
Since there are lots of data and many different

11
00:00:29,101 --> 00:00:30,733
kinds of stocks, so therefore, they would

12
00:00:30,734 --> 00:00:32,900
like to grab the information in little to no

13
00:00:32,901 --> 00:00:36,333
time. Let us see this visually to have a more

14
00:00:36,334 --> 00:00:39,333
better intrusion of the problem. We have

15
00:00:39,334 --> 00:00:42,266
week wise stock prices of the data. Week 1

16
00:00:42,267 --> 00:00:44,966
depicts the most oldest record, and Week 6

17
00:00:44,967 --> 00:00:48,633
represents the most recent stock price. For

18
00:00:48,634 --> 00:00:50,866
each week, we record the highest value of the

19
00:00:50,867 --> 00:00:54,233
stock that has been recorded so far. For Week 1,

20
00:00:54,234 --> 00:00:56,766
it has a value of 55, in the second week,

21
00:00:56,767 --> 00:00:59,600
the price goes to 80, and the maximum value is

22
00:00:59,601 --> 00:01:02,900
also 80. In the same way, we have prices for

23
00:01:02,901 --> 00:01:05,666
Week 3. In Week 4 however, the price

24
00:01:05,667 --> 00:01:08,033
is, the highest prices does not change because

25
00:01:08,034 --> 00:01:11,000
120 is the highest price. To implement this

26
00:01:11,001 --> 00:01:13,166
problem, we will make use of what is called

27
00:01:13,167 --> 00:01:16,266
max stack. It is a simple stack, but has the

28
00:01:16,267 --> 00:01:18,266
information of the maximum element in the

29
00:01:18,267 --> 00:01:20,700
stack all the times, and this information can

30
00:01:20,701 --> 00:01:23,566
be obtained in little to no time. In computer

31
00:01:23,567 --> 00:01:25,566
science, we say that this information can be

32
00:01:25,567 --> 00:01:29,266
retrieved in constant time. The max stack can

33
00:01:29,267 --> 00:01:31,666
be implemented in different ways, but we will

34
00:01:31,667 --> 00:01:33,733
implement it using structure containing two

35
00:01:33,734 --> 00:01:37,566
stacks. Let us see how these two stacks will work.

36
00:01:38,133 --> 00:01:40,400
The two starts will be referred to as

37
00:01:40,401 --> 00:01:43,933
the Main Stack and the Max Stack. The Main Stack

38
00:01:43,934 --> 00:01:47,000
will work like an ordinary stack, while

39
00:01:47,001 --> 00:01:49,333
the Max Stack will keep track of the maximum

40
00:01:49,334 --> 00:01:52,066
element. For the first element, we will push it

41
00:01:52,067 --> 00:01:54,200
into the Main Stack. The element will be

42
00:01:54,201 --> 00:01:56,800
checked against the top of the Max Stack.

43
00:01:56,801 --> 00:01:58,466
If it is greater than it will be pushed,

44
00:01:58,467 --> 00:02:00,600
otherwise a copy of the top of the Max Stack

45
00:02:00,601 --> 00:02:03,900
will be pushed into the Max Stack. By default,

46
00:02:03,901 --> 00:02:05,966
the top will be set to a very low value, so

47
00:02:05,967 --> 00:02:08,233
that the first value is always being pushed.

48
00:02:09,199 --> 00:02:10,966
When we have the next element, it will be

49
00:02:10,967 --> 00:02:13,666
pushed as usual in the Main Stack. The value

50
00:02:13,667 --> 00:02:16,700
will be checked against the top of the Max Stack.

51
00:02:16,701 --> 00:02:18,233
Since it is greater in this case,

52
00:02:18,234 --> 00:02:20,666
therefore it will be pushed into the Max Stack.

53
00:02:20,933 --> 00:02:23,266
The next value which is 120 is again greater,

54
00:02:23,267 --> 00:02:25,766
so it will be pushed again. The next value is

55
00:02:25,767 --> 00:02:27,866
22, which is not greater than the top of the

56
00:02:27,867 --> 00:02:30,500
stack, so therefore a copy of the top of the

57
00:02:30,501 --> 00:02:32,666
Max Stack will be pushed instead of the value

58
00:02:32,667 --> 00:02:35,900
22. This process will repeat for all the

59
00:02:35,901 --> 00:02:38,566
values. You may note that, the Max Stack

60
00:02:38,567 --> 00:02:40,633
represents the maximum value in the stack at

61
00:02:40,634 --> 00:02:43,800
any point of time. The pop operation is

62
00:02:43,801 --> 00:02:46,100
simple, and it will pop up elements from both

63
00:02:46,101 --> 00:02:48,766
stacks, the top of the Max Stack will

64
00:02:48,767 --> 00:02:51,433
represent the maximum value in the stack, to

65
00:02:51,434 --> 00:02:54,400
grab the record of the maximum value, that is

66
00:02:54,401 --> 00:02:57,800
three weeks ago, we will do pop three times

67
00:02:57,801 --> 00:03:00,166
and then we'll display the top of the Max Stack.

68
00:03:00,167 --> 00:03:01,800
This way, we are able to retrieve the

69
00:03:01,801 --> 00:03:04,666
maximum value in the stack in little to no time.

70
00:03:04,966 --> 00:03:07,100
Now that we understand the problem, let

71
00:03:07,101 --> 00:03:10,700
us do its implementation. I will implement the

72
00:03:10,701 --> 00:03:13,000
Max Stack as a structure, so let us define it.

73
00:03:13,001 --> 00:03:17,600
[No Audio]

74
00:03:17,601 --> 00:03:20,066
The structure will have two stacks as its

75
00:03:20,067 --> 00:03:23,866
fields.The first stack will be called as Main Stack,

76
00:03:23,867 --> 00:03:26,333
and the second stack will be the

77
00:03:26,334 --> 00:03:29,633
maximum stack. Both the stacks will be the

78
00:03:29,634 --> 00:03:31,600
vectors of type i32.

79
00:03:31,601 --> 00:03:36,333
[No Audio]

80
00:03:36,334 --> 00:03:38,866
Next I will declare an implementation

81
00:03:38,867 --> 00:03:40,666
block for the main, for the

82
00:03:40,667 --> 00:03:44,033
Max Stack where I will define the relevant operations.

83
00:03:44,034 --> 00:03:47,333
[No Audio]

84
00:03:47,334 --> 00:03:49,100
First I will declare a new function,

85
00:03:49,101 --> 00:03:50,866
which will initialize the fields of

86
00:03:50,867 --> 00:03:53,466
the structure, that is main stack and MaxStack

87
00:03:53,467 --> 00:03:54,866
from empty stacks.

88
00:03:54,867 --> 00:04:01,766
[No Audio]

89
00:04:01,767 --> 00:04:03,633
The function you will have no inputs

90
00:04:03,634 --> 00:04:05,733
and will return an instance of Self.

91
00:04:05,734 --> 00:04:09,633
[No Audio]

92
00:04:09,634 --> 00:04:12,566
I will declare the fields of a main_stack

93
00:04:12,567 --> 00:04:15,700
and MaxStack as new empty vectors.

94
00:04:15,701 --> 00:04:21,666
[No Audio]

95
00:04:21,667 --> 00:04:24,533
Now we will implement the push and pop functions.

96
00:04:24,800 --> 00:04:28,033
First we will look into the details of the push function.

97
00:04:28,400 --> 00:04:31,133
The input to this function will be a mutable reference to

98
00:04:31,134 --> 00:04:33,533
Self, and the value that we want to push.

99
00:04:33,534 --> 00:04:39,933
[No Audio]

100
00:04:39,934 --> 00:04:43,466
The value will be pushed into the main_stack.

101
00:04:43,467 --> 00:04:47,500
[No Audio]

102
00:04:47,501 --> 00:04:50,266
Next we will check if the top of the stack is not empty,

103
00:04:50,267 --> 00:04:52,866
and the top of the stack is greater in value,

104
00:04:52,867 --> 00:04:54,500
then the value which is being

105
00:04:54,501 --> 00:04:55,966
pushed into the main_stack,

106
00:04:55,967 --> 00:04:58,033
then we will push a copy of the top of the

107
00:04:58,034 --> 00:04:59,400
stack to the MaxStack

108
00:04:59,401 --> 00:05:05,566
[No Audio]

109
00:05:05,567 --> 00:05:08,433
The first condition checks if the maximum stack

110
00:05:08,434 --> 00:05:10,733
is empty or not. The second condition

111
00:05:10,734 --> 00:05:12,933
means, if the top of the stack is greater than

112
00:05:12,934 --> 00:05:16,600
value, than the value provided. In this case,

113
00:05:16,601 --> 00:05:19,033
we will just push the copy of the top of the

114
00:05:19,066 --> 00:05:22,009
MaxStack and we'll push it into the MaxStack.

115
00:05:22,010 --> 00:05:27,766
[No Audio]

116
00:05:27,767 --> 00:05:29,900
Please note that we are using a mutable

117
00:05:29,901 --> 00:05:31,900
reference to Self, so therefore, we need to

118
00:05:31,901 --> 00:05:35,366
deref the value. In any other case, we will

119
00:05:35,367 --> 00:05:37,700
just push the value into the MaxStack.

120
00:05:38,800 --> 00:05:41,100
The last part will mean that either the

121
00:05:41,101 --> 00:05:43,566
max_stack is empty or the value is

122
00:05:43,567 --> 00:05:45,733
greater than the current top of the stack.

123
00:05:46,666 --> 00:05:48,933
Now, let us look at the pop function. The

124
00:05:48,934 --> 00:05:50,966
input to the function will be a mutable

125
00:05:50,967 --> 00:05:52,066
reference to Self.

126
00:05:52,067 --> 00:05:58,033
[No Audio]

127
00:05:58,034 --> 00:06:00,500
We will first pop the element from the main_stack,

128
00:06:00,501 --> 00:06:02,200
and then to make sure that the

129
00:06:02,201 --> 00:06:06,733
MaxStack is synced with main_stack by doing a pop

130
00:06:06,734 --> 00:06:10,100
on the max stack also, this was easy.

131
00:06:10,600 --> 00:06:13,866
The last function we need is the max_value.

132
00:06:13,867 --> 00:06:15,933
This will return the maximum value in the

133
00:06:15,934 --> 00:06:18,633
stack at any point of time. The input to this

134
00:06:18,634 --> 00:06:20,533
function will be a reference to self and the

135
00:06:20,534 --> 00:06:22,633
output will be an i32 value.

136
00:06:22,634 --> 00:06:29,100
[No Audio]

137
00:06:29,101 --> 00:06:31,233
This function will return the top value of

138
00:06:31,234 --> 00:06:32,500
the max_stack.

139
00:06:32,501 --> 00:06:35,400
[No Audio]

140
00:06:35,401 --> 00:06:36,866
Let us now use the MaxStack

141
00:06:36,867 --> 00:06:38,600
structure in our program.

142
00:06:39,133 --> 00:06:41,800
I will first create an instance of the

143
00:06:41,801 --> 00:06:43,566
MaxStack structure.

144
00:06:43,567 --> 00:06:46,566
[No Audio]

145
00:06:46,567 --> 00:06:49,143
Next I will push some elements into the stack.

146
00:06:49,144 --> 00:06:55,000
[No Audio]

147
00:06:55,001 --> 00:06:57,133
Let us now retrieve the maximum value of the

148
00:06:57,134 --> 00:06:59,603
stock by calling the max_value function.

149
00:06:59,604 --> 00:07:04,900
[No Audio]

150
00:07:04,901 --> 00:07:07,533
Let us now go one week back and retrieve the

151
00:07:07,534 --> 00:07:09,100
maximum stock again.

152
00:07:09,101 --> 00:07:13,600
[No Audio]

153
00:07:13,601 --> 00:07:15,266
We will need to do a single pop

154
00:07:15,267 --> 00:07:17,733
to go one week back in time and

155
00:07:17,734 --> 00:07:21,833
call the max_value, and we'll max display the result.

156
00:07:21,834 --> 00:07:28,566
[No Audio]

157
00:07:28,567 --> 00:07:30,433
Okay, let us cargo run this.

158
00:07:30,434 --> 00:07:34,200
[No Audio]

159
00:07:34,201 --> 00:07:36,700
The maximum st  ock is 145.

160
00:07:36,900 --> 00:07:38,966
If you look at the main, after

161
00:07:38,967 --> 00:07:41,266
entering all the stock prices, the maximum is

162
00:07:41,267 --> 00:07:44,866
indeed 145. Since it was the last item to

163
00:07:44,867 --> 00:07:47,033
be inserted, therefore it represents the most

164
00:07:47,034 --> 00:07:50,066
recent data. After going one week back, the

165
00:07:50,067 --> 00:07:53,233
next highest is 140, which is also retrieved.

166
00:07:53,966 --> 00:07:56,400
The MaxStack is a useful data structure and

167
00:07:56,401 --> 00:07:58,400
can be easily implemented. In the next

168
00:07:58,401 --> 00:08:00,200
tutorial, we will be covering the use of

169
00:08:00,201 --> 00:08:02,400
higher dimensional vectors and nested loops

170
00:08:02,401 --> 00:08:05,566
in, while solving a nice real life example,

171
00:08:05,567 --> 00:08:08,033
that will be more fun. So do come back for

172
00:08:08,034 --> 00:08:11,456
covering that, and until then happy Rust programming.

173
00:08:11,457 --> 00:08:17,300
[No Audio]