[No Audio]
Let us look at a business problem. There is
some business with different kinds of stocks.
They have information about your week wise
values, they are interested in a feature of
grabbing the highest value the stock may have
ever reached at any week. They may also want
to go back sequentially week wise, and
determine the highest value of stocks.
Since there are lots of data and many different
kinds of stocks, so therefore, they would
like to grab the information in little to no
time. Let us see this visually to have a more
better intrusion of the problem. We have
week wise stock prices of the data. Week 1
depicts the most oldest record, and Week 6
represents the most recent stock price. For
each week, we record the highest value of the
stock that has been recorded so far. For Week 1,
it has a value of 55, in the second week,
the price goes to 80, and the maximum value is
also 80. In the same way, we have prices for
Week 3. In Week 4 however, the price
is, the highest prices does not change because
120 is the highest price. To implement this
problem, we will make use of what is called
max stack. It is a simple stack, but has the
information of the maximum element in the
stack all the times, and this information can
be obtained in little to no time. In computer
science, we say that this information can be
retrieved in constant time. The max stack can
be implemented in different ways, but we will
implement it using structure containing two
stacks. Let us see how these two stacks will work.
The two starts will be referred to as
the Main Stack and the Max Stack. The Main Stack
will work like an ordinary stack, while
the Max Stack will keep track of the maximum
element. For the first element, we will push it
into the Main Stack. The element will be
checked against the top of the Max Stack.
If it is greater than it will be pushed,
otherwise a copy of the top of the Max Stack
will be pushed into the Max Stack. By default,
the top will be set to a very low value, so
that the first value is always being pushed.
When we have the next element, it will be
pushed as usual in the Main Stack. The value
will be checked against the top of the Max Stack.
Since it is greater in this case,
therefore it will be pushed into the Max Stack.
The next value which is 120 is again greater,
so it will be pushed again. The next value is
22, which is not greater than the top of the
stack, so therefore a copy of the top of the
Max Stack will be pushed instead of the value
22. This process will repeat for all the
values. You may note that, the Max Stack
represents the maximum value in the stack at
any point of time. The pop operation is
simple, and it will pop up elements from both
stacks, the top of the Max Stack will
represent the maximum value in the stack, to
grab the record of the maximum value, that is
three weeks ago, we will do pop three times
and then we'll display the top of the Max Stack.
This way, we are able to retrieve the
maximum value in the stack in little to no time.
Now that we understand the problem, let
us do its implementation. I will implement the
Max Stack as a structure, so let us define it.
[No Audio]
The structure will have two stacks as its
fields.The first stack will be called as Main Stack,
and the second stack will be the
maximum stack. Both the stacks will be the
vectors of type i32.
[No Audio]
Next I will declare an implementation
block for the main, for the
Max Stack where I will define the relevant operations.
[No Audio]
First I will declare a new function,
which will initialize the fields of
the structure, that is main stack and MaxStack
from empty stacks.
[No Audio]
The function you will have no inputs
and will return an instance of Self.
[No Audio]
I will declare the fields of a main_stack
and MaxStack as new empty vectors.
[No Audio]
Now we will implement the push and pop functions.
First we will look into the details of the push function.
The input to this function will be a mutable reference to
Self, and the value that we want to push.
[No Audio]
The value will be pushed into the main_stack.
[No Audio]
Next we will check if the top of the stack is not empty,
and the top of the stack is greater in value,
then the value which is being
pushed into the main_stack,
then we will push a copy of the top of the
stack to the MaxStack
[No Audio]
The first condition checks if the maximum stack
is empty or not. The second condition
means, if the top of the stack is greater than
value, than the value provided. In this case,
we will just push the copy of the top of the
MaxStack and we'll push it into the MaxStack.
[No Audio]
Please note that we are using a mutable
reference to Self, so therefore, we need to
deref the value. In any other case, we will
just push the value into the MaxStack.
The last part will mean that either the
max_stack is empty or the value is
greater than the current top of the stack.
Now, let us look at the pop function. The
input to the function will be a mutable
reference to Self.
[No Audio]
We will first pop the element from the main_stack,
and then to make sure that the
MaxStack is synced with main_stack by doing a pop
on the max stack also, this was easy.
The last function we need is the max_value.
This will return the maximum value in the
stack at any point of time. The input to this
function will be a reference to self and the
output will be an i32 value.
[No Audio]
This function will return the top value of
the max_stack.
[No Audio]
Let us now use the MaxStack
structure in our program.
I will first create an instance of the
MaxStack structure.
[No Audio]
Next I will push some elements into the stack.
[No Audio]
Let us now retrieve the maximum value of the
stock by calling the max_value function.
[No Audio]
Let us now go one week back and retrieve the
maximum stock again.
[No Audio]
We will need to do a single pop
to go one week back in time and
call the max_value, and we'll max display the result.
[No Audio]
Okay, let us cargo run this.
[No Audio]
The maximum st ock is 145.
If you look at the main, after
entering all the stock prices, the maximum is
indeed 145. Since it was the last item to
be inserted, therefore it represents the most
recent data. After going one week back, the
next highest is 140, which is also retrieved.
The MaxStack is a useful data structure and
can be easily implemented. In the next
tutorial, we will be covering the use of
higher dimensional vectors and nested loops
in, while solving a nice real life example,
that will be more fun. So do come back for
covering that, and until then happy Rust programming.
[No Audio]