Practical Assignment No:3
Aim: To study the concept of stack’s push and pop operation and to study the applications of
stacks.
Problem Statement: Implement stack as an abstract data type using singly linked list and use
this ADT for conversion of infix expression to postfix, prefix and evaluation of postfix and
prefix expression.
Objective:
1. To understand the algorithms of push and pop operations.
2. To understand and implement the applications of stacks.
Theory:
What is Stack?
Stack is a linear data structure that follows a particular order in which the operations are
performed. The order may be LIFO(Last In First Out) or FILO(First In Last Out). LIFO
implies that the element that is inserted last, comes out first and FILO implies that the
element that is inserted first, comes out last.
There are many real-life examples of a stack. Consider an example of plates stacked over one
another in the canteen. The plate which is at the top is the first one to be removed, i.e. the plate
which has been placed at the bottommost position remains in the stack for the longest period of
time. So, it can be simply seen to follow LIFO(Last In First Out)/FILO(First In Last Out) order.
Stack Operations:
● push(): Insert a new element into the stack i.e just insert a new element at the
beginning of the linked list.
● pop(): Return the top element of the Stack i.e simply delete the first element from the
linked list.
Implement a stack using singly linked list
To implement a stack using the singly linked list concept, all the singly linked list operations
should be performed based on Stack operations LIFO(last in first out) and with the help of that
knowledge, we are going to implement a stack using a singly linked list.
So we need to follow a simple rule in the implementation of a stack which is last in first out and
all the operations can be performed with the help of a top variable.
1. push() Function
The push function adds an element to the top of the stack. To implement this function
with a singly linked list(insertion at beg), we first check if the list is empty. If it is, we
make the newnode the top of the list. If the list is not empty, we make the next of the
newnode point to the top of the list and then make the newnode the new top of the list.
Algorithm:
2. pop() Function
The pop function removes the topmost element of the stack. To implement this
function with a singly linked list, we first check if the list is empty. If it is, we return
NULL. If there is only one node in the list, we remove the top node and return
NULL. If there is more than one node in the list, we create a temp and make it point
to the top. Then, we make the 2nd node our new top by doing top = top → next.
Finally, we delete (temp).
Algorithm:
The above pictorial representation of the stack data structure shows how a stack data structure
works. We can insert or remove the data from only one side (left side from the above figure).
When we insert data to the stack we call it Push & when we remove data from it we call it Pop
and the last element that we inserted to the stack is knows as the top of the stack.
Applications of Stacks:
There are many applications of stacks, in this practical we will study following::
1. Conversion of infix to postfix expression
2. Conversion of infix to prefix expression
3. Evaluation of postfix expression
4. Evaluation of prefix expression
Conversion of infix to postfix expression:
The following algorithm transform the infix expression Q into its equivalent postfix expression
P. It uses a stack to temporary hold the operators and left parenthesis. The postfix expression will
be constructed from left to right using operands from Q and operators popped from STACK.
Conversion of infix to prefix expression: The following algorithm transform the infix
expression Q into its equivalent prefix expression P. It uses a stack to temporary hold the
operators and right parenthesis. T
Evaluation of postfix expression:
If P is an arithmetic expression written in postfix notation. This algorithm uses STACK to hold
operands, and evaluate P.
Evaluation of prefix expression: If P is an arithmetic expression written in prefix notation. This
algorithm uses STACK to hold operands, and evaluate P. We have to traverse it from left to
right..
Algorithm
Conclusion: We have studied, implemented stack and its applications.
