“Data Structures”
Unit-II Linear Data Structures:- Stack
B Tech. (Computer Engineering & AIML)
Semester-III
By: Dr. Mayank Sohani
Structure
• A structure is therefore a collection of
variables under a single name. The variables
within a structure are of different data types
and each has a name that is used to select it
from the structure.
Structure Declaration
struct student
{
int r_no;
char name[20];
char course[20];
float fees;
} stud1, stud2;
Or
struct student stud1;
For example, we can initialize a student
structure by writing,
STRUCTURES AND FUNCTIONS
Passing Individual Members
Passing the Entire Structure
Passing Structures through Pointers
Stacks
• Stack is an important data structure which
stores its elements in an ordered manner.
• You must have seen a pile of plates where one
plate is placed on top of another as shown in
Fig.
• Now, when you want to remove a plate, you
remove the topmost plate first.
• Hence, you can add and remove an element
(i.e., a plate) only at/from one position which is
the topmost position.
Stacks
• A stack is a linear data structure which uses the same principle, i.e., the
elements in a stack are added and removed only from one end, which
is called the TOP. Hence, a stack is called a LIFO (Last-In-First-Out) data
structure, as the element that was inserted last is the first one to be
taken out.
• Now the question is where do we need stacks in computer science?
• The answer is in function calls. Consider an example, where we are
executing function A.
• In the course of its execution, function A calls another function B.
Function B in turn calls another function C, which calls function D.
System stack in the case of function calls
System stack when a called function returns to the calling
function
Array Representation Of Stacks
• In the computer’s memory, stacks can be represented as a linear array.
• Every stack has a variable called TOP associated with it, which is used to
store the address of the topmost element of the stack.
• It is this position where the element will be added to or deleted from.
There is another variable called MAX, which is used to store the
maximum number of elements that the stack can hold.
• If TOP = NULL, then it indicates that the stack is empty and if TOP = MAX–
1, then the stack is full. (You must be wondering why we have written
MAX–1. It is because array indices start from 0.) Look at Fig.
Operations On a Stack
• A stack supports three basic operations: push, pop,
and peek.
• The push operation adds an element to the top of
the stack and
• The pop operation removes the element from the
top of the stack.
• The peek operation returns the value of the
topmost element of the stack.
Operations On a Stack
• Push Operation
– The push operation is used to insert an element into the stack. The
new element is added at the topmost position of the stack.
However, before inserting the value, we must first check if
TOP=MAX–1, because if that is the case, then the stack is full and no
more insertions can be done. If an attempt is made to insert a value
in a stack that is already full, an OVERFLOW message is printed.
Consider the stack given in Fig.
Operations On a Stack
• Push Operation
– To insert an element with value 6, we first check if
TOP=MAX–1. If the condition is false, then we increment
the value of TOP and store the new element at the
position given by stack[TOP]. Thus, the updated stack
becomes as shown in Fig.
Algorithm to Insert an Element in a Stack
• In Step 1, we first check for
the OVERFLOW condition.
• In Step 2, TOP is
incremented so that it
points to the next location
in the array.
• In Step 3, the value is stored
in the stack at the location
pointed by TOP.
Operation on a Stack
• Pop Operation
– The pop operation is used to delete the topmost element from the
stack. However, before deleting the value, we must first check if
TOP=NULL because if that is the case, then it means the stack is
empty and no more deletions can be done. If an attempt is made to
delete a value from a stack that is already empty, an UNDERFLOW
message is printed. Consider the stack given in Fig.
Operation on a Stack
• Pop Operation
– To delete the topmost element, we first check if TOP=NULL. If the condition is false,
then we decrement the value pointed by TOP. Thus, the updated stack becomes as
shown in Fig.
Algorithm to Delete an Element from a Stack
• In Step 1, we first check for
the UNDERFLOW condition.
• In Step 2, the value of the
location in the stack pointed
by TOP is stored in VAL.
• In Step 3, TOP is
decremented.
Operation on a Stack
• Peek Operation
– Peek is an operation that returns the value
of the topmost element of the stack without
deleting it from the stack. The algorithm for
Peek operation is given in Fig.
– However, the Peek operation first checks if
the stack is empty, i.e., if TOP = NULL, then
an appropriate message is printed, else the
value is returned. Consider the stack given in
Fig.
– Here, the Peek operation will return 5, as it
is the value of the topmost element of the
stack.
APPLICATIONS OF STACKS
Following problems where stacks can be easily applied for a simple and
efficient solution.
• Reversing a list
• Parentheses checker
• Conversion of an infix expression into a postfix expression
• Evaluation of a postfix expression
• Conversion of an infix expression into a prefix expression
• Evaluation of a prefix expression
• Recursion
• Tower of Hanoi
Reversing a List
• A list of numbers can be reversed by reading
each number from an array starting from the
first index and pushing it on a stack. Once all
the numbers have been read, the numbers
can be popped one at a time and then stored
in the array starting from the first index.
Reversing a List
Implementing Parentheses Checker
• Stacks can be used to check the validity of
parentheses in any algebraic expression. For
example, an algebraic expression is valid if for every
open bracket there is a corresponding closing
bracket.
➢ For example, the expression (A+B} is invalid but an
expression {A + (B – C)} is valid.
Implementing Parentheses Checker
Evaluation of Arithmetic Expression
Polish Notations-
Infix, postfix, and prefix notations are three different but equivalent notations of
writing algebraic expressions.
• While writing an arithmetic expression using infix notation, the operator is placed
in between the operands. For example, A+B; here, plus operator is placed
between the two operands A and B.
• Although it is easy for us to write expressions using infix notation, computers find
it difficult to parse as the computer needs a lot of information to evaluate the
expression. Information is needed about operator precedence and associativity
rules, and brackets which override these rules.
• So, computers work more efficiently with expressions written using prefix and
postfix notations.
Evaluation of Arithmetic Expression
Polish Notations-
➢ Postfix notation was developed by Jan Łukasiewicz who was a Polish logician,
mathematician, and philosopher. His aim was to develop a parenthesis-free
prefix notation (also known as Polish notation) and a postfix notation, which is
better known as Reverse Polish Notation or RPN.
• In postfix notation, as the name suggests, the operator is placed after the
operands. For example, if an expression is written as A+B in infix notation, the
same expression can be written as AB+ in postfix notation. The order of
evaluation of a postfix expression is always from left to right. Even brackets
cannot alter the order of evaluation.
– The expression (A + B) * C can be written as:
[AB+]*C
AB+C* in the postfix notation
Evaluation of Arithmetic Expression
Polish Notations-
➢ Postfix notation-
✓ A postfix operation does not even follow the rules of operator precedence. The
operator which occurs first in the expression is operated first on the operands. For
example, given a postfix notation AB+C*. While evaluation, addition will be performed
prior to multiplication.
✓ Thus we see that in a postfix notation, operators are applied to the operands that are
immediately left to them. In the example, AB+C*, + is applied on A and B, then * is
applied on the result of addition and C.
✓ Although a prefix notation is also evaluated from left to right, the only difference
between a postfix notation and a prefix notation is that in a prefix notation, the
operator is placed before the operands. For example, if A+B is an expression in infix
notation, then the corresponding expression in prefix notation is given by +AB.
Evaluation of Arithmetic Expression
Polish Notations-
➢ Postfix notation-
✓ While evaluating a prefix expression, the operators are applied to the operands that
are present immediately on the right of the operator. Like postfix, prefix expressions
also do not follow the rules of operator precedence and associativity, and even
brackets cannot alter the order of evaluation.
Convert the following infix expressions into postfix expressions.
(a) (A–B) * (C+D)
(b) (A + B) / (C + D) – (D * E)
Solution:- (a) [AB–] * [CD+]
AB–CD+*
(b) [AB+] / [CD+] – [DE*]
[AB+CD+/] – [DE*]
AB+CD+/DE*–
Conversion of an Infix Expression into a Postfix Expression
• Let I be an algebraic expression written in infix notation. I may contain
parentheses, operands, and operators. For simplicity of the algorithm we
will use only +, –, *, /, % operators. The precedence of these operators
can be given as follows:
Higher priority *, /, %
Lower priority +, –
• No doubt, the order of evaluation of these operators can be changed by
making use of parentheses.
• For example, if we have an expression A + B * C, then first B * C will be
done and the result will be added to A. But the same expression if
written as, (A + B) * C, will evaluate A + B first and then the result will be
multiplied with C.
Convert the following
infix expressions into prefix expressions.
(a) (A + B) * C
(b) (A–B) * (C+D)
(c) (A + B) / ( C + D) – ( D * E)
Solution:-
(a) (+AB)*C
(c ) [+AB] / [+CD] – [*DE]
*+ABC
[/+AB+CD] – [*DE]
(b) [–AB] * [+CD]
–/+AB+CD*DE
*–AB+CD
Algorithm to convert an infix notation to postfix
notation
Conversion of an Infix Expression into a Postfix Expression
• Convert the following infix
expression into postfix
expression using the
algorithm :
A – (B / C + (D % E * F) / G)* H
Evaluation of a Postfix Expression
Infix to Postfix
•
Conversion of an Infix Expression into a Prefix Expression
Evaluation of a Prefix Expression
Infix to Prefix & Postfix
Recursion
Recursion
Now if you look at the problem carefully, you can see that we
can write a recursive function to calculate the factorial of a
number. every recursive function must have a base case and
a recursive case. For the factorial function,
• Base case is when n = 1, because if n = 1, the result will be
1 as 1! = 1.
• Recursive case of the factorial function will call itself but
with a smaller value of n, this case can be given as
factorial(n) = n × factorial (n–1)
Factorial of a given number using recursion
Tower of Hanoi
• The tower of Hanoi is one of the main applications of
recursion. It says, ‘if you can solve n–1 cases, then you
can easily solve the nth case’.
• Look at Fig. which shows three rings mounted on pole A.
The problem is to move all these rings from pole A to pole
C while maintaining the same order. The main issue is that
the smaller disk must always come above the larger disk.
• We will be doing this using a spare pole. In our case, A is
the source pole, C is the destination pole, and B is the
spare pole. To transfer all the three rings from A to C, we
will first shift the upper two rings (n–1 rings) from the
source pole to the spare pole. We move the first two rings
from pole A to B as shown in Fig.
Tower of Hanoi
• To summarize, the solution to our problem of moving n rings from A to C using B as spare
can be given as:
Base case: if n=1
Move the ring from A to C using B as spare
Recursive case:
Move n – 1 rings from A to B using C as spare
Move the one ring left on A to C using B as spare
Move n – 1 rings from B to C using A as spare
Tower of Hanoi