Data Structures MMC203

Module – 1: Introduction to Data Structures and Algorithms

Introduction to Data Structures and Algorithms:

• Basic Concepts:
➢ Definition and importance of data structures,

• Algorithm analysis:
➢ Time and space complexity,
➢ Big O notation.

• Arrays:
➢ Definition,
➢ operations: Insertion, deletion, traversal,
➢ Multidimensional arrays,
➢ Applications of arrays.

• Stacks:
➢ Definition
➢ operations:
→ Push,
→ pop,
→ peek,
➢ Applications:
→ Expression evaluation,
→ Infix to postfix conversion
→ String Reversal
→ backtracking,
→ function calls.
→ Recursion

Dr. Vishwanath Murthy, Sahitya K, MCA, RNSIT 1

Data Structures MMC203
Module – 1: Introduction to Data Structures and Algorithms

1.1) Definition and importance of data structures

• Data structures Definition:

- Data structure is a way of organizing and storing data so that it can be accessed and
modified efficiently.
- Each type of data structure is optimized for specific tasks, and understanding when to use
which one is crucial for writing efficient code.

• Importance of data structures

- Without data structures, managing large amounts of data efficiently would be difficult. Data
structures help us to optimize our code and make it more efficient.
- Data structures are essential for two main reasons:
o They make the code more efficient, and
o They make the code easier to understand.

Datatype Data structure

Data type specify that a variable can hold Data structure, however, is a collection of
single type of value. various data types.
Data types specify the type of value and basic Data structures specify methods of organizing
operations that can be applied on it (like and storing data in a way that enables efficient
arithmetic operation). access, retrieval, and manipulation.
We can directly assign values to the data type We need to use some special operations to assign
variables. Hence Data types are faster. values for the data structure (like push, pop).
Hence Data structures suffer from the problem of
time complexity.
A data type defines the type of value it can A data structure defines the collection of values
hold (e.g., integers, float) it can hold (e.g., integers, float)
Examples: int, float, double Examples: stacks, queues, tree

Dr. Vishwanath Murthy, Sahitya K, MCA, RNSIT 2

Data Structures MMC203
Module – 1: Introduction to Data Structures and Algorithms

1.2) Algorithm analysis

• What is algorithm:
- An algorithm is a finite sequence of well-defined instructions that can be used to solve a
computational problem.
- An algorithm is a set of instructions that is designed to accomplish a task.

• Characteristics of a good algorithm

✓ Clear and Unambiguous: Algorithm should be clear and unambiguous. Each of its steps
should be clear in all aspects and must lead to only one meaning.
✓ Well Defined Inputs: If an algorithm says to take inputs, it should be well-defined inputs.
✓ Well Defined Outputs: The algorithm must clearly define what output will be yielded and it
should be well-defined as well.
✓ Finiteness: The algorithm must be finite, i.e. it should not end up in an infinite loop or
similar.
✓ Feasible: The algorithm must be simple, generic and practical, such that it can be executed
upon will the available resources. It must not contain some future technology, or anything.
✓ Language Independent: The Algorithm designed must be language-independent, i.e. it must
be just plain instructions that can be implemented in any language, and yet the output will
be same, as expected.

Dr. Vishwanath Murthy, Sahitya K, MCA, RNSIT 3

 Data Structures MMC203
Module – 1: Introduction to Data Structures and Algorithms

1.2.1) Time and space complexity,

---------------------------------------------------------------------------------------------------
- Analysis of algorithms is important because using an inefficient algorithm could make our
program slow or even unworkable.
- To measure the performance of algorithms, we typically use time and space complexity
analysis instead of actual time.
• Why not actual time
- Due to the following reason, we will not look at the actual time (Execution time) an
implemented algorithm uses to run.
- The actual time depends on many factors:
o Programming language used
o Compiler or interpreter used
o Computer hardware on which algorithm is run
o Amount of data the algorithm is working on

• Time complexity
- Time complexity measures the execution time of an algorithm relative to input size.
- Quantifies the amount of time taken by an algorithm to run as a “function of the length
of the input”.
- Time complexity is the number of operations needed to run an algorithm on large
amounts of data.
- Example: Find the time complexity of an algorithm that finds smallest element in a given
array ‘A’.
Algorithm:

procedure getSmall (input: Array A[] with n elements)

small = A[0]
for (i = 1; i<n ; i++)
if (A[i] > small)
small = A[i]
return small;

In above algorithm, each value in the array must be compared at least one time. Every such
comparison can be considered an operation, and each operation takes a certain amount of
time. So the total time the algorithm needs to find the lowest value depends on the number of
values in the array.

Hence Time complexity for above algorithm is: O(n)

Dr. Vishwanath Murthy, Sahitya K, MCA, RNSIT 4

 Data Structures MMC203
Module – 1: Introduction to Data Structures and Algorithms

• Space complexity
- Space complexity measures the amount of memory an algorithm uses in relation to the
size of its input.
- This includes memory for input data, variables, and any additional storage used during
execution.
Key aspects of space complexity:
• Input space: The memory required to store the input data itself.
• Auxiliary space: The additional memory used by the algorithm during execution, such as
variables, data structures, or temporary storage.
• Big O notation: Used to describe how the memory usage grows as the input size increases,
similar to time complexity.

How to Calculate Space Complexity?

Calculating space complexity involves analyzing the memory usage of an algorithm by
considering both the fixed and variable parts of memory:
1. Identify the Fixed Part
Determine the memory required for constants, simple variables, and fixed-size data structures. This
part does not change with the size of the input.

2. Identify the Variable Part

Determine the memory required for dynamic data structures, recursion stack space, and temporary
variables. This part changes with the size of the input.

3. Sum the Fixed and Variable Parts

Add the memory required for the fixed part and the variable part to get the total space complexity.

Dr. Vishwanath Murthy, Sahitya K, MCA, RNSIT 5

 Data Structures MMC203
Module – 1: Introduction to Data Structures and Algorithms

1.2.2) Big O notation.

----------------------------------------------------------------------------------------------------------------------------
- In mathematics, Big O notation is used to describe the upper bound of a function.
- In computer science, Big O notation is used more specifically to find the worst case time
complexity for an algorithm.
- Big O notation uses a capital letter O with parenthesis O(), and inside the parenthesis there
is an expression that indicates the algorithm runtime. Runtime is usually expressed
using ’n’, which is the number of values in the data set the algorithm is working on.

Here is how time increases when the number of values ‘n’ increase for different algorithms:

• Best, Average and Worst Case

- Consider the algorithm that finds the lowest value in an array with n values:
o It requires ‘n’ operations to do so, and that is always the same.
o So, this algorithm has the same best, average, and worst-case scenarios.
- But for many other algorithms, if we keep the number of values- ‘n’ fixed, the runtime can
still change a lot depending on the actual values.
- Example: Linear search
o Worst case happens when the element to be searched (key) is not present in the array.
o Best case occurs when the (key) is present at the first location.
o Average case is calculated by taking sum of all the cases and dividing the sum by (n+1).
In Linear search example, best case and worst case depend on the key position in the array.
Algorithms work similarly: For the same amount of data, they can sometimes be slow and
sometimes fast. So, to be able to compare different algorithms' time complexities, we usually
look at the worst-case scenario using Big O notation.

Dr. Vishwanath Murthy, Sahitya K, MCA, RNSIT 6

Data Structures MMC203
Module – 1: Introduction to Data Structures and Algorithms

Ques: What are data structures? Explain the classification of data structures 10
Marks
with an example.

• Data structures:
− Data structure is a way of organizing and storing data so that it can be accessed and
modified efficiently.
− Example: Array is a data structure that organizes data sequentially in memory, so that it
can be accessed efficiently.

Data-structure

Linear data-structure Non-Linear data-structure

Array
Tree
Stack

Queue Graph

Linked List

Figure 1.1: Classification of Data structure

Data structures are classified as Linear and Nonlinear.

i) Linear data structure
a) Array
b) Stack
c) Queue
d) Linked list

ii) Non-Linear data structure

e) Tree
f) Graph

Dr. Vishwanath Murthy, Sahitya K, MCA, RNSIT 7

Data Structures MMC203
Module – 1: Introduction to Data Structures and Algorithms

i) Linear Data structure

a) Array
− An array is a fixed-size Linear data structure that can store a collection of elements of the
same type in sequential order.

arr 0 1 2 3
f10
f10 f14 f18 f22

b) Stack
− “A stack is a Linear data structure in which all insertion and deletions operations are
restricted to one end, called the top. Stack follows LIFO principle, with two major operations:
• push: Adds an element to top of the Stack, and
• pop: Removes an element from top of the Stack.

c) Queue
− A queue is an abstract data structure that has a linear collection of elements which follows
FIFO principle with two major operations:
• enqueue: Adds an element to rear of the queue.
• dequeue: Removes an element from front of the queue.

Dr. Vishwanath Murthy, Sahitya K, MCA, RNSIT 8

Data Structures MMC203
Module – 1: Introduction to Data Structures and Algorithms

d) Linked List
− Linked list is a Linear data structure that consists of nodes where each node contains a data
field and a reference(link) to the next node in the list

Head
f10

data link data link data link

NULL
f10

i) Non-Linear Data structure:

− In non-linear Data structures, data elements are arranged hierarchically. Because the
items are not stored sequentially, they cannot be traversed or retrieved in a single
iteration. Such data structures are not easy to implement.
− Example: Tree, Graph

Non Linear Data structure

e) Tree
Tree is a non-linear data structure which is a collection of
nodes connected by edges in hierarchical representation.

f) Graph
A graph G can be defined as a pair (V, E), where V is a set of
vertices, and E is a set of edges between the vertices.

Dr. Vishwanath Murthy, Sahitya K, MCA, RNSIT 9

Data Structures MMC203
Module – 1: Introduction to Data Structures and Algorithms

• Differences between Linear Data Structures and Non-linear Data Structures.

Sr. Linear Data Structures Non-linear Data Structures

No.

Elements are ordered in a linear and

1 Data elements are arranged hierarchically.
sequential manner.

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

Linear data structures Implementation is Non-linear data structures

3
relatively easier. Implementation is relatively complicated.

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

5 Memory utilization is not efficient. Use memory very efficiently.

6 Example: Array, Linked List, Queue, Stack. Example: Tree, Graph, Map.

1.3) Arrays

1.3.1) What are Arrays?

− Definition: An array is a data structure that stores a fixed-size, sequential collection of
elements of the same data type.
− Array syntax:

DataType arrayName[size];
− Example:
int arr[4];
float price[3];
− Memory diagram: for integer array.

arr 0 1 2 3
f10
f10 f14 f18 f22

Dr. Vishwanath Murthy, Sahitya K, MCA, RNSIT 10

Data Structures MMC203
Module – 1: Introduction to Data Structures and Algorithms

1.3.2) Operations: Insertion, deletion, traversal.

----------------------------------------------------------------------------------------------------------------------------
- The basic operations in the Arrays are insertion, deletion, and traversal.
o Insertion − Adds an element at the given index.
o Deletion − Deletes an element at the given index.
o Traversal − print all the array elements one by one.

i) Insert:
- An operation that inserts a key element into a given position in an existing array.
Algorithm: Insert element at give position
1. Input the key and position: Ask the user to Input the element and position where to
insert the new element.
2. Shift elements: Shift all elements to right by one index starting from the insertion
position and up to last element. This creates a space for the new element.
3. Insert the element: Place the new element at the specified position.
4. Update the element count: increment count of element (n) by 1.

Steps to insert an element at the specified position.

Before inserting 67 at index 3 ( size = 6)

Insert 67 at index 3 Size = 6

arr 0 1 2 3 4 5 6 7
f10 10 8 55 9 33 11
f10 f14 f18 f22 f26 f30 f34 f38

After inserting 67 at index 3 ( size = 7)

67 Shift elements to right

arr 0 1 2 3 4 5 6 7
f10 10 8 55 67 9 33 11
f10 f14 f18 f22 f26 f30 f34 f38

Size = 7

Dr. Vishwanath Murthy, Sahitya K, MCA, RNSIT 11

Data Structures MMC203
Module – 1: Introduction to Data Structures and Algorithms

Function to insert an element at a given position in an Array

void insert (int A[], int *n)

{
int pos, element, j
printf (“Input an element to be inserted to Array:”);
scanf (“%d”, &element);
printf (“Input position to insert the new element:”);
scanf (“%d”, &pos);

j = *n – 1;
while (j >= pos-1)
{
A[j+1] = A[j];
j--;
}
A[pos-1] = element;
*n = *n + 1;
}

Practice program: Homework

Modify the above program to satisfy the following:
1. Check if Array Full: Can’t insert if array is full.
2. Input the key and position: Ask the user to Input the element and position where to
insert the new element.
3. Check if the index is valid: Ensure the index is within the bounds of the array.
4. Determine the position: Identify the index where you want to insert the new
element.
5. Shift elements: Shift all elements to right by one index starting from the insertion
position and up to last element. This creates a space for the new element.
6. Insert the element and update count: Place the new element at the specified
position and increment count by 1.

Dr. Vishwanath Murthy, Sahitya K, MCA, RNSIT 12

Data Structures MMC203
Module – 1: Introduction to Data Structures and Algorithms

ii) Delete
- An operation that removes an element from a given location in an array.
• Algorithm: Remove element from given position
1. Input the position: Ask the user to input the position from where the element to be
removed.
2. Store element: before remove store array value at given position in variable ‘element’
3. Shift elements: Shift all elements to left by one index starting from the next to insertion
position and up to last element. This overwrites the element at given position.
4. Update count: Decrement count of elements (n) by 1.
5. Return element: return the value of the element that is removed from the array.

Steps to Remove an element from an array at a given position

Before removing element at position 4 (index3) ( size = 6)

arr 0 1 2 3 4 5 6 7
f10 10 8 55 9 33 11
f10 f14 f18 f22 f26 f30 f34 f38

Element at index 3 is ‘9’ Size = 6

After removing element (updated size = 5)

Shift elements to left

arr 0 1 2 3 4 5 6 7
f10 10 8 55 33 11
f10 f14 f18 f22 f26 f30 f34 f38

Element removed is ‘9’ Size = 5

All the elements after the index are shifted by one position to the left. Finally, the size is
decremented by one.

Dr. Vishwanath Murthy, Sahitya K, MCA, RNSIT 13

Data Structures MMC203
Module – 1: Introduction to Data Structures and Algorithms

Function to remove an element from a given position in an Array

int remove (int A[],int *n)

{
int element, pos, j,
printf (“Input position to insert the new element:”);
scanf (“%d”, &pos);
element = A[pos-1];
j = pos-1
while (j < *n – 1)
{
A[j] = A[j+1];
j ++;
}
*n = *n - 1;
return element;
}

Practice program: Homework

Modify the above program to satisfy the following conditions:
1. Check if the index is valid: Ensure the index is within the bounds of the array.
2. Check if array is empty: can’t remove element if array is empty.
3. Shift elements: Shift all the elements from given position till last element to left by
one location.
6. Update the count: Decrement count of elements (n) by 1.
7. Return element: return the value of the element that is removed from the array.

Dr. Vishwanath Murthy, Sahitya K, MCA, RNSIT 14

Data Structures MMC203
Module – 1: Introduction to Data Structures and Algorithms

iii) Traversal:
- An operation that displays each element of an array.
Function to Traverse an Array

void Display (int A[], int n)

{
for (int i = 0; i < n ; i++)
printf (“ %d ”, A[i])
}

Assignment-1
- Write a complete C program to implement the following basic operations 12 Marks
on the Arrays
o Insertion – Create insert function that Adds an element at the given
index.
o Deletion − Create remove function that Deletes an element at the
given index.
o Traversal − Create Display function that print all the array elements
one by one.
Implement main function that input an array and Call all the above functions
based on user choice.

Dr. Vishwanath Murthy, Sahitya K, MCA, RNSIT 15

Data Structures MMC203
Module – 1: Introduction to Data Structures and Algorithms

1.3.3) Multidimensional arrays.

----------------------------------------------------------------------------------------------------------------------------
- A multi-dimensional array can be defined as an array that has more than one dimension.
- Some popular multidimensional arrays are 2D arrays and 3D arrays.
- Arrays can have any number of dimensions.
- A multidimensional array is basically an array of arrays.

• Syntax

DataType arrayName [size1] [size2] …. [sizeN];

→ Example: 2D Array

int matrix [2][3];

→ Initialization
int matrix [3][4] = {
{11, 22, 33, 44},
{55, 66, 77, 88},
{11, 66, 77, 44},
};

Dr. Vishwanath Murthy, Sahitya K, MCA, RNSIT 16

Data Structures MMC203
Module – 1: Introduction to Data Structures and Algorithms

→ Creating and initializing 3D Array:

float cube [3][3][3] =
{
{ {10, 11, 12}, {13, 14, 15}, {16, 17, 18} },
{ {20, 21, 22}, {23, 24, 25}, {26, 27, 28} },
{ {30, 31, 32}, {33, 34, 35}, {36, 37, 38} }
};

1.3.4) Applications of arrays.

----------------------------------------------------------------------------------------------------------------------------
Below are some applications of arrays.
• Storing and accessing data: Arrays store elements in a sequential order and Hence allow
Direct access to any element.
• Sorting and Searching: Sorting and searching is faster using arrays.
• Representing Matrices: Two-dimensional arrays are used to represent matrices.
• Implementing other data structures: Arrays are used as the underlying data structure
for implementing stacks and queues.
• Creating Data Buffers: Arrays serve as data buffers and queues, temporarily storing
incoming data like network packets, file streams, and database results before
processing.
• Simulation and Modeling: Arrays can represent various real-world systems, such as simulations
of traffic, weather patterns, or other grid-based simulations.

Dr. Vishwanath Murthy, Sahitya K, MCA, RNSIT 17

Data Structures MMC203
Module – 1: Introduction to Data Structures and Algorithms

1.4) Stack
Ques: What is stack? Explain the various data structures used to represent a stack with
neat diagram – (2+8 marks)

• Definition:
“A stack is a Linear data structure in which all insertion and deletions operations are
restricted to one end, called the top”.

• Properties of stack:
- Stack is an abstract data type with a predefined capacity.
- Stack is a linear data structure.
- It has only one pointer top that points the last or top most element of Stack.
- Stack uses LIFO structure (Last In – First Out)
o Insertion and deletion operations are performed based on LIFO principle.

Figure 1.1: Operations on stack

Dr. Vishwanath Murthy, Sahitya K, MCA, RNSIT 18

Data Structures MMC203
Module – 1: Introduction to Data Structures and Algorithms

1.4.1) Representation of stack

----------------------------------------------------------------------------------------------------------------

Ques: What is stack? What are the data structures used to represent stack? (July 2021)

Stack can be represented using any of the following data structures.

o Array representation,
o Linked list representation.

i) Array representation of stack

− A stack can be implemented using a one-dimensional array.
− Limitations of array.
o Array size is fixed: hence stack can store only a fixed number of data values.
o Array is homogeneous: hence stack can store similar type of data values.

0 1 2 3 3

top 30 10 20 30

20

10 top

Stack

ii) Linked list representation of stack

− In linked list implementation of stack, the nodes are maintained non-contiguously in the
memory. Each node contains a pointer to its immediate successor node in the stack. Stack
is said to be overflown if the space left in the memory heap is not enough to create a node.

top
top

Dr. Vishwanath Murthy, Sahitya K, MCA, RNSIT 19

Data Structures MMC203
Module – 1: Introduction to Data Structures and Algorithms

1.4.2) Stack operations

----------------------------------------------------------------------------------------------------------------

Ques: What is stack? Explain the basic operations of stack with neat – (2+8 marks)
diagram.
• Stack operations - Stack supports following operations:
➢ PUSH operation represented as push(element) function.
➢ POP operation represented as pop() function.
➢ PEEK: operation represented as peek() function.

1) PUSH
o Insert a new element on the top of Stack.
o Can’t insert an element if the stack is FULL.
o Push operation first increments top to point next empty space and then add a
element.

(a) before PUSH operation (b) after PUSH operation

2) POP
o Remove an element from the top of stack.
o Can’t remove an element from EMPTY stack.
o Pop operation first reads a top element, then it decrements the top.

(a) before POP operation (b) after POP operation

Dr. Vishwanath Murthy, Sahitya K, MCA, RNSIT 20

Data Structures MMC203
Module – 1: Introduction to Data Structures and Algorithms

3) PEEK
o Peek operation allows the user to see the element on the top of the stack.
o The stack is not modified in any manner in this operation.

PEEK() 30 30

top 30 top 30
20 20

10 10
Stack
(a) before PEEK operation (b) after PEEK operation

Q1. Write a program to implement stack operations using array as a data structure
(without using Structure). Implement the following conditions on stack.
1. Stack overflow 2. Stack underflow 3. Stack empty 4. Stack full

Q2. Define stack. Write a program to implement basic operations on stack.

/* Stack implementation */
#define MAX 3
int top = -1;
int stack [MAX];

void push(int item )

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

if (top == MAX-1)
printf("\n .. STACK FULL ..");
}

Dr. Vishwanath Murthy, Sahitya K, MCA, RNSIT 21

Data Structures MMC203
Module – 1: Introduction to Data Structures and Algorithms

int pop ()
{
int item;
if (top == -1)
{
printf ("\n .. STACK UNDERFLOW ..");
return 0;
}
item = stack[top--];
if (top == -1)
printf ("\n ..Stack Is Empty ..\n");
return item;
}
void display ()
{
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]);
}
void main()
{
int choice, item;
while(1)
{
printf ("\n\n Stack Operations :\n");
printf ("\n 1. Push. \n 2. Pop. \n 3. Display.");

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

scanf ("%d", &choice);

Dr. Vishwanath Murthy, Sahitya K, MCA, RNSIT 22

Data Structures MMC203
Module – 1: Introduction to Data Structures and Algorithms

switch (choice)
{
case 1:
printf ("\n Enter the element to be pushed: ");
scanf ("%d", &item);
push (item);
break;
case 2:
item = pop();
if(item)
printf ("\n Popped item is: %d .",item);
break;
case 3:
display();
break;
default:
exit(0);
}
}
}

Dr. Vishwanath Murthy, Sahitya K, MCA, RNSIT 23

Data Structures MMC203
Module – 1: Introduction to Data Structures and Algorithms

1.4.3) Applications of Stack

----------------------------------------------------------------------------------------------------------------

Stack applications:
(a) Infix to postfix conversion
(b) Evaluation of postfix expression
(c) String Reversal
(d) Subroutine call
(e) Recursion
(f) Parenthesis checking
(g) Parsing data
(h) Backtracking

Infix, Polish and Reverse Polish expressions

• Arithmetic 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 or Suffix expression)

i) Infix Notation
o Form: “operator is placed in-between the two operands”
o Example: A + B, 5 – 6

ii) Polish Notation (Prefix expression)

o Prefix notation was introduced by the “Polish logician Lukasiewicz” and is sometimes
called “Polish notation”.
o Form: “operator is placed in beginning of the two operands”
o Example: + A B, - 5 6
iii) Reverse Polish Notation or Suffix (Postfix expression)
o Postfix notation is also called “Reverse Polish Notation - RPN”.
o Form: “operator is placed in end of the two operands”
o Example: A B +, 5 6 –

Dr. Vishwanath Murthy, Sahitya K, MCA, RNSIT 24

Data Structures MMC203
Module – 1: Introduction to Data Structures and Algorithms

Ques: Explain Polish and reverse polish notations. – 4 marks

→ Why we need Infix or Prefix or Postfix Expression?

• Infix Notation:
- Infix notation needs extra information to evaluate the expression as
o Operator precedence
o Associativity.
- Brackets ( ) allow users to override these rules.
- For example:
o In expression: a + (b – c) * d the subtraction is performed first, next multiplication is
performed and finally the addition is performed.
o Associativity for arithmetic operator is from left to right.

Priority table from highest to lowest

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

• Prefix and Postfix Notation:

- The prefix/postfix notations does not require extra information for Operator precedence
and Associativity, as this information is included in expression itself.
- No Brackets ( ) are required to override these rules.
- Infix expression: a * (b – c) // angular brace is used to change the precedence.
- Prefix expression: *a- bc // Precedence is inbuilt.
- Postfix expression: a b c -* // Precedence is inbuilt.

Dr. Vishwanath Murthy, Sahitya K, MCA, RNSIT 25

Data Structures MMC203
Module – 1: Introduction to Data Structures and Algorithms

• 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 and postfix:

Infix Prefix Postfix

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

Convert to prefix → ( A + [*BC] ) + D → ( (A + [BC*] ) + D

and postfix
→ ( [+A*BC] + D ) → ( [ABC*+] + D )

→ + + A * B C D → A B C * + D +
→ →
Postfix = A B + C + D +

Convert to infix and

prefix

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

Convert to prefix
and postfix

Dr. Vishwanath Murthy, Sahitya K, MCA, RNSIT 26

Data Structures MMC203
Module – 1: Introduction to Data Structures and Algorithms

Stack Application: a) Infix-to-Postfix Conversion

• Algorithm: Infix to Postfix

1. Set operator stack to empty.
2. Scan Next Symbol from infix expression one at a time.
➢ If Symbol = operand then
- Add symbol to postfix
➢ If Symbol = openBrace then
- Push symbol to stack
➢ If Symbol = closingBrace then
- while ( StackTop != openBrace )
Pop and add to postfix.
- Remove open brace from stack and discard
➢ If Symbol = operator then
- while (precedence(Symbol) <= precedence(StackTop) )
Pop and add to postfix.
- Push symbol to stack. // as precedence of Symbol is High
3. Repeat step-2 untill no more symbols in Infix string.
4. While (stack is not empty)
- Pop and add to postfix.

Operator Meaning Precedence

$ or ^ Exponent (Highest) 4
*, / Multiplication and division 3
+, - Addition and subtraction 2
( Open brace 1
# Bottom of stack (Lowest) 0

Ques: Write an algorithm to convert infix expression to postfix – 6 marks

Dr. Vishwanath Murthy, Sahitya K, MCA, RNSIT 27

Data Structures MMC203
Module – 1: Introduction to Data Structures and Algorithms

Q3. Write a function that convert the infix expression to postfix expression that -- 10 marks
also includes braces (Parenthesis)
/* infixToPostfix() function */
void infixToPostfix(char *infix, char* postfix)
{
char symbol, brace;
int i = 0, k = 0;

push('#');

while ((symbol = infix[i++]) != '\0')

{
if (isalnum(symbol)) /* Built-in function in ctype.h */
postfix[k++] = symbol;
else if (symbol == '(')
push(symbol);

else if (symbol == ')')

{
while (stack[top] != '(')
postfix[k++] = pop();
brace = pop(); /* Remove open brace ‘(‘ */
}
else
{ /* Operator */
while (precedence(symbol) <= precedence(stack[top]))
postfix[k++] = pop();
push(symbol);
}
}

while (stack[top] != '#') /* Pop from stack till empty */

postfix[k++] = pop();

postfix[k] = '\0';
}

Output:

Dr. Vishwanath Murthy, Sahitya K, MCA, RNSIT 28

Data Structures MMC203
Module – 1: Introduction to Data Structures and Algorithms

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

#define SIZE 10 /* Size of Stack */

#include <ctype.h>

char stack[SIZE]; /* Global declarations */

int top;

void push(char symbol)

{
stack[++top] = symbol;
}

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

int precedence(char opr)

{ /* Function for precedence */
switch (opr)
{
case '#': return 0;
case '(': return 1;
case '+':
case '-': return 2;
case '*':
case '/': return 3;
}
}
void main()
{
char infix[50], postfix[50];

top = -1;

printf ("\n Input the Infix Expression: ");

scanf ("%s", infix);
infixToPostfix (infix, postfix);
printf ("\n Postfix Expression : %s", postfix);
}

Dr. Vishwanath Murthy, Sahitya K, MCA, RNSIT 29

Data Structures MMC203
Module – 1: Introduction to Data Structures and Algorithms

Stack Application: b) Evaluation of Postfix Expression

• Algorithm: Evaluation of Postfix Expression
1. Set Operand Stack to empty
2. Scan Next Symbol from postfix expression one at a time.
a). If symbol = operand then
- Push symbol to stack.
b). If symbol = operator then
- Pop first operand to OP2
- Pop second operand to OP1
- Apply operator on both operands as
result = Apply (OP1, symbol, OP2).
- Push the result back to stack.
3. Repeat step-2 untill end of input string.
4. Pop final result and Return

[Link] a C program to evaluate postfix expression. – 10 marks (Aug.2022)

/* evaluation of postfix expression */

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

#define MAX 20

float stack[MAX];
int top;

void push(float item)

{
stack[++top] = item;
}

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

Dr. Vishwanath Murthy, Sahitya K, MCA, RNSIT 30

Data Structures MMC203
Module – 1: Introduction to Data Structures and Algorithms

float getResult (float op1, float op2, char symbol)

{
float result;
switch (symbol) /* perform operation */
{
case '+' : result = op1 + op2;
break;
case '-' : result = op1 - op2;
break;
case '*' : result = op1 * op2;
break;
case '/' : if(op2)
result = op1 / op2;
else
{ printf(“Exception: Divide by zero”);
exit(0);
}
break;
}
return (result);
}

float evalPost (char *postfix)

{
int i=0;
char symbol;
float op1, op2, result, digit;
top=-1;

while ( (symbol = postfix[i++]) != '\0')

{
if(isdigit(symbol)) /* Built-in function in ctype.h */
{
digit = symbol - '0';
push(digit);
}
else
{
op2 = pop();
op1 = pop();
result = getResult (op1, op2, symbol);
push(result);
}
}
return pop();
}

Dr. Vishwanath Murthy, Sahitya K, MCA, RNSIT 31

Data Structures MMC203
Module – 1: Introduction to Data Structures and Algorithms

int main()
{
char postfix[MAX];
float result;

printf("\n Enter a valid postfix expression: ");

scanf("%s", postfix);

result = evalPost (postfix);

printf("\n The result is: %f", result);

}

Output:

Dr. Vishwanath Murthy, Sahitya K, MCA, RNSIT 32

Data Structures MMC203
Module – 1: Introduction to Data Structures and Algorithms

Stack Application: c) Function Calls

• Call stack:
A call stack is an area of memory that is allocated to a program to store information about each active
subroutine. An active subroutine is one that has been called, but has not yet finished execution. At any
point during a program's execution, there may be multiple active subroutines.

The call stack, like any stack, is finite in size. Memory space is allocated for the call stack before the
program is run. In some low-level languages, the amount of memory allocated is determined by the
programmer. In high-level languages, it is controlled by the program language variables, the compiler,
and/or the operating system.

If you write a subroutine that calls itself with no means of escape, you will fill up the stack with hundreds
of stack frames. This will eventually result in the infamous stack overflow error message.

Example:

int main() Call stack

{
one();
}
void one()
{
two(); two()
}
void two() one() one() one()
{
main() main() main() main() main()
int a = 10, b = 20;
printf (“c = %d”, a + b );
}

Dr. Vishwanath Murthy, Sahitya K, MCA, RNSIT 33

Data Structures MMC203
Module – 1: Introduction to Data Structures and Algorithms

When a function is invoked (called), a new stack frame (or activation record) is pushed onto the
call stack. This stack frame holds essential information related to that specific function call.
Typically, a stack frame stores the following:

• Return Address: This is the memory address of the instruction in the calling function
that should be executed immediately after the called function finishes. This is vital for the
program to know where to resume execution.
• Local Variables: These are the variables declared within the function. The stack frame
allocates space to store the values of these variables.
• Parameters (Arguments): The values passed to the function when it was called are also
stored in the stack frame.
• Saved Registers: Before a function call, the values of some CPU registers might need to
be saved so they can be restored after the function returns. The stack frame can hold these
saved register values.
• Frame Pointer (Optional): Some architectures use a frame pointer to easily access local
variables and parameters within the stack frame
.

Stack

Dr. Vishwanath Murthy, Sahitya K, MCA, RNSIT 34

Data Structures MMC203
Module – 1: Introduction to Data Structures and Algorithms

Stack application: d) Backtracking

Backtracking can be defined as a general algorithmic technique that considers

searching every possible combination in order to solve a computational problem.

how the stack is typically used in a backtracking algorithm:

1. Making a Choice (Push): When the algorithm explores a new option or makes a
decision, the information representing that choice (and potentially the state resulting from
that choice) is pushed onto the stack. This records the step taken and allows the algorithm
to return to this point later if needed.
2. Exploring Further: The algorithm then proceeds to make further choices based on the
current state (which is implicitly defined by the elements in the stack).
3. Reaching a Dead End or Invalid State: If the algorithm reaches a point where no valid
further choices can be made, or if the current path leads to an invalid or undesirable state,
it needs to backtrack.
4. Backtracking (Pop): The "backtracking" step is achieved by popping the top element
from the stack. This effectively undoes the last choice made, returning the algorithm to
the state before that choice.
5. Trying a Different Choice: From this previous state (now at the top of the stack), the
algorithm can then explore other available options that were not taken before.

Dr. Vishwanath Murthy, Sahitya K, MCA, RNSIT 35

Data Structures MMC203
Module – 1: Introduction to Data Structures and Algorithms

Application of Stack: e) Reversing String

• Algorithm
1. Set operand Stack to empty.
2. Scan next symbol from input String and Push it to stack.
3. Repeat step 2 till end of string.
4. Pop character from stack one by one and add to output string.
5. Repeat step-4 till stack is empty.
6. Add null character to output string.
7. Display output string.

Example:

Ques: Write C program to reverse a given string using stack

void reverse ( char str [], char rev [ ] )

{
int i;
for (i = 0; str[i] != '\0'; i++)
push (str[i]);

for (i=0; top != -1 ; i++) //pop till stack is empty

rev[i] = pop();

rev[i] = '\0';
}

Dr. Vishwanath Murthy, Sahitya K, MCA, RNSIT 36

Data Structures MMC203
Module – 1: Introduction to Data Structures and Algorithms

#include <stdio.h>
#define MAX 20
char stack [MAX];
int top;
void push (char item)
{
stack[++top] = item;
}
char pop ()
{
return (stack[top--]);
}
int main()
{
char originalString[MAX], rev[MAX];
int i;
top = -1; //initialize stack to empty
printf ("\n Enter any string: ");
scanf ("%s", originalString);

reverse (originalString, rev);

printf ("\n The reversed string is: %s", rev);

Dr. Vishwanath Murthy, Sahitya K, MCA, RNSIT 37

Data Structures MMC203
Module – 1: Introduction to Data Structures and Algorithms

Module – 1: Question Bank Marks

Introduction to data structures and Algorithm Analysis

1 Define Data structures. Explain different types of data structures with neat
08
diagram.
2 Define Data structures. Explain any two linear data structures with neat diagram. 08
3 Define Data structures. Explain various non-linear data structures with neat
08
diagram.
4 What is data structure? Explain the classification of data structure with example
10
for each.
5 Define algorithm. Explain the use of Big O notation with respect to analysis. 10
6 Define algorithm. Explain the properties of good algorithm. 05
7 Write a note on i) Time and space complexity ii) Big O notation 10
8 Explain the concept of algorithm analysis with respect to Time and space
10
complexity and Big O notation.
Arrays
1 Write a c program to implement following operations on array
12
i) insert ii) remove iii) traversal
2 Write a C program to implement the insert operation on one-dimensional array.
Ask the user to input the array elements, the position at which to insert a new
element, and the value to be inserted. Include appropriate logic for boundary 10
conditions and display the array before and after insertion with the help of
diagrams.
3 Implement a C program to perform remove operation on array. Ask the user to
input the array elements and the position at which the element to be removed.
10
Include appropriate logic for boundary conditions and display the array before
and after removal operation with the help of diagrams.
4 Explain the creation and initialization of 3-Dimensional array with neat memory
diagram. Write a C program that demonstrates the creation and initialization of a 10
3-Dimensional array.
Stacks
1 What is a stack? List and explain basic operations on the stack with neat diagram. 10
2 Write a C program to implement a stack with the following operations: push, 10
pop, and display. Enhance the program to include error handling for stack
overflow and underflow conditions. Ensure that your program handles edge
cases such as attempting to pop from an empty stack or push to a full stack.

Dr. Vishwanath Murthy, Sahitya K, MCA, RNSIT 38

Data Structures MMC203
Module – 1: Introduction to Data Structures and Algorithms

3 Write a C Program implement STACK with the following operations. 10

a) Push b) Pop c) Peek d) Display
4 Write a program to implement stack operations using array as a data structure. 10
Implement the following conditions on stack.
1. Stack overflow 2. Stack underflow 3. Stack empty 4. Stack full
5 What are Polish and Reverse Polish notations? Convert the following infix 10
expression to its equivalent prefix and postfix expression:
➢ (A+B)*(C^( D–E)+F)–G
➢ (A+B)*(C–D)^E*F
➢ A+(((B–C)*(D–E)+F)/G)+H
6 What are Polish and Reverse Polish notations? Convert the following infix 10
expression to its equivalent prefix and postfix expression:
i) ( A + B ) * C – D $ E * F
ii) A – B / C * D $ E
iii) ( A + B ) $ ( c + D – E ) * F
7 Explain with an algorithm how a stack can be used as a temporary storage 10
structure for converting an infix mathematical expression to its postfix
equivalent. Trace the algorithm for input: A+B*C.
8 Write an algorithm to convert an infix expression to postfix. Trace the algorithm 10
for following infix expression ( ( A – ( B + C ) ) * D ) $ ( E + F )
9 Present a detailed algorithm, employing a stack data structure, to systematically 10
convert a given infix arithmetic expression into its postfix equivalent. Clearly
outline each step of the algorithm, including the handling of operator precedence
and parentheses.
10 Design and implement a C function, that accepts a valid infix arithmetic 10
expression (assume single-digit operands and the operators +, -, , /, and
parentheses) and returns its equivalent postfix expression.
11 Define Prefix and Postfix expressions. Write a program to convert an infix 10
expression to postfix expressions.
12 Write an algorithm to evaluate a postfix expression. Trace the algorithm for the 10
following expression: A B C + * C B A - + * with A=1, B=2, C=3.
13 Write an algorithm to evaluate a postfix expression using a stack. Apply your 10
algorithm to evaluate the following postfix expression: 2 3 * 4 2 ^ / 5 +
14 Illustrate with a clear algorithm and a suitable example, demonstrating how a 10
stack data structure is utilized to evaluate a given postfix arithmetic expression.
15 Develop a robust C program that takes a valid postfix arithmetic expression as 10
input and evaluate to its numerical result.

Dr. Vishwanath Murthy, Sahitya K, MCA, RNSIT 39

Data Structures MMC203
Module – 1: Introduction to Data Structures and Algorithms

16 Write a C function to evaluate a Postfix expression. Trace the code to evaluate the 10
postfix expression: 6 2 / 3 + 5 * -
17 In the context of function calls in a program, explain the role of a call stack. What 10
information is typically stored on the call stack when a function is invoked?
18 Define stack with diagram. Write a C program that uses a stack to reverse a 10
string. Ensure the program handles edge cases such as empty strings.
Additionally, include a memory diagram to show how the stack changes as
characters are pushed and popped during the reversal process.

Some practice problems on Converting expressions.

Priority table from highest to lowest

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

Convert the following infix expression from infix to prefix and postfix.

Infix Prefix postfix

A+B–C

(A+B) * (C-D)

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

A–B/(C*D$E)

Dr. Vishwanath Murthy, Sahitya K, MCA, RNSIT 40