Data Structures and Algorithms PDF Textbook

ALAGAPPA UNIVERSITY [Accredited with ’A+’ Grade by NAAC (CGPA:3.64) in the Third Cycle and Graded as Category–I University by MHRD-UGC] KARAIKUDI – 630 003...

ALAGAPPA UNIVERSITY [Accredited with ’A+’ Grade by NAAC (CGPA:3.64) in the Third Cycle and Graded as Category–I University by MHRD-UGC] KARAIKUDI – 630 003 DIRECTORATE OF DISTANCE EDUCATION DATA STRUCTURES AND ALGORITHMS Diploma in Computer Applications 517 23 Diploma in Computer Applications DATA STRUCTURE AND ALGORITHMS II - Semester  ALAGAPPA UNIVERSITY [Accredited with ‘A+’ Grade by NAAC (CGPA:3.64) in the Third Cycle and Graded as Category–I University by MHRD-UGC] (A State University Established by the Government of Tamil Nadu) KARAIKUDI – 630 003 Directorate of Distance Education Diploma in Computer Applications II - Semester 517 23 DATA STRUCTURES AND ALGORITHMS Author: Dr.A. Sumathi, Assistant Professor, Department of CSE,SRC Sastra University, Kumbakonam – 612 001. The Copyright shall be vested with Alagappa University” All rights reserved. No part of this publication which is material protected by this copyright notice may be reproduced or transmitted or utilized or stored in any form or by any means now known or hereinafter invented, electronic, digital or mechanical, including photocopying, scanning, recording or by any information storage or retrieval system, without prior written permission from the Alagappa University, Karaikudi, Tamil Nadu.  SYLLABI-BOOK MAPPING TABLE Data structures and Algorithms Syllabi Mapping in Book Unit I : 1 - 10 Introduction to Data Structure : Types of Data Structure , Primitive data types -Algorithms –Time and space Complexity of algorithms. Unit II: 11-18 Arrays: Array initialization, Definition of Array, Characteristic of Array ,One- dimensional Array, Two-dimensional array and Multi- dimensional array Unit III: 19-45 Stack : Stack related terms, Operations on a stack - Representation of Stack: Implementation of a stack – application of Stack. Expression Evaluation Polish notation. Queues: Operations on queue Circular Queue, Representation of Queues, Application of Queues. Unit IV: 46-71 List: Merging lists, Linked list, Single linked list, Double Linked List, Header - Linked list - Operation on Linked List : Insertion and Deletion of linked list -Traversal: Traversing a linked list , Representation of linked list. Unit V: 72-105 Trees: Binary Trees, Types of Binary trees, Binary Tree Representation - Binary Tree operations / Applications : Traversing Binary Trees, Binary Search tree -Operations on Binary Tree: Insertion and Deletion operations, Hashing Techniques. Unit VI: 106 - 111 Searching Techniques : Introduction, Searching, Types of searching, Linear Search, Binary search technique.  CONTENTS BLOCK I : INTRODUCTION UNIT -I: INTRODUCTION TO DATA STRUCTURE 1-10 1.1 Introduction 1.2 Objectives 1.3 Types of data structures 1.3.1 Linear Data Structures 1.3.2 Non-Linear Data Structures 1.4 Algorithms 1.4.1 Time and space complexity of algorithms 1.5 Check your progress questions 1.6 Answers to check your progress questions 1.7 Summary 1.8 Key Words 1.9 Self-Assessment Questions and Exercises 1.10 Further Readings UNIT -II: ARRAYS 11-18 2.1 Introduction 2.2 Objectives 2.3 Arrays 2.3.1 Definition 2.3.2 Initialization 2.3.3 Characteristic 2.4 Types of Array 2.4.1 Single-Dimensional Array 2.4.2 Multi-Dimensional Array 2.5 Check your progress 2.6 Answers to check your progress questions 2.7 Summary 2.8 Key Words 2.9 Self-Assessment Questions and Exercises 2.10 Further Readings BLOCK II : LINEAR DATA STRUCTURE UNIT -III: STACK 19-26 3.0 Introduction 3.1 Objectives 3.2 Stacks 3.2.1 Implementation 3.3 Stack Related Terms 3.4 Operations on Stack 3.5 Check your progress questions 3.6 Answers to check your progress questions 3.7 Summary 3.8 Key Words 3.9 Self-Assessment Questions and Exercises 3.10 Further Readings UNIT -IV: REPRESENTATION OF STACK 27-32 4.1 Introduction 4.2 Objectives 4.3 Application and Implementation of Stack 4.3.1 Converting Infix Notation to Postfix and Prefix or Polish Notations 4.4 Check your progress 4.5 Summary 4.6 Key Words 4.7 Self-Assessment Questions and Exercises 4.8 Further Readings UNIT -V: QUEUES 33-45 5.1 Introduction 5.2 Objectives 5.3 Queues 5.3.1 Operations on Queues 5.4 Representation of Queues 5.5 Circular Queue 5.6 Applications of Queues 5.7 Check your progress 5.8 Answers to check your progress 5.9 Summary 5.10 Key Words 5.11 Self-Assessment Questions and Exercises 5.12 Further Readings UNIT -VI: LIST 46-59 6.1 Introduction 6.2 Objectives 6.3 Merging lists 6.4 Linked List 6.5 Singly-Linked Lists 6.6 Doubly-Linked Lists 6.7 Header Linked List 6.8 Check Your Progress Questions 6.9 Answers to Check Your Progress Questions 6.10 Summary 6.11 Key Words 6.12 Self-Assessment Questions and Exercises 6.13 Further Readings UNIT -VII: OPERATION ON LINKED LIST 60-66 7.1 Introduction 7.2 Objectives 7.3 Insertion and Deletion Operations in Linked List 7.4 Check Your Progress Questions 7.5 Answers to Check Your Progress Questions 7.6 Summary  7.7 Key Words 7.8 Self-Assessment Questions and Exercises 7.9 Further Readings UNIT -VIII: TRAVERSAL 67-71 8.1 Introduction 8.2 Objectives 8.3 Traversing Linked Lists 8.4 Representation of Linked List 8.5 Check Your Progress Questions 8.6 Answers to Check Your Progress Questions 8.7 Summary 8.8 Key Words 8.9 Self-Assessment Questions and Exercises 8.10 Further Readings BLOCK : III NON-LINEAR DATA STRUCTURE UNIT -IX: TREES 72-81 9.1 Introduction 9.2 Objectives 9.3 Binary Trees 9.4 Types of Binary Tree 9.5 Binary Tree Representations 9.6 Check Your Progress Questions 9.7 Answers to Check Your Progress Questions 9.8 Summary 9.9 Key Words 9.10 Self-Assessment Questions and Exercises 9.11 Further Readings UNIT -X: BINARY TREE OPERATIONS / APPLICATIONS 82-87 10.1 Introduction 10.2 Objectives 10.3 Traversing Binary trees 10.4 Binary Search Tree 10.5 Traversing a Binary Search Tree 10.6 Check Your Progress Questions 10.7 Answers to Check Your Progress Questions 10.8 Summary 10.9 Key Words 10.10Self-Assessment Questions and Exercises 10.11 Further Readings UNIT -XI: OPERATIONS ON BINARY TREE 88-105 11.1 Introduction 11.2 Objectives 11.3 Insertion and Deletion Operations 11.4 Hashing Techniques 11.5 Check Your Progress Questions 11.6 Answers to Check Your Progress Questions  11.7 Summary 11.8 Key Words 11.9 Self-Assessment Questions and Exercises 11.10 Further Readings BLOCK IV : SEARCHING TECHNIQUES UNIT -XII: SEARCHING 106-111 12.1 Introduction 12.2 Objectives 12.3 Searching 12.4 Linear Search 12.5 Binary Search 12.13 Check Your Progress Questions 12.6 Answers to Check Your Progress Questions 12.7 Summary 12.8 Key Words 12.9 Self-Assessment Questions and Exercises 12.10 Further Readings BLOCK V : SORTING TECHNIQUES UNIT -XIII: SORTING 112-120 13.1 Introduction 13.2 Objectives 13.3 Definition 13.4 Bubble Sort 13.5 Insertion Sort 13.6 Radix Sort 13.7 Check Your Progress Questions 13.8 Answers to Check Your Progress Questions 13.9 Summary 13.10 Key Words 13.11 Self-Assessment Questions and Exercises 13.12 Further Readings UNIT -XIV: OTHER SORTING TECHNIQUES 121-128 14.1 Introduction 14.2 Objectives 14.3 Selection Sort 14.4 Quick Sort 14.5 Tree Sort 14.6 Check Your Progress Questions 14.7 Answers to Check Your Progress Questions 14.8 Summary 14.9 Key Words 14.10 Self-Assessment Questions and Exercises 14.11 Further Readings  Introduction to Data Structure BLOCK – I INTRODUCTION [ T y UNIT- I INTRODUCTION TO DATA p NOTES STRUCTURE e Structure 1.1 Introduction t 1.2 Objectives h 1.3 Types of data structures e 1.3.1 Linear Data Structures 1.3.2 Non-Linear Data Structures s 1.4 Algorithms 1.4.1 Time and space complexity of algorithms i 1.5 Check your progress questions d 1.6 Answers to check your progress questions e 1.7 Summary b 1.8 Key Words a 1.9 Self-Assessment Questions and Exercises r 1.10 Further Readings 1. 1 Introduction c Data Structure can be defined as the group of data elements which o provides an efficient way of storing and organizing data in the n computer so that it can be used efficiently. Some examples of Data t Structures are arrays, Linked List, Stack, Queue, etc. Data Structures are widely used in almost every aspect of Computer Science i.e. e operating System, Compiler Design, Artificial intelligence, Graphics n and many more. t. Need for data structure: A A data structure helps you to understand the relationship of one data element with the other and organize it within the memory. s Sometimes the organization might be simple. E.g.: List of names of i months in a year –Linear Data Structure, List of historical places in the d world- Non-Linear Data Structure. A data structure helps you to e analyze the data, store it and organize it in a logical and mathematical b manner. a r Data and Information 1. Raw facts gathered about a condition, event, idea, entity or anything else which is bare and random, is called data. i Information refers to facts concerning a particular event or s subject, which are refined by processing. 2. Data are simple text and numbers, while information is a processed and interpreted data. s 1 t a Self instructional materials n d a  Data is in an unorganized form, i.e. it is randomly collected facts and Introduction to Data figures which are processed to draw conclusions. On the other hand, when Structure the data is organized, it becomes information, which presents data in a better way and gives meaning to it. 1.2 Objectives After going through the unit you will be able to; NOTES  Discuss Primitive data types  Understand composite data types  Explain Linear and non-linear data structure  Analyze abstract data types 1.3 Types of Data Structures Primitive Data Structures Primitive Data Structures are the basic data structures that directly operate upon the machine instructions. They have different representations on different computers. For example, integer, character, and string are all primitive data types. Programmers can use these data types when creating variables in their programs. Non-primitive Data Structures Non-primitive data structures are more complicated data structures and are derived from primitive data structures. 1.3.1 Linear Data Structures A data structure is called linear if all of its elements are arranged in the linear order. In linear data structures, the elements are stored in non- hierarchical way where each element has the successors and predecessors except the first and last element. 2 Self instructional materials  Introduction to Data Types of Linear Data Structures are given below: Structure  Arrays: An array is a collection of similar type of data items [ and each data item is called an element of the array. The data T type of the element may be any valid data type like char, int, y NOTES float or double. The elements of array share the same variable p name but each one carries a different index number known as e subscript. The array can be one dimensional, two dimensional or multidimensional. t  Linked List: Linked list is a linear data structure which is used h to maintain a list in the memory. It can be seen as the collection of nodes stored at non-contiguous memory locations. Each node e of the list contains a pointer to its adjacent node.  Stack: Stack is a linear list in which insertion and deletions are s allowed only at one end, called top. A stack is an abstract data i type (ADT), can be implemented in most of the programming d languages. It is named as stack because it behaves like a real- e world stack, for example: - piles of plates or deck of cards etc. b  Queue: Queue is a linear list in which elements can be inserted a only at one end called rear and deleted only at the other end r called front.It is an abstract data structure, similar to stack. Queue is opened at both end therefore it follows First-In-First- Out (FIFO) methodology for storing the data items. c o 1.3.2 Non Linear Data Structures n This data structure does not form a sequence i.e. each item or element is t connected with two or more other items in a non-linear arrangement. e The data elements are not arranged in sequential structure. n t Types of Non Linear Data Structures are given below:.  Trees: Trees are multilevel data structures with a hierarchical relationship among its elements known as nodes. The bottommost nodes in the hierarchy are called leaf node while A the topmost node is called root node. Tree data structure is based on the parent-child relationship among the nodes. Each s node contains pointers that points to the child node. Each node i in the tree can have more than one children except the leaf d nodes whereas each node can have at most one parent except the e root node. Trees can be classified into many categories which b will be discussed later. a r  Graphs: Graphs can be defined as the pictorial representation of the set of elements (represented by vertices) connected by the links known as edges. A graph is different from tree in the sense i that a graph can have cycle while the tree cannot have the one. s Primitive Data Types a s 3 t a Self instructional materials n d a  Basically, primitive data types, as the name is self-explanatory, are Introduction to Data the data types that already come with the programming Structure language completely ready for the programmer’s use. NOTES 1.4 Algorithms An algorithm is a procedure having well defined steps for solving a particular problem. Algorithm is finite set of logic or instructions, written in order for accomplish the certain predefined task. It is not the complete program or code, it is just a solution (logic) of a problem, which can be represented either as an informal description using a Flowchart or Pseudo code. Characteristics of an Algorithm An algorithm must follow the mentioned below characteristics:  Input: An algorithm must have 0 or well defined inputs.  Output: An algorithm must have 1 or well defined outputs, and should match with the desired output.  Feasibility: An algorithm must be terminated after the finite number of steps.  Independent: An algorithm must have step-by-step directions which is independent of any programming code.  Unambiguous: An algorithm must be unambiguous and clear. Each of their steps and input/outputs must be clear and lead to only one meaning. The major categories of algorithms are given below:  Sort: Algorithm developed for sorting the items in certain order.  Search: Algorithm developed for searching the items inside a data structure. 4 Self instructional materials  Introduction to Data  Delete: Algorithm developed for deleting the existing element Structure from the data structure. [  Insert: Algorithm developed for inserting an item inside a data T structure. y NOTES  Update: Algorithm developed for updating the existing element p inside a data structure. e 1.4.1 Time and space complexity of algorithms t Sometimes, there are more than one way to solve a problem. We need h to learn how to compare the performance different algorithms and e choose the best one to solve a particular problem. While analysing an algorithm, we mostly consider time complexity and space complexity. s Time complexity of an algorithm quantifies the amount of time taken i by an algorithm to run as a function of the length of the input. d Similarly, Space complexity of an algorithm quantifies the amount of e space or memory taken by an algorithm to run as a function of the length of the input. b a The performance of algorithm is measured on the basis of following r properties: c  Time complexity: It is a way of representing the amount of o time needed by a program to run to the completion. n t  Space complexity: It is the amount of memory space required e by an algorithm, during a course of its execution. Space n complexity is required in situations when limited memory is available and for the multi user system. t. Each algorithm must have: A  Specification: Description of the computational procedure.  Pre-conditions: The condition(s) on input. s  Body of the Algorithm: A sequence of clear and unambiguous i instructions. d  Post-conditions: The condition(s) on output. e Example: Design an algorithm to multiply the two numbers x and y b and display the result in z. a o Step 1 START r o Step 2 declare three integers x, y & z i o Step 3 define values of x & y s o Step 4 multiply values of x & y o Step 5 store the output of step 4 in z a o Step 6 print z o Step 7 STOP s 5 t a Self instructional materials n d a  Introduction to Data Asymptotic analysis Structure Asymptotic analysis of an algorithm refers to defining the mathematical foundation/framing of its run-time performance. Using asymptotic analysis, we can very well conclude the best case, average case, and worst case scenario of an algorithm. NOTES Usually, the time required by an algorithm falls under three types  Best Case − Minimum time required for program execution.  Average Case − Average time required for program execution.  Worst Case − Maximum time required for program execution. Asymptotic Notations Following are the commonly used asymptotic notations to calculate the running time complexity of an algorithm.  Ο Notation  Ω Notation  θ Notation Big O Notation The Big O notation defines an upper bound of an algorithm, it bounds a function only from above. It is used for estimating the rate of function growth. It was introduced by Paul Bachmann in 1894. f(n) is O(g(n)) if there exist positive numbers c and N such that f(n)≤ c.g(n), ∀𝑛 ≥ 𝑁 i.e., f is not larger than c.g(n) for sufficiently large ns. g(n) is an upper- bound on the value of f(n), where g(n) is the given function and f(n) is the analysing function. Ω Notation Just as Big O notation provides an asymptotic upper bound on a function, Ω notation provides an asymptotic lower bound. 6 Self instructional materials  Introduction to Data f(n) is Ω(g(n)) if there exist positive numbers c and N such that Structure [ f(n) ≥ 𝑐. 𝑔(𝑛), ∀ 𝑛 ≥ 𝑁. T i.e., c.g(n) is a lower bound on the size of f(n). Ω provides a lower y NOTES bound for the value of f(n). p e t h e s i d e b a r Θ Notation c o The theta notation bounds a function from above and below, so it n defines exact asymptotic behavior. t e The function f(n) is Θ(g(n)), if there exist positive numbers c1,c2 and N n such that t 𝑐1. 𝑔(𝑛) ≤ 𝑓(𝑛) ≤ 𝑐2. 𝑔(𝑛), ∀𝑛 ≥ 𝑁. i.e., f(n) is Θ(g(n)) if f(n) is O(g(n)) and f(n) is Ω(g(n)). A i.e., f(n) is Θ(g(n)) if and only if g(n) is both an upper bound and lower bound on f(n). s i d e b a r i s a 1.5 Check your progress questions s 7 t a Self instructional materials n d a  1. What is data structure? Introduction to Data 2. What is time and space complexity? Structure 1.6 Check your progress questions 1) A data structure is a specialized format for organizing, processing, retrieving and storing data. 2) Time complexity of an algorithm quantifies the amount NOTES of time taken by an algorithm to run as a function of the length of the input. Similarly, Space complexity of an algorithm quantifies the amount of space or memory taken by an algorithm to run as a function of the length of the input. 1.7 Summary  Each programming language provides various data types and each data type is represented differently within the computer’s memory.  The memory requirement of a data type determines the permissible range of values for that data type.  The data types can be classified into several categories, including primitive data types and composite data types.  The data types provided by a programming language are known as primitive data types or in-built data types.  In addition to primitive and composite data types, programming languages allow the user to define new data types (or user-defined data types) as per his requirements.  Generally, handling small problems is much easier than handling comparatively larger problems.  The size of each module is kept as small as possible and if required, other modules are invoked from it.  Second, a well-designed modular program has modules independent of each other’s, implementation, which will make the program easily modifiable.  An abstract data type (ADT) is an extension of a modular design in a way that the set of operations of an ADT are defined at a formal, logical level, and nowhere in ADT’s definition, it is mentioned how these operations are implemented.  The basic idea of ADT is that the implementation of the set of operations are written once in the program and the part of program which needs to perform an operation on ADT accomplishes this by invoking the required operation.  If there is a need to change the implementation details of an ADT, the change will be completely transparent to the programs using it.  The logical or mathematical model used to organize the data in main memory is called a data structure.  These features should be kept in mind while choosing a data structure for a particular situation.  The choice of a data structure depends on its simplicity and effectiveness in processing of data.  Data structures are divided into two categories, namely, linear data structure and non-linear data structure. 8 Self instructional materials  Introduction to Data  A linear data structure is one in which its elements form a Structure sequence. It means each element in the structure has a unique [ predecessor and a unique successor. T  A finite collection of homogenous elements is termed as an y NOTES array. p  The elements of an array are always stored in a contiguous e memory locations irrespective of the array size.  A stack is a linear list of data elements in which the addition of t a new element or the deletion of an element occurs only at one h end. e  A queue is a linear data structure in which the addition or insertion of a new element occurs at one end, called ‘Rear’, and deletion of an element occurs at other end, called ‘Front’. s  A tree consists of multiple nodes, with each node containing i zero, one or more pointers to other nodes called child nodes. d e 1.8 Keywords b a  Traversing: It means accessing all the data elements one by r one to process all or some of them.  Substitution method: In this method, a reasonable guess for the c solution is made and it is proved through mathematical induction. o  Recursion tree: In this method, recurrences are represented as a n tree whose nodes indicate the cost that is incurred at the various t levels of recursion. e  Searching: It is the process of finding the location of a given n data element in the data structure. t  Insertion: It means adding a new data element in the data. structure. A new element can be inserted anywhere in the structure, such as in the beginning, in the end, or in the middle. A  Deletion: It means removing any existing data element from the data structure. s  Sorting: It is the process of arranging all the elements of a data structure in a logical order such as ascending or descending i order. d  Merging: It is the process of combining the elements of two e sorted data structures into a single sorted data structure. b a 1.9 Self-Assessment Questions and Exercises r Short-Answer Questions i 1. Write a short note on abstract data types. 2. Write some points of differences between linear and non-linear data s structures. 3. What are the different operations on data structures? a 4. What are algorithms? 5. What are the various asymptotic notations? s 9 t a Self instructional materials n d a  6. Explain big O notation. Introduction to Data Structure Long-Answer Questions 1. “The data types provided by a programming language are known as primitive data types or in-built data types. Different programming languages provide different set of primitive data types.” Discuss in detail. 2. “If there is a need to change the implementation details of an ADT, the NOTES change will be completely transparent to the programs using it.” Explain. 3. Write a detailed note on Algorithm Design Techniques. 4. What do you mean by time and space complexity of algorithms? 1.8 Further Readings Storer, J.A. 2012. An Introduction to Data Structures and Algorithms. New York: Springer Publishing. Preiss, Bruno. 2008. Data Structures and Algorithms with Object-Oriented Design Patterns in C++. London: John Wiley and Sons. Pandey, Hari Mohan. 2009. Data Structures and Algorithms. New Delhi: Laxmi Publications. Goodrich Michael, Tamassia Roberto and Michael H. Goldwasser. 2014. Data Structures and Algorithms in Java. London: John Wiley and Sons. McMillan, Michael. 2007. Data Structures and Algorithms Using C#. Cambridge, UK: Cambridge University Press. 10 Self instructional materials  Arrays UNIT - II ARRAYS [ Structure T 2.1 Introduction y 2.2 Objectives p NOTES 2.3 Arrays e 2.3.1 Definition 2.3.2 Initialization 2.3.3 Characteristic t 2.4 Types of Array h 2.4.1 Single-Dimensional Array e 2.4.2 Multi-Dimensional Array 2.5 Check your progress s 2.6 Answers to check your progress questions i 2.7 Summary d 2.8 Key Words e 2.9 Self-Assessment Questions and Exercises b 2.10 Further Readings a 2.1 Introduction r Array stores a fixed-size sequential collection of elements of the same type. An array is used to store a collection of data, but it is often more useful to think of an array as a collection of variables of the same type. c o Instead of declaring individual variables, such as number0, number1, n..., and number99, you declare one array variable such as numbers and t use numbers, numbers, and..., numbers to represent individual variables. A specific element in an array is accessed by an e index. All arrays consist of contiguous memory locations. The lowest n address corresponds to the first element and the highest address to the t last element.. A s i d e b 2.2 Objectives a r After going through this unit, the learner will be able to understand i  Array initialization and characterization s  Types of Arrays a s 11 t a Self instructional materials n d a  2.3 Arrays Arrays An array is a data structure that contains a group of elements. Typically these elements are all of the same data type, such as an integer, float, character or string. Arrays are commonly used in computer programs to NOTES organize data so that a related set of values can be easily sorted or searched. int no={10,20,30}; float no={1.5,2.7,8.9}; 2.3.1 Definition An array is a collection of elements of the same type placed in contiguous memory locations that can be individually referenced by using an index to a unique identifier. 2.3.2 Initialization An array can be initialized in two ways.  By declaring and initializing it simultaneously. int arr[] = { 10, 20, 30, 40 }  By declaring it first and initializing it later during run time. 2.3.3 Characteristics  An array holds elements that have the same data type  Array elements are stored in subsequent memory locations  Two-dimensional array elements are stored row by row in subsequent memory locations  Array name represents the address of the starting element  Array size should be mentioned in the declaration.  Array size must be a constant expression and not a variable. 2.4 Types of Arrays  One dimensional (1-D) arrays or Linear arrays.  Multi-dimensional arrays.  Two dimensional (2-D) arrays or Matrix arrays.  Three dimensional arrays. 2.4.1 Single-Dimensional Arrays 12 Self instructional materials  Arrays A single-dimensional array is defined as an array in which only one subscript value is used to access its elements. [ T y p NOTES e t h e Before using an array in a program, it needs to be declared. The syntax of declaring a single-dimensional array in C is as follows: s data_type array_name[size]; i where, d data_type = data type of elements to be stored in array e array_name = name of the array b size = the size of the array indicating that the lower bound of the a array is 0 and the upper bound is size-1. Hence, the value of the subscript ranges from 0 to size-1. r c o n t e n t. For example, in the statement int array, an integer array of ten elements is declared and the array elements are indexed from 0 to 9. A Once the compiler reads a single-dimensional array declaration, it allocates a specific amount of memory for the array. Memory is s allocated to the array at the compile-time before the program is executed. i d e Working with single dimensional array b An array can be initialized in two ways. It can be done by declaring and a initializing it simultaneously or by accepting elements of the already r declared array from the user. Once an array is declared and initialized, the elements stored in it can be accessed any time. These elements can i be accessed by using a combination of the name of an array and s subscript value. A program to illustrate the initialization of two arrays and display their a elements is as follows: #include #include s 13 t a Self instructional materials n d a  #define MAX 5 Arrays void main() { int A[MAX]={1,2,3,4,5}; int B[MAX], i; clrscr(); NOTES printf(“Enter the elements of array B:\n”); for (i=0;itop == stack->capacity - 1; } NOTES // Stack is empty when top is equal to -1 int isEmpty(struct Stack* stack) { return stack->top == -1; } // Function to add an item to stack. It increases top by 1 void push(struct Stack* stack, int item) { if (isFull(stack)) return; stack->array[++stack->top] = item; printf("%d pushed to stack\n", item); } // Function to remove an item from stack. It decreases top by 1 int pop(struct Stack* stack) { if (isEmpty(stack)) return INT_MIN; return stack->array[stack->top--]; } // Function to return the top from stack without removing it int peek(struct Stack* stack) { if (isEmpty(stack)) return INT_MIN; return stack->array[stack->top]; } // Driver program to test above functions int main() { struct Stack* stack = createStack(100); push(stack, 10); push(stack, 20); push(stack, 30); printf("%d popped from stack\n", pop(stack)); return 0; } 3.5 Check Your Progress Questions 1. Define Stack. 2. List out the operations on stack. 24 Self instructional materials  Linear Data Structure 3.6 Answers to Check Your Progress Questions 1. Stack is a linear data structure which follows a particular order in which the operations are performed. The order may be NOTES LIFO(Last In First Out) or FILO. 2. Push(), Pop(), isEmpty(), isFull() 3.5 Summary  A stack can be organized (represented) in the memory either as an array or as a singly-linked list.  Though array representation is a simple technique, it provides less flexibility and is not very efficient with respect to memory utilization.  When a stack is organized as an array, a variable named Top is used to point to the top element of the stack.  An array representation of a stack is static, but linked list representation is dynamic in nature  When a stack is organized as an array, a variable named Top is used to point to the top element of the stack. Initially, the value of Top is set as -1 to indicate an empty stack.  Overflow occurs when a stack is full and there is no space for a new element and an attempt is made to push a new element.  When a stack is organized as an array, a variable named Top is used to point to the top element of the stack.  Similarly, before removing the top element from the stack, it is necessary to check the condition of underflow.  To POP (or remove) an element from a stack, the element at the top of the stack is assigned to a local variable and then Top is decremented by one. 3.7 Key Words  Overflow: It occurs when a stack is full and there is no space for a new element and an attempt is made to push a new element.  Stack: It is an abstract data type that serves as a collection of elements, with two principal operations: push, which adds an element to the collection, and pop, which removes the most recently added element that was not yet removed.  Underflow: An error condition that occurs when an item is called for from the stack, but the stack is empty. Contrast with stack overflow. 3.8 Self-Assessment Questions and Exercise Short-Answer Questions 1. What is a stack? 25 Self instructional materials  2. How is a stack organized? Linear Data Structure 3. What do you mean by overflow in a stack? 4. Explain stack underflow. 5. Give the algorithm to push elements into stack. 6. Give the algorithm to pop elements from stack. NOTES Long-Answer Questions 1. Write a program to implement a stack as an array. 2. How can you insert elements in a stack? Explain. 3. Write a note on the operations on stack. 3.13 Further Readings Storer, J.A. 2012. An Introduction to Data Structures and Algorithms. New York: Springer Publishing. Preiss, Bruno. 2008. Data Structures and Algorithms with Object-Oriented Design Patterns in C++. London: John Wiley and Sons. Pandey, Hari Mohan. 2009. Data Structures and Algorithms. New Delhi: Laxmi Publications. Goodrich Michael, Tamassia Roberto and Michael H. Goldwasser. 2014. Data Structures and Algorithms in Java. London: John Wiley and Sons. McMillan, Michael. 2007. Data Structures and Algorithms Using C#. Cambridge, UK: Cambridge University Press. 26 Self instructional materials  Representation Of Stack UNIT – IV REPRESENTATION OF [ T STACK y Structure p NOTES e 4.1 Introduction 4.2 Objectives t 4.3 Application and Implementation of Stack h 4.3.1 Converting Infix Notation to Postfix and Prefix or Polish e Notations 4.4 Check your progress 4.5 Summary s 4.6 Key Words i 4.7 Self-Assessment Questions and Exercises d 4.8 Further Readings e b 4.1 Introduction a r A stack is an abstract data type and it serves as a collection of elements, with two primary principal operations: push, and pop. Push adds an c element to the collection and pop removes the most recently added o element. As in this unit, we will see the application and implementation n of stacks. t e 4.2 Objectives n After going through this unit, you will be able to: t  Explain what are stacks.  Discuss the application of stacks  Analyse the implementation of stacks A 4.2 Application and Implementation of Stack s i d Stacks are used where the last-in-first-out principle is required like e reversing strings, checking whether the arithmetic expression is b properly parenthesized, converting infix notation to postfix and prefix notations, evaluating postfix expressions, implementing recursion and a function calls, etc. r Reversing Strings i A simple application of stacks is reversing strings. To reverse a string, s the characters of a string are pushed onto a stack one by one as the string is read from left to right. Once all the characters of the string are a pushed onto the stack, they are popped one by one. Since the character s 27 t a Self instructional materials n d a  last pushed in comes out first, subsequent POP operations result in reversal Representation Of Stack of the string. For example, to reverse a string ‘REVERSE’, the string is read from left to right and its characters are pushed onto a stack, starting from the letter R, then E, V, E, and so on NOTES Algorithm for string reversal reversal(s, str) 1. Set i = 0 2. While(i < length_of_str) Push str[i] onto the stack Set i = i + 1 End While 3. Set i = 0 4. While(i < length_of_str) Pop the top element of the stack and store it in str[i] Set i = i + 1 End While 5. Print “The reversed string is: ”, str 6. End 4.3.1 Converting Infix Notation to Postfix and Prefix or Polish Notations The general way of writing arithmetic expressions is known as infix notation where the binary operator is placed between two operands on which it operates. For simplicity, expressions containing unary operators have been ignored. For example, the expressions ‘a+b’ and ‘(a–c)*d’, ‘[(a+b)*(d/f)–f]’ are in infix notation. The order of evaluation of these expressions depends on the parentheses and the precedence of operators. For example, the order of evaluation of the expression ‘(a+b)*c’ is different from that of ‘a+(b*c)’. As a result, it is difficult to evaluate an expression in an infix notation. Thus, the arithmetic expressions in the infix notation are converted to another notation which can be easily evaluated by a computer system to produce a correct result. A Polish mathematician Jan Lukasiewicz suggested two alternative notations to represent an arithmetic expression. In these notations, the operators can be written either before or after the operands on which they operate. The notation in which an operator occurs before its operands is known as the prefix notation (also known as Polish notation). For example, 28 Self instructional materials  Representation Of Stack the expressions ‘+ab’ and ‘*– acd’ are in prefix notation. On the other hand, the notation in which an operator [ occurs after its operands is known as the postfix notation (also known T as Reverse Polish or suffix notation). For example, the expressions y ‘ab+’ and ‘ac–d*’ are in postfix notation. p NOTES e Advantages of Prefix notation A characteristic feature of prefix and postfix notations is that the order t of evaluation of expression is determined by the position of the operator h and operands in the expression. That is, the operations are performed in e the order in which the operators are encountered in the expression. Hence, parentheses are not required for the prefix and postfix notations. Moreover, while evaluating the expression, the precedence of operators s is insignificant. As a result, they are compiled faster than the i expressions in infix notation. d Conversion of infix to prefix notation e b In infix to prefix conversion the infix notation is scanned in reverse order, that is, from right to left. Therefore, the stack in this case stores a the operators and the closing (right) parenthesis. r Algorithm for infix to prefix conversion c infixtoprefix(s, infix, prefix) o 1. Set i = 0 n 2. While (i < number_of_symbols_in_infix) t If infix[i] is a whitespace or comma e Set i = i + 1 go to step 2 n If infix[i] is an operand, add it to prefix t Else If infix[i] = ‘)’, push it onto the stack Else If infix[i] is an operator, follow these steps:. i. For each operator on the top of stack whose precedence is greater A than or equal to the precedence of the current operator, pop the operator from stack and add it s to prefix i ii. Push the current operator onto the stack Else If d infix[i] = ‘(’, follow these steps: e i. Pop each operator from top of the stack and add it to prefix until ‘)’ is b encountered in the stack a ii. Remove ‘)’ from the stack and do not r add it to prefix End If i Set i = i + 1 s End While 3. Reverse the prefix expression a 4. End s 29 t a Self instructional materials n d a  For example, consider the conversion of the following infix expression to a Representation Of Stack prefix expression: a-(b+c)*d/f The step-wise conversion of the expression a-(b+c)*d/f into its equivalent prefix expression is shown. Note that initially ‘)’ is pushed onto the stack, and ‘(’ is inserted in the beginning of the infix expression. Since the infix expression is scanned from right to left, but elements are inserted in the NOTES resultant expression from left to right, the prefix expression needs to be reversed. 4.4 Check Your Progress 1) What is a characteristic feature of prefix and postfix notation? 2) Where are stacks used? 3) Where is stack used during evaluation? 4.5 Summary  Stacks are used where the last-in-first-out principle is required like reversing strings.  A simple application of stacks is reversing strings. To reverse a string, the characters of a string are pushed onto a stack one by one as the string is read from left to right.  Once all the characters of the string are pushed onto the stack, they are popped one by one.  Since the character last pushed in comes out first, subsequent POP operations result in reversal of the string.  The general way of writing arithmetic expressions is known as infix notation where the binary operator is placed between two operands on which it operates.  A characteristic feature of prefix and postfix notations is that the order of evaluation of expression is determined by the position of the operator and operands in the expression.  To convert an arithmetic expression from an infix notation to a postfix notation, the precedence and associativity rules of operators should always kept in mind. 30 Self instructional materials  Representation Of Stack  The conversion of an infix expression to a prefix expression is similar to the conversion of infix to postfix expression. [  In a computer system, when an arithmetic expression in an infix T notation needs to be evaluated, it is first converted into its y postfix notation. p NOTES  Evaluation of postfix expressions is also implemented through e stacks. Representation of Stack  Since the postfix expression is evaluated in the order of t appearance of operators, parentheses are not required in the h postfix expression. e  During evaluation, a stack is used to store the intermediate results of evaluation.  Since an operator appears after its operands in a postfix s expression, the expression is evaluated from left to right. i  If the element is an operand, it is pushed onto the stack. d  If two or more stacks are needed in a program, then it can be e accomplished in two ways. b a 4.6 Keywords r  Stack: It is an abstract data type that serves as a collection of c elements, with two principal operations- push and pop. o  Reversing Strings: It is a simple application of stacks. To n reverse a string, the characters of a string are pushed onto a t stack one by one as the string is read from left to right. e  Prefix Notation: It is also called polish notation. It is simply a n mathematical notation where the operators precede the t operands.. 4.7 Self-assessment questions and exercise A Short-Answer Questions 1. Write the algorithm for reversing a string. s 2. Write a short note on stacks. i 3. Discuss the application of stacks. d 4. Discuss the advantages of polish notation. e Long-Answer Questions b 1. What do you mean by implementation of stack? Discuss in detail. a 2. Write a program to reverse a given string using stacks. r 3. Write a detailed note on Conversion of infix to prefix notation. 4. State and explain an algorithm to convert an expression from infix notation to prefix notation. i s 4.8 Further Readings a Storer, J.A. 2012. An Introduction to Data Structures and Algorithms. New s 31 t a Self instructional materials n d a  York: Springer Publishing. Representation Of Stack Preiss, Bruno. 2008. Data Structures and Algorithms with Object-Oriented Design Patterns in C++. London: John Wiley and Sons. Pandey, Hari Mohan. 2009. Data Structures and Algorithms. New Delhi: Laxmi Publications. Goodrich Michael, Tamassia Roberto and Michael H. Goldwasser. 2014. NOTES Data Structures and Algorithms in Java. London: John Wiley and Sons. McMillan, Michael. 2007. Data Structures and Algorithms Using C#. Cambridge, UK: Cambridge University Press. 32 Self instructional materials  Queues UNIT- V QUEUES [ T NOTES Structure y 5.1 Introduction p 5.2 Objectives e 5.3 Queues 5.3.1 Operations on Queues 5.4 Representation of Queues t 5.5 Circular Queue h 5.6 Applications of Queues e 5.7 Check your progress 5.8 Answers to check your progress s 5.9 Summary i 5.9 Key Words d 5.10 Self-Assessment Questions and Exercises e 5.11 Further Readings b a 5.1 Introduction r A Queue is an abstract data structure which is somewhat similar to Stacks. But unlike stacks, a queue is open at both its ends. One end of a c queue is always used to ins rt data (called enqueue) and the other is o used to remove data (called dequeue). Queue follows the basic and n simple First-In-First-Out methodology, which means that the data item t stored first will be accessed first. e n 5.2 Objectives t. After going through this unit, you will be able to:  Understand queues A  Discuss the representation of queues  Analyse circular queues and deque s  Explain about priority queues i  List the applications of queue. d e 5.3 Queues b a A queue is a linear data structure in which a new element is inserted at r one end and an element is deleted from the other end. The end of the queue from which the element is deleted is known as the Front and the i end at which a new element is added is known as the Rear. s a s 33 t a Self instructional materials n d a  5.3.1 Operations on Queues Queues Operations Description NOTES enqueue() This function defines the operation for adding an element into queue. dequeue() This function defines the operation for removing an element from queue. init() This function is used for initializing the queue. Front Front is used to get the front data item from a queue. Rear Rear is used to get the last item from a queue. 5.4 Representation of Queues Like stacks, queues can be represented in the memory by using an array or a singly linked list. We will discuss how a queue can be implemented using an array. Array Implementation of a Queue When a queue is implemented as an array, all the characteristics of an array are applicable to the queue. Since an array is a static data structure, the array representation of a queue requires the maximum size of the queue to be predetermined and fixed. As we know that a queue keeps on changing as elements are inserted or deleted, the maximum size should be large enough for a queue to expand or shrink. struct queue { int item[MAX]; int Front; int Rear; }; The representation of a queue as an array needs an array to hold the elements of the queue and two variables Rear and Front to keep track of the rear and the front ends of the queue, respectively. Initially, the value of Rear and Front is set to –1 to indicate an empty queue. Before we insert a new element in the queue, it is necessary to test the condition of overflow. A queue is in a condition of overflow (full) when Rear is equal to MAX–1, where MAX is the maximum size of the array. If the queue is not full, the 34 Self instructional materials  Queues insert operation can be performed. To insert an element in the queue, Rear is incremented by one and the element is inserted at [ that position. T NOTES y Similarly, before we delete an element from a queue, it is p necessary to test the condition of underflow. A queue is in the e condition of underflow (empty) when the value of Front is –1. If a queue is not empty, the delete operation can be performed. To t delete an element from a queue, the element referred by Front is assigned to a local variable and then Front is incremented by h one. The total number of elements in a queue at a given point of e time can be calculated from the values of Rear and Front given as follows: s i Number of elements = Rear – Front + 1 d e To understand the implementation of a queue as an array in b detail, consider a queue stored in the memory as an array named a Queue that has MAX as its maximum number of elements. Rear and Front store the indices of the rear and front elements of r Queue. Initially, Rear and Front are set to –1 to indicate an empty queue. c o n t e n t. Whenever a new element has to be inserted in a queue, Rear is incremented by one and the element is stored at Queue[Rear]. Suppose A an element 9 is to be inserted in the queue. In this case, the rear is incremented from –1 to 0 and the element is stored at Queue. Since s it is the first element to be inserted, Front is also incremented by one to make it to refer to the first element of the queue. For subsequent i insertions, the value of Rear is incremented by one and the element is d stored at Queue[Rear]. e b a r i s a However, Front remains unchanged. Observe that the front and rear elements of the queue are the first and last elements of the list, s 35 t a Self instructional materials n d a  respectively. Whenever, an element is to be deleted from a queue, Front is incremented by one. Suppose that an element is to be deleted from Queue. Queues Then, here it must be 9. It is because the deletion is always made at the front end of a queue. Deletion of the first element results in the queue as shown in Similarly, deletion of the second element results in the queue. NOTES Observe that after deleting the second element from the queue, the values of Rear and Front are equal. Here, it is apparent that when values of Front and Rear are equal other than –1, there is only one element in the queue. When this only element of the queue is deleted, both Rear and Front are again made equal to –1 to indicate an empty queue. Further, suppose that some more elements are inserted and Rear reaches the maximum size of the array. This means that the queue is full and no more elements can be inserted in it even though the space is vacant on the left of the Front. We can use a one-dimensional array A of size n to represent a queue in memory. To manipulate the elements in the queue, we can use 2 pointers called as Front and Rear (f and r respectively). These pointers are initialized to -1. Basic Conditions: Empty Queue : f = -1, r = -1 Full Queue : r = n-1, where n is the size of the queue. Single element in Queue: f = r Algorithm for enqueue Algorithm Enqueue( ) { if ( r ==n-1) { 36 Self instructional materials  Queues Print”queue is full” } [ else T NOTES { y If(f= =-1) p { e f=0; } t r=r+1; q[r]=x h } e } Algorithm for dequeue s Algorithm Dequeue() i { d if ( f==-1 && r==-1) e { b Print”queue is empty” a } else r { Y=q[p] c If(f==r) o { n F=-1; t } e else n { f=f+1; t }. } } A Algorithm Display() s { if ( f ==-1 && r==-1 ) i { d Print”queue is empty” e } b else a { r for(i=f;iRear = MAX-1 AND q->Front = 0) OR (q->Rear + 1 = q->Front)) Print “Overflow: Queue is full!” and go to step 5 End If //check if circular queue is full