CU-BCA-SEM-III-DATA STRUCTURES- Second Draft-converted

if(Prod->Power > MaxDegree) { Error(“Exceeded Array Size”); } else { for(i=0;i<=Sum->Power; i++) { for(i=0;i<=Sum->Power; i++) { Prod->CoeffArray[i + j] += Poly1->CoeffArray[i] * Poly2->CoeffArray[j]; } } } } 3.4 SUMMARY • Linear search is the simplest search algorithm and often called a sequential search. In this type of searching, we simply traverse the list completely and match each element of the list with the item whose location is to be found. If the match found then the location of the item is returned otherwise the algorithm return NULL. • A binary search is an advanced type of search algorithm that finds and fetches data from a sorted list of items. • Binary search is commonly known as a half-interval search or a logarithmic search • It works by dividing the array into half on every iteration under the required element is found. • The binary algorithm takes the middle of the array by dividing the sum of the left and rightmost index values by 2. Now, the algorithm drops either the lower or upper 51 CU IDOL SELF LEARNING MATERIAL (SLM)

bound of elements from the middle of the array, depending on the element to be found. • Binary search performs comparisons of the sorted data based on an ordering principle than using equality comparisons that are slow and inaccurate. • A binary search is not suitable for unsorted data. • Polynomial: A polynomial object is a homogeneous ordered list of pairs <exponent, coefficient>, where each coefficient is unique. • Operations include returning the degree, extracting the coefficient for a given exponent, addition, multiplication, evaluation for a given input. 3.5 KEYWORDS • Linear search: to find an element in an unsorted array • Binary search: to find an element in a sorted array and executing very fast compare to linear search • Polynomial: A polynomial object is a homogeneous ordered list of pairs exponent, coefficient, where each coefficient is unique. 3.6 LEARNING ACTIVITY 1. You have to sort an array of student records by social security number. Write a program to do this, using binary sort and linear sort. ___________________________________________________________________________ ____________________________________________________________________ 3.7 UNIT END QUESTIONS A. Descriptive Questions Short Questions 1. Define linear search? 2. What is a binary search? 3. What is polynomial? 4. How do you represent polynomial using array? 5. Write a program to find a particular element using binary search. Long Questions 1. Explain in details about linear search. 52 CU IDOL SELF LEARNING MATERIAL (SLM)

2. Difference between linear search and binary search. 3. Write an algorithm for binary search and explain it. 4. Explain in details about binary search. 5. Write an algorithm for Linear search and explain it. B. Multiple choice Questions 1. What is the worst-case complexity of binary search using recursion? a. O(nlogn) b. O(logn) c. O(n) d. O(n2) 2. What is the average case time complexity of binary search using recursion? a. O(nlogn) b. O(logn) c. O(n) d. O(n2) 3. Which of the following is not an application of binary search? a. To find the lower/upper bound in an ordered sequence b. Union of intervals c. Debugging d. To search in an unordered list 4. Given an array arr = {5,6,77,88,99} and key = 88; How many iterations are done until the element is found in linear search? a. 1 b. 3 c. 4 d. 2 53 CU IDOL SELF LEARNING MATERIAL (SLM)

5. Is there any difference in the speed of execution between linear search(recursive) vs linear search(lterative)? a. Both execute at the same speed b. Linear search(recursive) is faster c. Linear search(Iterative) is faster d. Can’t be said Answer 1. (b) 2. (b) 3. (d) 4. (c) 5. (c) 3.8 REFERENCES Reference Books: • R1 Trembley & Soreson, Introduction to Data Structures Applications, Second Edition, Pearson Education. • R2 A. Tannenbaum, Y. Lanhgsam and A.J. Augenstein, Data Structures Using C++, Prentice Hall of India. Text Books: • T1 Schaum's Outlines Series- Data Structures, Seymour Lipschutz, TMH. • T2 E. Balagarusamy, Data Structure using C/C++, Tata McGraw-Hill Education. Websites: • https://www.geeksforgeeks.org/ • https://www.tutorialspoint.com/ 54 CU IDOL SELF LEARNING MATERIAL (SLM)

UNIT 4: STRUCTURES Structure 4.0 Learning Objective 4.1 Internal Representation of Structures 4.2 Self–Referential Structures 4.3 Summary 4.4 Keywords 4.5 Learning activity 4.6 Unit End Questions 4.7 References 4.0 LEARNING OBJECTIVE After studying this unit, the student will be able to • To provide the knowledge of basic data structures and their implementations. • To declare structure variables. • How to represent the Structures and provide solution to problems. • Explain the concept of Self–Referential Structures. 4.1 INTERNAL REPRESENTATION OF STRUCTURES The structure may be a user-defined data type in C language which allows us to mix data of various types. Structure helps to construct a posh data type that's more meaningful. we need to store the info of scholars like student name, age, address, id etc. One way of doing this is able to be creating a special variable for every attribute, however, once you got to store the info of multiple students than therein case, you'd got to create these several variables again for every student. this is often such an enormous headache to store data during this way. We can solve this problem easily by using structure. we will create a structure that has members for name, id, address and age then we will create the variables of this structure for every student. 55 CU IDOL SELF LEARNING MATERIAL (SLM)

int age Student (Stu) stu; Figure 4.1: Memory Representation of structure Defining a structure struct keyword is used to define a structure. struct defines a new data type which is a collection of primary and derived data types. Syntax: The struct keyword is used to create a structure in C. A struct keyword is a short form of structured data type. struct structName { DataType member1Name; DataType member2Name; DataType member3Name; … } [structureVariables]; Here structName can be anything of your choice. The member's data type can be the same or different. Once we have declared the structure we can use the struct name as a data type like int, float, array etc. After the closing curly brace, we can specify one or more structure variables, and this is optional also. Example of Structure struct Stud { int id; char Name[10]; 56 CU IDOL SELF LEARNING MATERIAL (SLM)

//F for female and M for male char Gender; }; Here struct Student declares a structure to carry the small print of a student which consists of 4 data fields, namely name, age, branch and gender. These fields are called structure elements or members. Each member can have a special datatype, like during this case, the name is an array of char type and age is of int type etc. Declaring Structure Variables It is possible to declare variables of a structure, either alongside structure definition or after the structure is defined. Structure variable declaration is analogous to the declaration of any normal variable of the other datatype. Structure variables are often declared within the following two ways: 1. Declaring Structure variables separately 2. Declaring Structure variables with structure definition Declaring Structure variables separately struct Stud { int id; char Name[10]; //F for female and M for male char Gender; }; struct Stud S1, S2; Declaring Structure variables with structure definition struct Stud { int id; char Name[10]; //F for female and M for male char Gender; 57 CU IDOL SELF LEARNING MATERIAL (SLM)

} S1, S2; Access members of a structure There are two types of operators used for accessing members of a structure. . - Member operator -> - Structure pointer operator S1.id=10; S1.Name=”jai”; S2->id=11; S2->Name=”raj”; Keyword typedef The typedef keyword is used to create an alias name for data types. It is commonly used with structures to simplify the syntax of declaring variables. struct Stud { int id; char Name[10]; //F for female and M for male char Gender; }; int main() { struct Stud s1, s2; } is equivalent to typedef struct Stud { int id; char Name[10]; //F for female and M for male char Gender; } stud; 58 CU IDOL SELF LEARNING MATERIAL (SLM)

int main() { Stud s1, s2; } Array of Structure An array of structures are often defined because the collection of multiple structures variables where each variable contains information about different entities. The array of structures is wont to store information about multiple entities of various data types. The array of structures is additionally referred to as the gathering of structures. Example: struct Stud stu[5]; struct Stud { int id; char Name[50]; }; struct Stud stu[5]; int i, j; void GetValues() { for(i = 0; i < 3; i++) { printf(\"\\nEnter %dst Student record:\\n\", i+1); printf(\"\\nEmployee name:\\t\"); scanf(\"%s\", stu[i].Name); } printf(\"\\nDisplaying Employee record:\\n\"); for(i = 0; i < 3; i++) { printf(\"\\nStudent name is %s\", stu[i].Name); printf(\"\\nID is %d\", stu[i].id); } } 59 CU IDOL SELF LEARNING MATERIAL (SLM)

int main() { GetValues(); return 0; } 4.2 SELF–REFERENTIAL STRUCTURES Self-Referential Structures A structure can have members which point to a structure variable of the same type. These types of structures are called self-referential structures and are widely used in dynamic data structures like trees, linked list, etc. It should be remembered that a pointer to a structure is similar to a pointer to any other variable. A self-referential data structure is essentially a structure definition that includes at least one member that is a pointer to the structure of its own kind. Such self-referential structures are very useful in many applications that involve linked data structures, such as lists and trees. Unlike a static data structure such as an array where the number of elements that can be inserted in the array is limited by the size of the array, a self-referential structure can dynamically be expanded or contracted. Operations like insertion or deletion of nodes in a self-referential structure involve simple and straight forward alteration of pointers. Figure 4.2: Self Referential Structure 60 Example Program: struct Node { int data1; int data2; struct Node* Link; }; int main() { CU IDOL SELF LEARNING MATERIAL (SLM)

struct Node ob; return 0; } Types of Self-Referential Structures 1. Self-Referential Structure with Single Link 2. Self-Referential Structure with Multiple Links Self-Referential Structure with Single Link: These structures can have only one self- pointer as their member. The following example will show us how to connect the objects of a self-referential structure with the single link and access the corresponding data members. Figure 4.3: Self Referential Structure 61 #include <stdio.h> struct Node { int data1; char data2; struct Node* Link; }; int main() { struct node ob1; // Node1 // Initialization ob1.Link = NULL; ob1.data1 = 10; ob1.data2 = 20; struct node ob2; // Node2 CU IDOL SELF LEARNING MATERIAL (SLM)

// Initialization ob2.Link = NULL; ob2.data1 = 30; ob2.data2 = 40; // Linking ob1 and ob2 ob1.Link = &ob2; // Accessing data members of ob2 using ob1 printf(\"%d\\t\", ob1.Link->data1); printf(\"\\n%d\", ob1.Link->data2); return 0; } Self-Referential Structure with Multiple Links: Self-referential structures with multiple links can have quite one self-pointer. Many complicated data structures are often easily constructed using these Self-Referential Structure with Multiple Links. Such structures can easily hook up with quite one node at a time. the subsequent example shows one such structure with quite one links. Figure 4.4: Self Referential Structure Doubly List 62 #include <stdio.h> struct Node { int data; struct node* prev; struct node* next; }; CU IDOL SELF LEARNING MATERIAL (SLM)

int main() 63 { struct node ob1; // Node1 Creation // Initialization ob1.prev = NULL; ob1.next = NULL; ob1.data = 10; struct node ob2; // Node2 Creation // Initialization ob2.prev = NULL; ob2.next = NULL; ob2.data = 20; struct node ob3; // Node3 Creation // Initialization ob3.prev = NULL; ob3.next = NULL; ob3.data = 30; // Forward links ob1.next = &ob2; ob2.next = &ob3; // Backward links ob2.prev = &ob1; ob3.prev = &ob2; CU IDOL SELF LEARNING MATERIAL (SLM)

// Accessing data of ob1, ob2 and ob3 by ob1 printf(\"%d\\t\", ob1.data); printf(\"%d\\t\", ob1.next->data); printf(\"%d\\n\", ob1.next->next->data); // Accessing data of ob1, ob2 and ob3 by ob2 printf(\"%d\\t\", ob2.prev->data); printf(\"%d\\t\", ob2.data); printf(\"%d\\n\", ob2.next->data); // Accessing data of ob1, ob2 and ob3 by ob3 printf(\"%d\\t\", ob3.prev->prev->data); printf(\"%d\\t\", ob3.prev->data); printf(\"%d\", ob3.data); return 0; } In the above example we will see that ‘ob1’, ‘ob2’ and ‘ob3’ are three objects of the self- referential structure ‘node’. and that they are connected using their links in such how that any of them can easily access each other’s data. this is often the facility of the self-referential structures. The connections are often manipulated consistent with the wants of the programmer. Applications: Self-referential structures are very useful in creation of other complex data structures like: 1. Linked Lists 2. Stacks 3. Queues 4. Trees 5. Graphs 4.3 SUMMARY • Structure is a user-defined datatype in C language which allows us to combine data of different types together. Structure helps to construct a complex data type which is more 64 CU IDOL SELF LEARNING MATERIAL (SLM)

meaningful. struct keyword is used to define a structure. struct defines a new data type which is a collection of primary and derived data types. • A Self-Referential Structure can have members which point to a structure variable of the same type. These types of structures are called self-referential structures and are widely used in dynamic data structures like trees, linked list, etc. It should be remembered that a pointer to a structure is similar to a pointer to any other variable. • Self-Referential Structure with Single Link: Self-Referential structures can have only one self-pointer as their member of the structure. • Self-Referential Structure with Multiple Links: Self-referential structures with multiple links can have more than one self-pointer. • A struct is a data structure that stores data elements belonging to different types. • Whereas an array stores data elements of a similar type, a struct stores data elements of different types. • A struct should be used when the data elements are not expected to change value. • The members of a struct are accessed using the dot (.) and (->)operator. • To create a C struct, we use the struct keyword. • Pointers pointing to a struct are created similarly to how pointers that are pointing to regular types are created. • A struct can be passed as an argument to a function in the same way ordinary functions are passed. 4.4 KEYWORDS • Structure: Structure is a user-defined datatype in C language which allows us to combine data of different types together. Structure helps to construct a complex data type which is more meaningful. • Self-Referential Structures: A structure can have members which point to a structure variable of the same type. These types of structures are called self-referential structures • Self-Referential Structure with Single Link: Self-Referential structures can have only one self-pointer as their member of structure. • Self-Referential Structure with Multiple Links: Self-referential structures with multiple links can have more than one self-pointer. 65 CU IDOL SELF LEARNING MATERIAL (SLM)

4.5 LEARNING ACTIVITY 1. Given two sorted list, L1 and L2, write a procedure to compute ������1 ������ ������2 using only the self referencial structure. ___________________________________________________________________________ ____________________________________________________________________ 2. Given two sorted list, L1 and L2, write a procedure to compute ������1 Ω ������2 using only the self referencial structure. ___________________________________________________________________________ ____________________________________________________________________ 4.6 UNIT END QUESTIONS A. Descriptive Questions Short Questions 1. Define structure 2. Identify the features of structure 3. Show the declaration of a structure 4. How would you initialize the structure? 5. Write the syntax of self-referential structure with an example. Long Questions 1. Describe the structure of a C program with an example. 2. Explain in details about the types of self-referential structure with example program 3. Write a C program to store the information of Students using Structure. The information of each student to be stored is: • Each Student Record should have: • Name • Roll Number • Age • Total Marks 4. What is structure and how do you initialize the structure in C program. 5. Explain in details about self-referential structure B. Multiple choice Questions 66 CU IDOL SELF LEARNING MATERIAL (SLM)

1. What will be the output of the following C code? #include <stdio.h> struct stud { char *c; struct stud *point; }; void main() { struct stud s; struct stud m; s.c = m.c = \"hi\"; m.point = &s; m.point)->c = \"hey\"; printf(\"%s\\t%s\\t\", s.c, m.c); } a. hey hi b. hi hey c. Run time error d. hey hey 2. What is a structure in C language.? a. A structure is a collection of elements that can be of same data type. b. A structure is a collection of elements that can be of different data type. c. Elements of a structure are called members. d. All of these 3. What is the size of a C structure.? 67 a. C structure is always 128 bytes. b. Size of C structure is the total bytes of all elements of structure. CU IDOL SELF LEARNING MATERIAL (SLM)

c. Size of C structure is the size of largest element. d. None of these 4. Choose a correct statement about C structures. a. Structure elements can be initialized at the time of declaration. b. Structure members cannot be initialized at the time of declaration c. Only integer members of structure can be initialized at the time of declaration d. None of these 5. Choose a correct statement about C structure.? int main() { struct ship { }; return 0; } a. It is wrong to define an empty structure b. Member variables can be added to a structure even after its first definition. c. There is no use in defining an empty structure d. None of these Answer 1. (b) 2. (b) 3. (b) 4. (b) 5. (c) 4.7 REFERENCES Reference Books: • R1 Trembley & Soreson, Introduction to Data Structures Applications, Second Edition, Pearson Education. • R2 A. Tannenbaum, Y. Lanhgsam and A.J. Augenstein, Data Structures Using C++, Prentice Hall of India. Text Books: • T1 Schaum's Outlines Series- Data Structures, Seymour Lipschutz, TMH. 68 CU IDOL SELF LEARNING MATERIAL (SLM)

• T2 E. Balagarusamy, Data Structure using C/C++, Tata McGraw-Hill Education. Websites: • https://www.geeksforgeeks.org/ • https://www.tutorialspoint.com/ 69 CU IDOL SELF LEARNING MATERIAL (SLM)

UNIT 5: STACKS 1 Structure 5.0 Learning Objective 5.1 Introduction 5.2 Primitive Operations 5.3 Summary 5.4 Keywords 5.5 Learning activity 5.6 Unit End Questions 5.7 References 5.0 LEARNING OBJECTIVE After studying this unit students will be able to: • Analyse linear data structures such as stacks and their applications. • Explain the operations of stacks. 5.1 INTRODUCTION Stack may be a linear arrangement with the restriction that insertions and deletions are often performed in just one position, namely, the top of the list, called the highest. Stacks are sometimes referred to as LIFO (Last in First Out) or FILO (First in Last Out). Figure 5.1: Stack Operation Every time a component is added, it goes on the highest of the stack and therefore the only element which will be removed is that the element that's at the highest of the stack, a bit like a pile of objects. 70 CU IDOL SELF LEARNING MATERIAL (SLM)

Working principle of Stack: Stack works on the LIFO pattern. As we will observe within the below figure there are five memory blocks within the stack; therefore, the dimensions of the stack is 5. Suppose we would like to store the weather during a stack and let's assume that stack is empty. we've taken the stack of size 5 as shown below during which we are pushing the weather one by one until the stack becomes full. Figure 5.2: Stack Representation Since our stack is full because the size of the stack is 5. within the above cases, we will observe that it goes from the highest to rock bottom once we were entering the new element within the stack. The stack gets filled up from rock bottom to the highest. When we perform the delete operation on the stack, there's just one way for entry and exit because the other end is closed. It follows the LIFO pattern, which suggests that the worth entered first are going to be removed last. within the above case, the worth 5 is entered first, so it'll be removed only after the deletion of all the opposite elements. Stack Node Declaration: Struct Node { int data; struct Node * Next; }; 71 CU IDOL SELF LEARNING MATERIAL (SLM)

5.2 PRIMITIVE OPERATIONS Stack Primitive Operations: The following are some common operations implemented on the stack 1. push (): once we insert a component during a stack then the operation is understood as a push. If the stack is full then the overflow condition occurs. 2. pop (): once we delete a component from the stack, the operation is understood as a pop. If the stack is empty means no element exists within the stack, this state is understood as an underflow state. 3. isEmpty(): It determines whether the stack is empty or not. 4. isFull(): It determines whether the stack is full or not.' 5. peek(): It returns the element at the given position. 6. count(): It returns the entire number of elements available during a stack. 7. change(): It changes the element at the given position. 8. display(): It prints all the weather available within the stack. PUSH operation: Before inserting a component during a stack, we check whether the stack is full or not. If we attempt to insert the element during a stack, and therefore the stack is full, then the overflow condition occurs. once we initialize a stack, we set the worth of the highest as -1 to see that the stack is empty. Figure 5.3: Stack Push Operation 72 CU IDOL SELF LEARNING MATERIAL (SLM)

When the new element is pushed during a stack, first, the worth of the highest gets incremented, i.e., top=top+1, and therefore the element are going to be placed at the new position of the highest . the weather are going to be inserted until we reach the max size of the stack. POP operation: • Before deleting the element from the stack, we check whether the stack is empty or not. • If we attempt to delete the element from the empty stack, then the underflow condition occurs. • If the stack isn't empty, we first access the element which is pointed by the highest • Once the pop operation is performed, the highest is decremented by 1, i.e., top=top-1. Figure 5.4: Stack POP Operation 5.3 SUMMARY • Stack is a linear data structure with the restriction that insertions and deletions can be performed in only one position, namely, the end of the list called the top. Stacks are sometimes known as LIFO (Last In First Out) or FILO (First In Last Out). • push(): When we insert an element in a stack then the operation is known as a push. If the stack is full then the overflow condition occurs. 73 CU IDOL SELF LEARNING MATERIAL (SLM)

• pop(): When we delete an element from the stack, the operation is known as a pop. If the stack is empty means that no element exists in the stack, this state is known as an underflow state. • At all times, we maintain a pointer to the last PUSHed data on the stack. As this pointer always represents the top of the stack, hence named top. The top pointer provides the top value of the stack without actually removing it. • TOP(): TOP pointer is used to push the element into a stack and remove the element from the stack 5.4 KEYWORDS • TOP: Both insertion and removal are allowed at only one end of Stack called Top • isEmpty(): It determines whether the stack is empty or not. • isFull(): It determines whether the stack is full or not.' • peek(): It returns the element at the given position. • count(): It returns the total number of elements available in a stack. • change(): It changes the element at the given position. • display(): It prints all the elements available in the stack. 5.5 LEARNING ACTIVITY 1. You have to create a self-referential structure of student records by social security number. Write a program to do this, using stack. ___________________________________________________________________________ ____________________________________________________________________ 5.6 UNIT END QUESTIONS A. Descriptive Questions Short Questions 1. Define stack 2. List out the operations on the stack 3. Write short notes on any two operations on a stack 4. What is the primitive operation on the stack? 5. List out the primitive operation on the stack Long Questions 74 CU IDOL SELF LEARNING MATERIAL (SLM)

1. Explain in details about the stack. 2. Draw a neat sketch on stack operations 3. Explain in details about stack operations 4. Write short notes on the stack and explain the list of operation. 5. Explain in details the basic operation of the stack. B. Multiple choice Questions 1. Which of the following is also called last in first out system? a. Queue b. Stack c. Graph d. Tree 2. Which of the following is a linear data structure? a. Stack b. Graph c. Tree d. Binary tree 3. Process of inserting an element in stack is called ____________ a. Create b. Push c. Evaluation d. Pop 4. Pushing an element into stack already having five elements and stack size of 5, then stack becomes ___________ a. Overflow b. Crash c. Underflow d. User flow 75 CU IDOL SELF LEARNING MATERIAL (SLM)

5. In a stack, if a user tries to remove an element from an empty stack it is called _________ a. Underflow b. Empty collection c. Overflow d. Garbage Collection Answer 1. (b) 2. (b) 3. (b) 4. (a) 5. (a) 5.7 REFERENCES Reference Books: • R1 Trembley & Soreson, Introduction to Data Structures Applications, Second Edition, Pearson Education. • R2 A. Tannenbaum, Y. Lanhgsam and A.J. Augenstein, Data Structures Using C++, Prentice Hall of India. Text Books: • T1 Schaum's Outlines Series- Data Structures, Seymour Lipschutz, TMH. • T2 E. Balagarusamy, Data Structure using C/C++, Tata McGraw-Hill Education. Websites: • https://www.geeksforgeeks.org/ • https://www.tutorialspoint.com/ 76 CU IDOL SELF LEARNING MATERIAL (SLM)

UNIT 6: STACKS 2 Structure 6.0 Learning Objective 6.1 Memory Representation of Stacks Using Arrays 6.2 Memory Representation of Stacks Using Linked List 6.3 Summary 6.4 Keywords 6.5 Learning activity 6.6 Unit End Questions 6.7 References 6.0 LEARNING OBJECTIVE After studying this unit, the student will be able to • Analyse the basic concepts of Representation of a Stack using Array. • Explain the concepts about Representation of a Stack using Linked List. 6.1 MEMORY REPRESENTATION OF STACKS USING ARRAYS STACK- the name of the array storing stack elements TOP- storing the index where the last element is stored in array representing the stack MAX- defining that what percentage elements (maximum count) are often stored within the array representing the stack Figure 6.1: Stack Operations Using Array 77 CU IDOL SELF LEARNING MATERIAL (SLM)

The Stack ADT: push() − Pushing (Inserting) an element on the stack. pop() − Removing (Deleting) an element from the stack. Stack Creation: int stack[size]; PUSH Operation: The process of putting a replacement data element onto stack is understood as a Push Operation. Push operation involves a series of steps. • Checks if the stack is full. • If the stack is full, produces a mistake and exit. • If the stack isn't full, increments top to point next empty space. • Adds data element to the stack location, where top is pointing. • Returns success. Algorithm: begin procedure push: stack, data if stack is full return null endif top ← top + 1 stack[top] ← data end procedure Example: void push(int data) { if(!isFull()) { top = top + 1; stack[top] = data; } else 78 CU IDOL SELF LEARNING MATERIAL (SLM)

{ printf(\"Could not insert data, Stack is full.\\n\"); } } POP Operation: Removing element from the stack, is understood as a Pop Operation. In an array implementation of pop() operation, the info element isn't actually removed, instead top is decremented to a lower position within the stack to point to subsequent value. A Pop operation may involve the subsequent steps • Checks if the stack is empty. • If the stack is empty, produces a mistake and exit. • If the stack isn't empty, accesses the info element at which top is pointing. • Decreases the worth of top by 1. • Returns success. Algorithm for Pop Operation: begin procedure pop: stack if stack is empty return null endif data ← stack[top] top ← top - 1 return data end procedure Example: int pop(int data) { if(!isempty()) { data = stack[top]; top = top - 1; 79 CU IDOL SELF LEARNING MATERIAL (SLM)

return data; } else { printf(\"Empty Stack.\\n\"); } } 6.2 MEMORY REPRESENTATION OF STACKS USING LINKED LIST Using the Non-Contiguous Memory allocation sort of a Linked List. during this representation the stack is implemented using the dynamic arrangement Linked List. Using linked list for Application of stack make a dynamic stack. You don’t have the necessity to define the utmost number of elements within the stack. Pointers (links) to store addresses of nodes used are. TOP- storing the address of topmost element of the Linked list storing the stack Figure 6.2: Stack Using List PUSH Operation: Adding a node to the stack is mentioned as push operation. Pushing a component to a stack in linked list implementation is different from that of an array implementation. so as to push a component onto the stack, the subsequent steps are involved. • Create a node first and allocate memory thereto . • If the list is empty then the item is to be pushed because the start node of the list. This includes assigning value to the info a part of \"> a part of the node and assign null to the address part of the node. • If there are some nodes within the list already, then we've to feature the new element within the beginning of the list for this purpose, assign the address of the starting element to the address field of the new node and make the new node, the starting node of the list. 80 CU IDOL SELF LEARNING MATERIAL (SLM)

Figure 6.3: Stack PUSH Operation Using List Example: void push (int data) { struct node *ptr= (struct node*) malloc (sizeof (struct node)); ptr->data = data; ptr->next = NULL; if (ptr == NULL) { printf(\"not able to push the element\"); } else { if (head == NULL) { ptr -> next = NULL; head=ptr; 81 CU IDOL SELF LEARNING MATERIAL (SLM)

} else { ptr->next = head; head=ptr; } printf(\"Item pushed\"); } } POP Operation: Deleting a node from the highest of stack is mentioned as pop operation. Deleting a node from the linked list implementation of stack is different from that within the array implementation. so as to pop a component from the stack, we'd like to follow the subsequent steps: ▪ Check for the underflow condition: The underflow condition occurs once we attempt to pop from an already empty stack. The stack is going to be empty if the top pointer of the list points to null. ▪ Adjust the top pointer accordingly: In stack, the weather are popped only from one end, therefore, the worth stored within the head pointer must be deleted and therefore the node must be freed. subsequent node of the top node now becomes the top node. Figure 6.4: Stack POP Operation Using List Example: void pop() 82 CU IDOL SELF LEARNING MATERIAL (SLM)

{ struct node *ptr; if (head == NULL) { printf(\"Underflow\"); } else{ ptr = head; head = head->next; free(ptr); printf(\"Item popped\"); } } 6.3 SUMMARY • push(): When we insert an element in a stack then the operation is known as a push. If the stack is full then the overflow condition occurs. • pop(): When we delete an element from the stack, the operation is known as a pop. If the stack is empty means that no element exists in the stack, this state is known as an underflow state. 6.4 KEYWORDS • TOP: Both insertion and removal are allowed at only one end of Stack called Top • isEmpty(): It determines whether the stack is empty or not. • isFull(): It determines whether the stack is full or not.' • peek(): It returns the element at the given position. • count(): It returns the total number of elements available in a stack. • change(): It changes the element at the given position. • display(): It prints all the elements available in the stack. 6.5 LEARNING ACTIVITY 83 CU IDOL SELF LEARNING MATERIAL (SLM)

Write routines to implement two stacks using only one array. Your stack routines should not declare an overflow unless every slot in the array is used. ___________________________________________________________________________ ____________________________________________________________________ 6.6 UNIT END QUESTIONS A. Descriptive Questions Short Questions 1. What are the disadvantages of representing a stack by linked list? 2. What are the advantages of representing a stack by linked list? 3. What is top of stack? 4. What is empty stack? 5. What is overflow in stack? Long Questions 1. Write the routines to implement stack using linked list. 2. Write the routines to implement stack using array. 3. Write short notes on the operation of stack and What are the error conditions that could occur in stack implementation? How could they be rectified? 4. Explain in details about array representation of the stack. 5. Explain in details about list representation of the stack. B. Multiple choice Questions 1. What data structure would you most likely see in the non-recursive implementation of a recursive algorithm? a. Linked List b. Stack c. Queue d. Tree 2. Which of the following is true about linked list implementation of the stack? a. In a push operation, if new nodes are inserted at the beginning of the linked list, then in pop operation, nodes must be removed from the end. 84 CU IDOL SELF LEARNING MATERIAL (SLM)

b. In a push operation, if new nodes are inserted at the end, then in pop operation, nodes must be removed from the beginning. c. Both of these d. None of these 3. What is the result of the following operation? Top (Push (S, X)) a. X b. X+S c. S d. XS 4. Which data structure is used for implementing recursion? a. Queue b. Stack c. Array d. List 5. Which of the following statement(s) about stack data structure is/are NOT correct? a. Linked List are used for implementing Stacks b. Top of the Stack always contain the new node c. Stack is the FIFO data structure d. Null link is present in the last node at the bottom of the stack Answer 1. (b) 2. (d) 3. (a) 4. (b) 5. (c) 6.7 REFERENCES Reference Books: • R1 Trembley & Soreson, Introduction to Data Structures Applications, Second Edition, Pearson Education. 85 CU IDOL SELF LEARNING MATERIAL (SLM)

• R2 A. Tannenbaum, Y. Lanhgsam and A.J. Augenstein, Data Structures Using C++, Prentice Hall of India. Text Books: • T1 Schaum's Outlines Series- Data Structures, Seymour Lipschutz, TMH. • T2 E. Balagarusamy, Data Structure using C/C++, Tata McGraw-Hill Education. Websites: • https://www.geeksforgeeks.org/ • https://www.tutorialspoint.com/ 86 CU IDOL SELF LEARNING MATERIAL (SLM)

UNIT 7: APPLICATIONS OF STACKS Structure 7.0 Learning Objective 7.1 Evaluation of Postfix Expression 7.2 Infix to Postfix Conversion 7.3 Tower of Hanoi 7.4 Quick Sort 7.5 Summary 7.6 Keywords 7.7 Learning activity 7.8 Unit End Questions 7.9 References 7.0 LEARNING OBJECTIVE After studying this Unit students will be able to: • Learn prefix, infix, and postfix expression formats. • Develop skills to apply appropriate data structures in problem-solving. • Discuss how to use stacks to evaluate postfix expressions. • Convert expressions from infix to postfix. 7.1 EVALUATION OF POSTFIX EXPRESSION Postfix Expression: Postfix expression notation is named as reverse prefix notation. When variety is seen, it's pushed onto the stack; when an operator is seen, the operator is applied to the 2 numbers(symbols) that are popped from the stack, and therefore the result's pushed onto the stack. To evaluate a postfix expression using Stack arrangement we will use the subsequent steps. 1. Read all the symbols one by one from left to right within the given Postfix Expression 2. If the reading symbol is operand, then push it on to the Stack. 87 CU IDOL SELF LEARNING MATERIAL (SLM)

3. If the reading symbol is operator (+, -, *, / etc.,), then perform TWO pop operations and store the 2 popped operands in two different variables (operand1 and operand2). Then perform reading symbol operation using operand1 and operand2 and push result back on to the Stack. 4. Finally perform a pop operation and display the popped value as outcome. Algorithm: Begin for each character ch in the postfix expression, do if ch is an operator ⨀ , then a := pop first element from stack b := pop second element from the stack res := b ⨀ a push res into the stack else if ch is an operand, then add ch into the stack done return element of stack top End Example expression: Input Expression: 7 4 -3 * 1 5 + / * Figure 7.1: Postfix Expression Let the given expression be “7 4 -3 * 1 5 + / *. We scan all elements one by one from left to right. 88 CU IDOL SELF LEARNING MATERIAL (SLM)

1. Scan ‘7’, it’s variety , so push it to stack. Stack contains ‘7’ 2. Scan ‘4’, again variety , push it to stack, stack now contains ‘7 4’ (from bottom to top) 3. Scan ‘-3’, again variety , push it to stack, stack now contains ‘7 4 -3’ 4. Scan ‘*’, it’s an operator, pop two operands from stack, apply the * operator on operands, we get 4 *-3 which ends up in -12. We push the result ‘-12’ to stack. Stack now becomes‘7 -12’. 5. Scan ‘1’, it’s variety , so push it to stack. Stack contains ‘7 -12 1’ 6. Scan ‘5’, it’s variety , so push it to stack. Stack contains ‘7 -12 1 5’ 7. Scan ‘+’, it’s an operator, pop two operands from stack, apply the + operator on operands, we get 5 + 1 which ends up in 6. We push the result ‘6’ to stack. Stack contains ‘7 -12 6’. 8. Scan ‘/’, it’s an operator, pop two operands from stack, apply the / operator on operands, we get -12 / 6 which ends up in 6. We push the result ‘-2’ to stack. Stack contains ‘7 -2’. 9. Scan ‘*’, it’s an operator, pop two operands from stack, apply the * operator on operands, we get 7 *-2 which ends up in -14. We push the result ‘-14’ to stack. Stack contains‘-14’. 10. There are not any more elements to scan, we return the highest element from stack (which is that the only element left in stack). Example Program: #include<stdio.h> int stack[20]; int top = -1; void push(int x) { stack[++top] = x; } int pop() { return stack[top--]; } 89 CU IDOL SELF LEARNING MATERIAL (SLM)

int main() 90 { char exp[20]; char *e; int n1,n2,n3,num; printf(\"Enter the expression: \"); scanf(\"%s\",exp); e = exp; while(*e != '\\0') { if(isdigit(*e)) { num = *e - 48; push(num); } else { n1 = pop(); n2 = pop(); switch(*e) { case '+': { n3 = n1 + n2; break; } case '-': { n3 = n2 - n1; break; CU IDOL SELF LEARNING MATERIAL (SLM)

} case '*': { n3 = n1 * n2; break; } case '/': { n3 = n2 / n1; break; } } push(n3); } e++; } printf(\"\\nThe result of expression %s=%d\\n\\n\",exp,pop()); return 0; } 7.2 INFIX TO POSTFIX CONVERSION Infix to Postfix: One of the applications of Stack is within the conversion of arithmetic expressions in high- level programming languages into computer readable form. As our computing system can only understand and work on a binary language, it assumes that a mathematical process can happen in two operands only e.g. A+B,C*D,D/A etc. But in our usual form an arithmetic expression may contains quite one operator and two operands e.g.(A+B)*C(D/(J+D)) Let, X is an arithmetic expression written in mathematical notation. This algorithm finds the equivalent postfix expression Y. 1. Push “(“onto Stack, and add “)” to the end of X. 2. Scan X from left to right and repeat Step 3 to 6 for each element of X until the Stack is empty. 91 CU IDOL SELF LEARNING MATERIAL (SLM)

3. If an operand is encountered, add it to Y. 4. If a left parenthesis is encountered, push it onto Stack. 5. If an operator is encountered, then: a. Repeatedly pop from Stack and add to Y each operator (on the top of Stack) which has the same precedence as or higher precedence than operator. b. Add operator to Stack. [End of If] 6. If a right parenthesis is encountered ,then: a. Repeatedly pop from Stack and add to Y each operator (on the top of Stack) until a left parenthesis is encountered. b. Remove the left Parenthesis. [End of If] [End of If] 7. END. Infix Expression: ������ + (������ ∗ ������ − (������/������^������) ∗ ������) ∗ ������, where ^ is an exponential operator Table 7.1: Infix to Postfix Conversion 92 CU IDOL SELF LEARNING MATERIAL (SLM)

Resultant Postfix Expression: ������������������ ∗ ������������������^/������ ∗ −������ ∗ + 93 Example Program: #include<stdio.h> #include<ctype.h> char stack[100]; int top = -1; void push(char x) { stack[++top] = x; } char pop() { if(top == -1) return -1; else return stack[top--]; } int priority(char x) { if(x == '(') return 0; if(x == '+' || x == '-') return 1; if(x == '*' || x == '/') return 2; return 0; } int main() { char exp[100]; CU IDOL SELF LEARNING MATERIAL (SLM)

char *e, x; 94 printf(\"Enter the expression : \"); scanf(\"%s\",exp); printf(\"\\n\"); e = exp; while(*e != '\\0') { if(isalnum(*e)) printf(\"%c \",*e); else if(*e == '(') push(*e); else if(*e == ')') { while((x = pop()) != '(') printf(\"%c \", x); } else { while(priority(stack[top]) >= priority(*e)) printf(\"%c \",pop()); push(*e); } e++; } while(top != -1) { printf(\"%c \",pop()); } return 0; } CU IDOL SELF LEARNING MATERIAL (SLM)

7.3 TOWER OF HANOI Tower of Hanoi may be a mathematical puzzle where we've three rods and n disks. the target of the puzzle is to maneuver the whole stack to a different rod. Rules to follow 1. Only one disk can be moved at a time. 2. Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack i.e. a disk can only be moved if it is the uppermost disk on a stack. 3. No disk may be placed on top of a smaller disk. Algorithms: // Step 1 START // Step 2 Procedure Hanoi(disk, source, dest, aux) // Step 3 IF disk == 1, THEN move disk from source to dest ELSE Hanoi(disk - 1, source, aux, dest) move disk from source to dest Hanoi(disk - 1, aux, dest, source) END IF END Procedure STOP 95 CU IDOL SELF LEARNING MATERIAL (SLM)

Figure 7.2: Tower of Honai Example Program: #include <stdio.h> //fr=from rod,tr =to rod, ar=aux rod void TowerHanoi(int n, char fr, char tr, char ar) { if (n == 1) { printf(\"\\nMove disk 1 from rod %c to rod %c\", fr, tr); return; } TowerHanoi(n-1, fr, ar, tr); printf(\"\\nMove disk %d from rod %c to rod %c\", n, fr, tr); TowerHanoi(n-1, ar, tr, fr); } int main() { int n = 4; // n immplies the number of discs TowerHanoi(n, 'A','C','B');// A,B and C are the name of rod 96 CU IDOL SELF LEARNING MATERIAL (SLM)

return 0; } 7.4 QUICK SORT QuickSort may be a Divide and Conquer algorithm. It picks a component as pivot and partitions the given array round the picked pivot. There are many various versions of quickSort that pick pivot in several ways. 1. Always pick first element as pivot. 2. Always pick last element as pivot 3. Pick a random element as pivot. 4. Pick median as pivot. The key process in quickSort is partition(). Target of partitions is, given an array and a component x of array as pivot, put x at its correct position in sorted array and put all smaller elements (smaller than x) before x, and put all greater elements (greater than x) after x. All this could be wiped out linear time. Algorithm for QuickSort function: /* low --> Starting index, high --> Ending index */ QuickSort(arr[], low, high) { if (low < high) { /* pi is partitioning index, arr[pi] is now at right place */ pi = partition(arr, low, high); QuickSort(arr, low, pi - 1); // Before pi QuickSort(arr, pi + 1, high); // After pi } } 97 CU IDOL SELF LEARNING MATERIAL (SLM)

Partition Algorithm: We start from the leftmost element and keep track of index of smaller (or equal to) elements as i. While traversing, if we find a smaller element, we swap current element with arr[i]. Otherwise we ignore current element. partition (arr[], low, high) { // pivot (Element to be placed at right position) pivot = arr[high]; i=(low - 1) // Index of smaller element and indicates the // right position of pivot found so far for (j = low; j <= high- 1; j++) { // If current element is smaller than the pivot if (arr[j] < pivot) { i++; // increment index of smaller element swap arr[i] and arr[j] } } swap arr[i + 1] and arr[high]) return (i + 1) } Figure 7.3: Quick Sort 98 CU IDOL SELF LEARNING MATERIAL (SLM)

7.5 SUMMARY • Postfix expression notation is called reverse polish notation. When a number is seen, it is pushed onto the stack; when an operator is seen, the operator is applied to the two numbers(symbols) that are popped from the stack, and the result is pushed onto the stack. • One of the applications of Stack is in the conversion of arithmetic expressions in high- level programming languages into machine-readable form. As our computer system can only understand and work on a binary language, it assumes that an arithmetic operation can take place in two operands only e.g.������ + ������, ������ ∗ ������, ������/������ etc. But in our usual form, an arithmetic expression may consist of more than one operator and two operands e.g.(������ + ������) ∗ ������(������/(������ + ������)) • Tower of Hanoi is a mathematical puzzle where we have three rods and n disks. 1. Only one disk can be moved at a time. 2. Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack i.e. a disk can only be moved if it is the uppermost disk on a stack. 3. No disk may be placed on top of a smaller disk. 7.6 KEYWORDS • Postfix Expression: A postfix expression is a collection of operators and operands in which the operator is placed after the operands. • Infix to Postfix: One of the applications of Stack is in the conversion of arithmetic expressions in high-level programming languages into machine readable form. • Tower of Hanoi: The Tower of Hanoi, is a mathematical problem which consists of three rods and multiple disks. Initially, all the disks are placed on one rod, one over the other in ascending order of size similar to a cone-shaped tower. 7.7 LEARNING ACTIVITY 1. Show how to implement three stacks in one array. ___________________________________________________________________________ ____________________________________________________________________ 7.8 UNIT END QUESTIONS A. Descriptive Questions 99 CU IDOL SELF LEARNING MATERIAL (SLM)

Short Questions 1. List out application of stack 2. Write short notes on any two application of stack 3. Give any two applications of stacks. 4. Write procedure for changing the ith element of the stack. 5. Write short notes on tower of honai. Long Questions 1. Convert ((A+B) * C – (D – E)) $ (F + G) to Postfix notation. Postfix: AB + C * DE -- FG + $ 2. Write a program to convert infix to postfix using stack. 3. Outline the steps involved in converting an infix expression into polish notation with the help of a stack. Trace the steps on the following expression. ((a+b)*c)-d). 4. Explain in detail about tower of honai. 5. Explain in detail about postfix expression. B. Multiple choice Questions 1. Which of the following is not the application of stack? a. A parentheses balancing program b. Tracking of local variables at run time c. Compiler Syntax Analyzer d. Data Transfer between two asynchronous process 2. The data structure required to check whether an expression contains a balanced parenthesis is? a. Stack b. Queue c. Array d. Tree 3. Which one of the following is an application of Stack Data Structure? 100 a. Managing function calls b. The stock span problem c. Arithmetic expression evaluation CU IDOL SELF LEARNING MATERIAL (SLM)