Data Structures with Algorithms 23MCA103

Module-1: Classification of Data Structures

• Classification of Data Structures:

— Primitive and Non- Primitive
— Linear and Non linear
— Data structure Operations

• Stack:
— Definition
— Representation
— Operations and Applications:
o Polish and reverse polish expressions
o Infix to postfix conversion
o Evaluation of postfix expression
o Infix to prefix conversion
o Postfix to infix conversion

1
Data Structures with Algorithms 23MCA103

1. Classification of Data Structures

• Data Structure
Definition:
“A data structure is a storage that is used to store and organize data. It is a way of
arranging data on a computer so that it can be accessed and updated efficiently.”
• Data Structures in C are used to store data in an organised and efficient manner.
• The C Programming language has many data structures like an array, stack, queue, linked list,
tree, etc.
• A programmer selects an appropriate data structure and uses it according to their
convenience.

Data structure

Primitive data-structure Non-Primitive data-structure

int
Linear data-structure Non-Linear data-structure
char
Array Tree
float
structure
Pointer
Sets

stack Tables

Linked List

2
Data Structures with Algorithms 23MCA103

1. Primitive Data Structures

The primitive data types are the basic data types that are available in the system.
Example: int, float, double, char

2. Non- Primitive Data Structures: classified as Linear and Nonlinear.

Linear Data structure: Data structure in which data elements are arranged sequentially and each
element is connected to its previous and next adjacent element. Such data structures are
easy to implement. In computer memory data will be stored in sequentially.
Example: Array, Stack, Queue, Linked List etc.

Non-Linear Data structure: Data structures where data elements are not arranged
sequentially or linearly are called non-linear data structures.
Example: Tree, Graph

Following are the important differences between Linear Data Structures and Non-linear Data Structures.

Sr. No. Key Linear Data Structures Non-linear Data

Structures

Data elements are sequentially Data elements are

1 Data Element connected, through a single run hierarchically connected and
Arrangement are present at various
levels.

2 Levels All data elements are present at a Data elements are present
single level. at multiple levels.

Non-linear data structures

3 Implementation Linear data structures are easier to are difficult to understand and
complexity implement.
implement as compared to
linear data structures.

3
Data Structures with Algorithms 23MCA103

Non-linear data structure

4 Traversal Linear data structures can be traversed are not easy to traverse and
completely in a single run. needs multiple runs to be
traversed completely.

5 Memory Linear data structures are not very Non-linear data structures use
utilization
memory friendly and are not utilizing memory very efficiently.
memory efficiently.
6 Examples
Graph, Map, Tree.
Array, List, Queue, Stack.

4
Data Structures with Algorithms 23MCA103

• Data structure Operations

Basic operations can be performed on the data structures:
Traversing-
It is used to access each data item exactly once so that it can be processed.

Searching-
It is used to find out the location of the data item if it exists in the given collection of
data items.

Inserting-
It is used to add a new data item in the given collection of data items.

Deleting-
It is used to delete an existing data item from the given collection of data items.

Sorting-
It is used to arrange the data items in some order i.e., in ascending or descending
order in case of numerical data and in dictionary order in case of alphanumeric data.

Merging-
It is used to combine the data items of two sorted files into single file in the sorted form.

5
Data Structures with Algorithms 23MCA103

2. Stack

• Definition:

“A stack is a Linear collection of items in which all additions and deletions are restricted to one
end, called the top”.

A stack is a linear data structure in which all the insertion and deletion of data or you can say its
values are done at one end only, rather than in the middle. Stacks can be implemented by using
arrays.

• Stack Representation and Operations on Stack

Figure 2.1: Operations on stack

• Properties of stack:

— Stack is an abstract data type with a predefined capacity.

— Stack uses LIFO structure (Last in — First out)
— Stack is an ordered list of similar data type.

• Basic stack operations

Push: Insert new elements onto the top of Stack.
Pop: Remove an element from the top of stack.
isEmpty: True if stack is empty.
Display : Display the contents of the stack.

6
Data Structures with Algorithms 23MCA103

Push()
 Inserting an element into the stack is known as push operation.
 Only one item is inserted at a time and item has to be inserted only from the top of the stack.
 When the elements are being inserted there is possibility of stack being full.
 Once the stack is full, it is not possible to insert any element.
 Trying to insert an element, even when the stack is full result in stack overflow.
 Hence while inserting element into the stack we must check for overflow condition.
 Example: Stack contents after inserting 4 items 30,20,25 and 10 one after the other with a MAX 4.
MAX is a stack size.

Sequence of insertion operations

C function for PUSH() operation:

void push( int * stack, int item )

if(top ==MAX-1)
{
printf(”\n STACK OVERFLOW ..”);
}
stack [++top] = item;
printf( ”\n . . Element pushed Successfully. . ” ) ;
}

7
Data Structures with Algorithms 23MCA103

Pop()
 Deleting an element from top of the stack.
 Only one item is deleted at a time and item has to be deleted only from the top of the stack.
 When the elements are being deleted there is a possibility of stack being empty.
 Once the stack is empty, it is not possible to delete any element.
 Trying to delete any element, even when the stack is empty results in Stack Underflow.
 Hence while deleting element from the stack we must check for underflow condition.
 Example: Performing pop operation when stack already contains 30, 20, 25 and 10

Sequence of deletion operations

C function for POP() operation

int pop(int *stack)

{
int item;

if(top == -1)
{
printf(“\n .. STACK UNDERFLOW …”);
return 0;
}

item = stack[top --];

return item;
}

8
Data Structures with Algorithms 23MCA103

Q1. What is stack? What are the basic operations on stack?

Q2. Write a program to implement stack operation using array as a data structure (without
using Structure).
Implement following conditions on stack.
1. Stack overflow
2. Stack underflow
3. Stack empty
4. Display
/* Stack imp1ementat1on */
#include<stdio.h›
#include<conio.h>
#include<stdlib.h>

//function declaration

void push(int *, 1nt) ;

int pop( int * ) ;
void disp1ay( int * ) ;

#define Max 3
int top=-1; //global variable

void main( )

int stack[MAX] ; //local variables

int choice, item; //local variables

while(1)
{
printf(”\n\n Stack Operations :\n™);
printf(”\n 1. Push. ”);
printf(”\n 2. Pop.”);
printf(”\n 3. Display. ”);
printf(”\n 4. (or any other) Exit... ”);

printf(”\n\n Enter your choice: ”);

scant( "'%d ", &choice ) ;

6
Data Structures with Algorithms 23MCA103

switch(choice) //it will match choice value with case value

{
case 1 :
printf( "\ n Enter the eleme nt to be pushed: " ) ;
scanf( "'%d", &item) ;
push( stack, item) ; //function call
break;

case 2 :
item = pop(stack); //function call
if( item)
//popped item value will be displayed
printf( "\ n Popped item is : %d “, item) ;

break;

case 3 :
display(stack); //function call

break;

default: exit(0);
}

// end of main function

/* function definition section*/

void push( int * stack, int item )

if(top ==MAX-1)
{
printf(”\n STACK OVERFLOW ..”);
}
stack [++top] = item;
printf( ”\n . . Element pushed Successfully. . ” ) ;
}

7
Data Structures with Algorithms 23MCA103

//function definition
int pop(int *stack)
{
int item;

if(top == -1)
{
printf(“\n .. STACK UNDERFLOW …”);
return 0;
}

item = stack[top --];

return item;
}

/* Display the content of stack*/

void display(int *stack)
{
int temp;

if(top == -1)
{
printf(“\n .. Stack is Empty ..”);
return;
}

printf(“\n The contents of the stack are: \n”);

for(temp = top; temp >=0; temp-- )

printf(“%d”, stack[temp]);

return;

8
Data Structures with Algorithms 23MCA103

2.1. Applications of Stack

1. Infix to postfix conversion

2. Evaluation of postfix expression
3. Infix to prefix conversion
4. Postfix to infix conversion
5. Recursion
6. Reversing data
7. Compilers
8. Browsers
9. Backtracking steps

2.2. Polish and reverse polish expressions

• Arithmetic Expression:
— An expression is defined as a number of operands combined using several operators.

• Notations (Types/Forms) of Arithmetic Expression:

1. Infix Notation
2. Polish Notation (Prefix expression)
3. Reverse Polish Notation (Postfix expression)

1. Infix Notation
• Form: “operator is placed in-between the two operands”
• Example: A + B, 5 — 6

2. Polish Notation

3. (Prefix expression)
• Prefix notation was introduced by the “Polish logician Lukasiewicz”, and is
sometimes called “Polish notation”.
• Form: “operator is placed in beginning of the two operands”

• Example: +AB, - 5 6

9
Data Structures with Algorithms 23MCA103

4. Reverse Polish Notation (Postfix expression)

• Postfix notation is also called "Reverse Polish Notation - RPN”.

• Form: "operator is placed in end of the two operands”

• Example: AB+, 56-

To evaluate the expression

Infix expression:
• You need to check operator precedence and Associativity.
• Brackets () will be included.
• For Example: (a+b+c*d)
• Multiplication and Division are done before addition and subtraction.
• Associativity for arithmetic operator is from left to right.

Prefix and Postfix notation:

• No need operator precedence and Associativity, as it is included in expression itself.
• No brackets () are required.
Example: +-AC, 57*

• Priority table from highest to lowest

No Operator Meaning
1 $ or ^ Exponentiation
2 *, / Multiplication and division
3 +, - Addition and subtraction

Infix Expression:
Example: 2+3*4 = 2+12= 14.

1. 5+3*4/2*12

2. 3*(4%2)/2

3. 3*4+5*6

4. 3*(4+5)*6

10
Data Structures with Algorithms 23MCA103

Conversion between expression notations

Steps to Convert from Infix to prefix and postfix:

1. Step by step Parenthesize the expression using the precedence and Associativity rules.

2. At each step convert the parenthesized infix expression to prefix or postfix as needed.

3. Repeat step 1 and 2 till all the operators are transformed.

Convert the following expressions from Infix to prefix anal postfix:

Infix Prefix Postfix

A+B*C+D A+(B*C)+D A+(B*C)+D

(A+(*BC)) +D ((A+(BC*))+D
( (+A*BC) + D ((ABC*+)+D)

++A*BCD ABC*+D+
A * B + C *D

A+B/C$D- E* (F+ G)

11
Data Structures with Algorithms 23MCA103

2.4. Application of Stack: 1. Infix-to-Postfix Conversion

• Steps to convert an Infix to postfix expression

1. Scan all the character/symbol from left to right in the infix expression.
2. If the scanned symbol is a left bracket ‘(‘ , push it into stack.
3. If the scanned symbol is an operand add it to postfix expression.
4. If the scanned symbol is the operator and the stack is empty or contains the ‘(’, ‘)’ symbol,
push the operator into the stack.
5. If the scanned symbol is the operator and the stack is not empty, check the priority or
precedence
i) If priority of symbol is > priority of the operator presents in the top of the stack,
then the push operator into the stack.
ii) If priority of symbol is < priority of the operator presents in the top of the stack,
then pop the operator from the stack and add it to the postfix expression.
Go to Step (i)
iii) If priority of symbol is == priority of the operator presents in the top of the stack,.
Use associativity rule.
a) If the operators are Left to right associative then pop and add it to postfix
expression. Go to step (i)
b) If the operators are Right to left associative then push the operator into the
stack.

6. If scanned symbol is right bracket ’)’, pop the stack and print all output string character until
‘(‘ is encountered and discard both the brackets.
7. After reading all the symbols, if stack is not empty pop and add it to the postfix expression.

• Algorithm
1. Set operator stack to empty.
2. Symbol = (Scan/Read the infix expression from left to right one character at a time).
a) If ( Symbol = operand )
— Add symbol to postfix
b) If ( Symbol = ‘(’ )
— Push symbol to stack

12
Data Structures with Algorithms 23MCA103

c) If ( Symbol = ‘)’)
— while ( StackTop !=’(’)
Pop stack and add to postfix
— Remove open brace from stack and discard
d) Otherwise If ( Symbol = operator)
— while (precedence(Symbol) <= precedence(StackTop) )
Pop top operator and add it to postfix string
— Push symbol to stack. // as precedence of Symbol is High

4. Repeat step-2 till no more symbols in string. ( till end of string )

5. Pop all elements from stack till stack becomes empty and add to the Postfix Expression.

Priority Table:
case '#': return 0;
case '(': return 1;
case '+':
case '-': return 2;
case ' * ' :
case '/': return 3;
case ' $' :
case ‘^’ : return 4;

13
Data Structures with Algorithms 23MCA103

Evaluate the following Infix Expression to Postfix Expression using Stack.

Convert the Infix expression to Postfix Expression :

(A + B) * C - (D - E)

Steps Symbol Action Stack Postfix

1 ( Push
2 A Add to postfix ( A
3 + Push (,+ A
4 B Add to postfix (, + AB
5 ) Pop (, + AB +
6 ) Pop ( AB +
7 * Push * AB +
8 C Add to postfix * AB + C
9 Pop *
AB+C*
11 ( Push -, ( AB + C *
12 D Add to postfix -, ( AB + C * D
13 - Push -, (, - AB + C * D
14 E Add to postfix -,(, - AB + C * DE
15 ) Pop -, ( AB + C * DE -
16 ) Pop — AB + C * DE -
17 Pop Empty AB + C * DE - -

The Postfix Expression is : A B + C * D E - -

Infix Expressions
1. ((A*(B+D)/E) – (F *(G+H)/K))
2. A+(B*C)/D
3. ( A + B ) * ( C — D ) ^ E * F

13
Data Structures with Algorithms 23MCA103

write of C program to convert infix expression to postfix using function

#include<stdio.h>
#include<ctype.h›

#define SIZE 10 /* Size of Stack */

#include

char stack[SIZE]; /’GfobnfdeofnrnRoils ’/

int top = -1;
void infixToPostfix(char *, char*);
{
void push(char symbol)
{
stack[++top ] = symbo1;
}

char pop()
{
return (stack[top--]);
}

int priority (char op) {

switch (op)
{
case '#': return 0;
case '(': return 1;
case '+':
case '-': return 2;
case '*':
case '/': return 3;
}
}
void main()
{
char infix[50], postfix[50];
printf ( ” \n Read the infix expression ? ” ) ;
scanf( ”%s ” , infix) ;

infixToPostfix(infix, postfix); //function call

printf(”\n Postfix Expression : %s”, postfix);
}

15
Data Structures with Algorithms 23MCA103

2.5. Application of Stack:

2. Evaluation of Postfix Expression

• Steps for evaluation of postfix expression.
1. Scan the symbol of postfix expression from left to right.
2. If the scanned symbol is an operand, push it onto the stack.
3. If the scanned symbol is an operator, pop two elements from the stack. The first popped
element is operand2 and the second popped element is operand1.
i. Perform the indicated operation
ii. Push the result onto the stack
4. Repeat the above procedure till the end of the expression.

• Algorithm
1. Set Operand Stack to empty
2. Symbol = (Read/Scan the postfix input from left to right one character at a time).
a. If (symbol = operand)
— Push symbol to stack.
b. If (symbol = operator)
— Pop first operand2 and then operand1
— Find result by Applying the operator on operand1 operator operand2.
— Push the result back to stack.
3. Repeat step-2 till end of in put string.
4. Pop the final result and Return

Example:
456*+
62 3* + 5 –
54*65*-

Expression: 456*+
16
Data Structures with Algorithms 23MCA103

Steps Symbol Action/ Stack Calculate

Operation
1 4 Push 4
2 5 Push 4,5
3 6 Push 4,5,6
4 * Pop(2 elements) 4 5*6=30
& evaluate
5 Push result 4, 30
(30)
6 + Pop(2 element) 4+30=34
& evaluate
7 Push result 34
(34)
8 Null No more elements Empty 34
(Pop)

17
 Data Structures with Algorithms 23MCA103

C program to evaluate postfix expression

/* evaluation of postfix expression */

#include <stdio.h>
#include <string.h>
#include <math.h>
#define MAXSIZE 30

int s[MAXSIZE];
int top=-1;
int isdig(char);

int main()
{
char symbol,postfix[30];
int a,b,res,i;
void push(int);
int pop();
int op(int, int, char);
printf(" Enter a Postfix expression\n");
scanf("%s",postfix);
for(i=0;i<strlen(postfix);i++)
{
symbol=postfix[i];
if(isdig(symbol))
push(symbol-'0');
else
{
a = pop();
b = pop();
res = op(b,a,symbol);
push(res);
}
}
printf("The result of the expression is = ");
printf("%d\n",pop());

18
 Data Structures with Algorithms 23MCA103

return 0;
}
int pop()
{
if(top!=-1)
return s[top--];
else
{
printf("Stack underflow\n");
return 0;
}
}
void push(int item)
{
if(top!= MAXSIZE-1)
s[++top]=item;
else
printf("\nStak Overflow\n");
}
int op(int op1,int op2,char symbol)
{
switch(symbol)
{
case '+': return op1 + op2;
case '-': return op1 - op2;
case '*': return op1 * op2;
case '/': return op1 / op2;

}
}
int isdig(char symbol1)
{
return (symbol1>='0' && symbol1<='9');
}

19
Data Structures with Algorithms 23MCA103

2.6. Application of Stack:

3. Infix-to-Prefix Conversion
• Steps to convert infix to prefix expression
1. First, reverse the infix expression given in the problem.
2. Scan the expression from left to right.
3. Whenever the operands arrive, print them.
4. If the operator arrives and the stack is found to be empty, then simply push the operator
into the stack.
5. If the incoming operator has higher precedence than the TOP of the stack, push the
incoming operator into the stack.
6. If the incoming operator has the same precedence with a TOP of the stack, push the
incoming operator into the stack.
7. If the incoming operator has lower precedence than the TOP of the stack, pop, and print
the top of the stack. Test the incoming operator against the top of the stack again and
pop the operator from the stack till it finds the operator of a lower precedence or same
precedence.
8. If the incoming operator has the same precedence with the top of the stack and the
incoming operator is ^, then pop the top of the stack till the condition is true. If the
condition is not true, push the ^ operator.
9. When we reach the end of the expression, pop, and print all the operators from the top
of the stack.
10. If the operator is ')', then push it into the stack.
11. If the operator is '(', then pop all the operators from the stack till it finds ‘)’ closing
bracket in the stack.
12. If the top of the stack is ')', push the operator on the stack.
13. At the end, reverse the output.

20
Data Structures with Algorithms 23MCA103
• Algorithm

1. Set operator Stack to empty.

2. Read/Scan infix expression.
3. Reverse infix expression.
4. Symbol = (Read the reversed infix expression from left to right one character at a
time).
a) If(symbol = open brace)
— Pop each operator while closing brace is encountered and add to Output string.
— Discard both the braces if popped symbol is closing brace.
b) If (symbol = closing braces)
— Push to stack
c) if ( Symbol ==operand)
— Add to Output string
d) if (Symbol ==operator)
— if precedence(symbol) >
precedence(stackTop) push symbol
to stack
— while precedence(symbol) <=
precedence(stackTop) pop and add to
postfix

5. Repeat step-4 till no more symbols in string. ( till end of string )

6. Pop all elements from stack till stack becomes empty and add to the output string.

7. Reverse the Output string and return as prefix String.

21
Data Structures with Algorithms 23MCA103

Convert the infix Expression to Prefix: (A+B^C)*D+E^S

Reverse the infix Expression : S^E+D*(C^B+A)
Steps Symbol Action Stack Expression

S S
1
^ Push to stack ^ S
2
3 E SE
+ Compare(^,+), pop ^, push + SE^
4
incoming operator into stack
5 D SE^D
* Compare(+,*) + is not highest + * SE^D
6
Precedence than *, so push to
stack.
7 ( Push + *( SE^D
8 C + *( SE^DC
9 ^ +*(^ SE^DC
Push
10 B +*(^ SE^DCB
11 + Compare(^,+), pop ^, push +*(+ SE^DCB^
incoming operator into stack
12 A +*(+ SE^DCB^A
13 ) Pop + +* SE^DCB^A+
14 Pop remaining element from SE^DCB^A+*+
the stack

Prefix expression = reverse symbol = +*+A^BCD^ES

Example 2: A + B * C - ( D - E )

22
Data Structures with Algorithms 23MCA103
Data Structures with Algorithms

2.7 Application of Stack:

4. Postfix to Infix Conversion

• Steps to convert postfix to infix expression

1. Read the symbol from the input .based on the input symbol go to step 2 or 3.

2. If symbol is operand then push it into stack.

3. If symbol is operator then pop top 2 values from the stack.

4. This 2 popped value is our operand .

5. Create a new string and put the operator between this operand in string.

6. Push this string into stack.

7. At the end only one value remain in stack which is our infix expression.

• Algorithm
1. Scan operand stack to empty
2. Symbol = (scan Postfix String from Left to Right till null).
a. If(Symbol = Operand) then
i. Push it on to the Stack.
b. If(Symbol = Operator) then
i. Pop Operand 1 and Operand 2
ii. Concatenate them with operator using Infix notation.
iii. Use parentheses properly to ensure correct order of operators.
iv. Push the resultant expression on to the Stack.
3. Repeat the above steps till the Postfix string is not scan ned completely.
4. Pop the stack and return as infix expression.

23
Data Structures with Algorithms 23MCA103

Convert Postfix expression to infix: A B * C D * -

Steps Symbol Action Stack
1 A Push A
2 B Push A, B
3 * Pop op1, op2 and concatenate (A* B)
with *
4 C Push (A* B) , C
5 D Push (A* B) , C, D
6 * Pop op1, op2 and concatenate (A* B) , (C*D)
with *
7 - Pop op1, op2 and concatenate ( (A*B) - (C*D))
with -

8 Print ( (A*B) - (C*D))

Infix string = ( ( A * B ) - ( C * D ) )

24
Data Structures with Algorithms 23MCA103

Module-1: Question Bank Marks

1
Define Data structures. Explain different types of data structures. 8
2 What is a stack? List and Explain, implement the basic operations on stack. 8
4 What is a stack? Explain with diagram. Write C representation of stack. 6
5 Write an algorithm to implement stack using array. 8
6 Convert each of the following infix expression to postfix expression using 6
stack.
e) (A+B)*(C^(D—E)+F)—G
f) (A+B)*(C—D)^E*F
g) A + ( ( ( B — C ) * ( D — E ) + F ) / G ) + H
7 Convert any two of the following into its prefix and postfix form without stack. 6
i) ( A + B ) * C — D $ E * F
ii) A — B / C * D $ E
iii) (A + B ) $ C + D - E ) * F
8 Show the detailed 6
"623 + - 382 / + * 2 — 3 + " and evaluate the postfix expression using stack.
9 Write an algorithm to evaluate a postfix expression. Trace the algorithm with stack 8
contents for the following expression.
a) A B C + * C B A - + * with A=1, B=2, C=3.
10 Write an algorithm to convert from infix to reverse Polish notation. 8
11 Write a C program to check whether a string is palindrome or not using stack. 8
12 Explain with algorithm how stack is applied for evaluating a postfix arithmetic 8
expression.
13 Write an algorithm to evaluate postfix expression. 8
14 Write a short note on applications of stack. 5
15 Define Prefix and Postfix expressions. Write a program to convert infix to postfix expressions. 8

16 Write an algorithm to convert an infix expression to postfix. Trace the algorithm for 10
following infix expression ( ( A — ( B + C ) ) * D ) $ ( E + F )
17 Write an algorithm to evaluate a Postfix expression. Trace the algorithm for 10
following postfix expression showing contents of stack: 6 2 3 + - 3 8 2 / + * 2 $ 3 +

25