[No Audio]
Hello and welcome back again. The
objective in this and some of the upcoming
tutorials is, to give you some practice of
coding in Rust by applying what we have
learned so far. While doing this, we will
have a chance of learning frequently used
data structure called stack. More
specifically, it is an abstract data type or
ADT, commonly used in most programming
languages. It is named stack as it behaves
like a real world stack, for example, a deck
of cards or a pile of plates. A real world
stack allows operations at one end only, for
example, we can place or move a card or plate
from the top of the stack only. Likewise, the
stack abstract data type allows all data
operations at one end only. At any given time,
we can only access the top element of a stack.
This feature makes it behaves in a manner
that last element in is always the first one
to get out. This is sometimes referred to as
LIFO for short, that is Last In First Out.
There are two key terminologies that are
being used in connection with the stack, that
are called push and pop. In fact, these
are operations that are being performed on
the stack. The push operation is used to
insert on, or add in element at the top of the
stack, and the pop is used to remove an
element from the top of the stack. Some
simple applications of stack include string
traversal, expression evaluation,
backtracking, and syntax parsing. This
visualization explains the key concepts of
stack. Initially, we have an empty stack with
no top element, and insert a value of 10 into
the stack, the top of the stack element is
now, has now the value of 10. Next we add
another element in the stack using a push
operation. And the new value of 20 which is
being pushed, is now the new top of the stack.
Next to push another element with the value
of 30, which is the new top of the stack, the
pop operation will remove the top of the
stack element from the stack. So when the top
of the stack element is being removed, the
new top of the stack will become 20. This way
the stack ensures that the element which is,
which is first being pushed is always the last one
which is going to be out from the stack.
There is also a very nice online
visualization of stack, let me open it. There
are two operations that we can perform on the
stack, typically during implementation we
will have a fixed size of the stack.
These small boxes represents the elements
of the stack, which are all initially empty.
And let us add a few elements to the stack. I
will add a value of 30, followed by 15, and then 36.
[No Audio]
You may note that each time I add an
element, it is being added to the front of the
stack. You may consider this tag to be a
stack which is horizontal in direction. The
elements at the front are the top of the
stack elements. Let me do a pop and you may
note that the element from the front, which
represents the top of the stack, are being
removed. This visualization is helpful from
programming perspective, because in
programmatic implementation or in code, we
will encounter such horizontal implementation
of stack. Okay, now it's time to implement
the stack in Rust. So I will open up the VS Code.
The first thing to note is that, in Rust
there are many useful collections which
provides behavior and functionality similar
to that of a stack, and other important
abstract data types, such as heaps and linked
lists. All we need to do is to have some
wrapping around these beautifully designed
collections to implement the desired
functionality. The stack can be implemented
using vectors, simple arrays, the linked
lists, or vecdeque types. Since the objective in
these tutorials is to practice what we have
learned so far, so we will therefore use the
Vec type for implementing the stack.
I'm considering to implement a stack of u32
values. To start with, we will first define a
function called new_stack, this
function will receive an input of maxsize
which indicates how much space we need to
have in the stack, and then it will create a
new stack, and then we will, we will return that stack.
[No Audio]
Please note that the maxsize needs to be of
usize, because the size of the Vec needs to
be specified as usize type. The
with::capacity is a function, which is
used to create a vector with some predefined,
or some specified number of elements. This
function was covered in the earlier tutorials
also. Next we are going to define the pop
function. This function is going to remove the
topmost element from the stack, and will
display its value to the user. If the stack
is empty, then in this case this function
should return a none or no value. I will
declare the function pop and will provide a
mutable reference to the back as an input.
[No Audio]
Now this is because the function is supposed
to remove an element from that from the stack,
which means, we will be modifying the stack.
The output of the function will be an
optional u32 value, the option type
represents either some value, if the value
exists, or none value if the value, if there is
no value. Inside the function, I will declare a
variable called popped value, which will
store the result of pop operation on the stack.
[No Audio]
This will essentially remove the top
element from the back. Next, I will include, I
will include a print statement to display the
contents of the poped value.
[No Audio]
Finally, I will return the poped_val,
so I will write popped_val
without the semicolon. Next, the next
function we will implement is, the push
function, which will add the given value to
the top of the stack, so, let us declare the push function.
[No Audio]
The input will be a mutable reference to the stack.
[No Audio]
Please note that we should
be using a reference in all the
functions, because we do not want to take the
ownership of the stack, but rather we just
want to add an element to the stack. In
addition to the mutable reference to the stack,
we also need the item or number that
we want to add to the stack, so, let me mention that also.
[No Audio]
Finally, I will also need
a third input, which is the size of the stack.
This will be used to check if the maxsize is
reached or not, we will not allow further
elements to be added, if we have reached the
maxsize. This function is not going to return
anything. Inside the function, I will check if
the current length of the stack is equal to
that of the maxsize or not.
[No Audio]
In this case, I should not be adding any
further elements, therefore, I will display
the message of cannot add more.
[No Audio]
If however, this is not true, then I will
continue with adding the given item to the
top of the stack using the push function.
[No Audio]
I will also display the contents of the stack.
[No Audio]
I will add one more simple function, which is
going to return the current size of the stack
I will declare this function with the name of size.
The input, in this case, will be a, will be
an immutable reference to the stack, since we
are not modifying the stack and the output
will be the size of the stack which is of type usize.
[No Audio]
Inside the function, I will use the length
function on the stack, which will return the size.
[No Audio]
Okay great, we are almost done with the
stack implementation. Now, let us add some
code in the main function. In the main
function, first I will ask the user to tell me
the number of elements he wants to have in
the stack. So, I will add a suitable print
statement for this purpose.
[No Audio]
Next, I will write the code for taking the
user input, and I will store the input in the
variable of size_stack.
[No Audio]
As I will be using the code for taking the
user input many times, for tasks such as
selecting operation types such as, push, pop,
and for mentioning the item that the user
wants to push. So therefore, it is more
appropriate to have some function which will
contain the code for taking the user input. I
will declare the function with the name of
input this function will have no input, and
the output will be the values that are being
provided as input by the user. Now since we
are dealing mainly with the u32 type,
so I am expecting the input to be of type
u32. Therefore for the output type, I will
mention u32. Inside the body of the
function, I will write the code for taking the
user input which we covered in the previous sections.
[No Audio]
I will write the code for converting
the input to u32 using the parse function.
[No Audio]
Finally I will return the
input. Inside the main function, I will use
this function to have user input regarding
the size of the stack.
[No Audio]
Next, I will call the new_stack function
to create the stack.
[No Audio]
Please note that, since I will be adding
elements and deleting elements from the stack,
therefore I need to declare it as mutable,
and secondly, the size of the stack needs to
be mentioned as usize. So therefore, I
will convert the u32 to usize.
And next, I will display a menu to the user, from
which he can select one of the available
options on the stack.
[No Audio]
Again, for grabbing and storing the user
choice, we will call the input function, and
will storage result in the variable choice.
[No Audio]
Next, I will use a match statement to see
which choice is being selected, and
will make appropriate function calls. I will
do a match on the choice variable for this purpose.
[No Audio]
Next, I will mention the arms
corresponding to different choices. In case
the choice is one, so I will push an element
onto the stack. Let me add the arm
corresponding to first choice. In this case,
I will ask the user for the item that he
wants to insert into the stack. I will take
the input from the user and we'll store it in
a variable of item.
[No Audio]
Finally, I will call the push function
to add the element to the stack.
The function needs three inputs, that is the
mutable reference to the stack, the item we
want to insert and the signs. Now let us add
the arm for the second choice. In this case,
I will pop the element from the stack. So I
will call the pop function and we'll display
the element that is being popped out.
[No Audio]
The next arm is for choice 4, in this case,
we will display the sides of the stack, so
let me complete the code for this arm also.
[No Audio]
In case of none, there is none of the above
arm matches, so I will exit. This is going to
be the default arm, so let me include this also.
[No Audio]
Now this code will only allow a single
operation to take place, there is a single pop,
or push, or display. I want the same code to
be repeated multiple times, and when the user
want to exit, so only in that case, I will
break out from the iterations. So to do that,
I will enclose this whole code inside a loop.
[No Audio]
At the end of the loop, I will ask the user
again if he wants to continue or not. So I
will create a suitable print statement and
we'll take the user input, and store it in
some variable, let's say status. Next, I will
add a simple if else statement. In the left
part, I will check if the user wants to
continue with the operations on the stack. So
I will continue with the next iteration of the loop.
In any other case, I will break out from the loop.
Now this code is correct, but
it will be more meaningful if I include the
the if else inside the match, inside the match
statement by adding another arm for the
match. Because the value 5 in our menu
list, corresponds to an exit. So I will write
5 and then a break.
And we'll comment out the print statement.
Finally for the default case,
I will write something like, wrong
selection try again. Ok, and now our code is complete.
Let us execute this program.
[No Audio]
it will ask for the size of the stack, so
let me enter the value of 3. The menu list
has been displayed, let us try to pop
something from the empty stack. The popped
element is none, because we do not have any,
anything to pop. Let us continue again by
selecting 1. This time I will push something
like 56. Let me continue again and push one
more element. At this time I will add the
value of 8. The stack, in this case is in
horizontal direction, and the top of the stack
is indicated by the right-most element.
Let us add one more element. Let us try one more
element, and this should be, and this should not be
possible, because we are at the limit of the
stack. It rightfully says that, we cannot add
more. Let us also test the pop function and
remove one element. The top of the stack is
being removed, the statement contains only
two elements. Before we end, I would like to
highlight the fact that there are many other
efficient ways in which we can implement a
stack using Rust. Using some advanced concepts
such as, generic, structures and others, which
we will cover later on in the course. The
objective however in this implementation was,
to have some practice of the key concepts and
notions that we have learned so far.
Finally there is also more effective and
efficient way of testing our code, which we
will cover later on in the sections. With
this we end this tutorial. In the upcoming
tutorials, we will be looking at some
applications of stack. So do come back for
covering that and until then happy Rust programming.
[No Audio]