UNIT 2 3 stack queue linkedlist.pdf

Data Structure Prof. Vijya Tulsani, Assistant Professor IT and Computer Science  CHAPTER-2 Linear Data Structure Arrays It is a most commonly used data structure If you want to store group of data together in one place , than array is data structure that is most commonly use...

Data Structure Prof. Vijya Tulsani, Assistant Professor IT and Computer Science  CHAPTER-2 Linear Data Structure Arrays It is a most commonly used data structure If you want to store group of data together in one place , than array is data structure that is most commonly used. Arrays enable us to arrange more than one element, and so it is known as composite data structure. Arrays “Arrays are finite and ordered collection of Homogeneous data elements.” Arrays are finite because it contains only limited number of element. Arrays are ordered because all the elements are stored one by one in the computer memory. Arrays are homogeneous because all the elements of an array are of the same type only. Derived Data Type Simply, declaration of array is as follows: int a Where int specifies the data type or type of elements arrays stores. “a” is the name of array & the number specified inside the square brackets is the number of elements an array can store, this is also called sized or length of array. Base address of array is always 0. N=5 1st ele 2nd ele 3rd ele 4th ele 5th ele 4 8 7 9 10 Value of element a a a a a a = 1026 a = 1028 Arrays An individual element of the array can be accessed by specifying name of the array, following by index value inside square brackets. The first element of the array has index value. It means the first element and last element will be specified as: my_arr & my_arr Respectively. Following equation will give the number of elements that can be stored in an array, that is the size of array or its length. 5 Lowerbound : 0 Upperbound : 4 (n-1)(5-1) ( Ubound – lbound ) +1 For the above array it would be (19-0)+1=20, where 0 is lower bound of array and 19 is upper bound of array. Image source : Google Array - limitations It is wastage of memory sometimes It cannot work with elements of different data type. In arrays task of insertion and deletion is not easy It is also shortage of Memory- if we don’t know the size of memory in advance Image source : Youtube video Operations – Arrays Insertion of new array element Deletion of required array element Modification of an existing array element Merging of arrays in a single array Sort the array Search an element from array Image source : Google Array - Applications Arrays are used to implement mathematical vectors and matrices, as well as other kinds of rectangular tables. Databases, small as well as large, consisting of one-dimensional arrays whose elements are records. Arrays are also used to implement other data structures, such as lists, heaps, hash tables, deques, queues and stacks. A Int a 001 123 432 Image source : Google Types of Array 1. One Dimensional One dimensional array is having only one subscript also called an index value to access and store any element in the array. e.g. int s5 2. Two Dimensional One dimensional array is having two subscripts also called an index value to access and store any element in the array. e.g. int s5 n Array[rows][cols] Image source : Google Address Calculation in single (one) Dimension Array: Image source : Google Example Q:1: Consider an integer array A with the base address 1000 and calculate address of a Image source : Google Example A(2)=Lo+[c*(i-0)] =1100 + [4*(2-0)] =1100 + 8 =1108 Image source : Google 2-D array Also defined as an array of arrays. This type of 2D arrays is organized as matrices which can be represented as the collection of rows and columns. These 2D arrays can be created to implement a relational database lookalike data structure. 2D arrays are providing ease of holding the bulk of data at once which can be passed to any number of functions wherever required. Image source : Google 2-D array Just like 1D array, we must have to specify the data type, the name, and the size of the array. In this array size of the array is described as the number of rows and number of columns. Syntax: datatype array_name_2D[rows][columns]; Example: int twodimen_2D; a: array_2D [ 1.. 6, 1.. 5] of integer lb1 ub1lb2 ub2 Image source : Google 2-D array Image source : Google 2-D array a: array [ 1.. 5, 1.. 4] of integer lb1 ub1 lb2 ub2 Two type of representation: 1. Row major – Representation of array is row by row 2. Column major – Representation of array is column by column Row major: a [i,j] = SA + [(i-lb1) * (ub2-lb2+1) + (j-lb2)] * C column major: a [ i,j] = SA + [(j-lb1) * (ub2-lb2+1) + (i-lb2)] * C Image source : Google Example – 2D-array Image source : Google Sparse Matrix A matrix is called a two-dimensional data object made up of m rows and n columns, therefore having total m x n values. If in my matrix most of the elements of the matrix have 0 value, then it is called a sparse matrix. Here instead of storing zeroes with non-zero elements, we only store non-zero elements. That means we will store non-zero elements with triples- (Row, Column, value). Image source : Google Example 2D array will used to represent a sparse matrix in which there are three rows named as Row: Index of row, in which non-zero element is located Column: Index of column, in which non-zero element is located Value: Value of the non zero element located at index position – (row,column) Image source : Google Sparse Matrix Sparse matrix is the matrix which contains large no. of zeroes. 1 2 3 4 5 6 7 Consider the matrix given as shown in figure above 1 0 0 6 0 9 0 0 This matrix is commonly used in scientific applications and contains hundreds or even 2 2 0 0 7 8 0 4 thousands of rows and columns. Total storage requirement is 6X7 = 42 3 10 0 0 0 0 0 0 memory locations 4 0 0 12 0 0 0 0 5 0 0 0 0 0 0 0 6 0 0 0 3 0 0 5 Image source : Google  ROW column A 1 1 3 6 2 1 5 9 Total storage requirement = 3 * 10 = 30, so it saves 42 – 30 = 12 3 2 1 2 storage spaces. 4 2 4 7 2 5 1 2 3 4 5 6 7 5 8 6 2 7 4 1 0 0 6 0 9 0 0 7 3 1 10 2 2 0 0 7 8 0 4 8 4 3 12 3 10 0 0 0 0 0 0 9 6 4 3 4 0 0 12 0 0 0 0 10 6 7 5 5 0 0 0 0 0 0 0 6 0 0 0 3 0 0 5 7/11/2024 11:23:08 AM 22  ROW column A 1 1 1 3 6 2 3 2 5 9 Total storage 3 7 3 1 2 requirement is 6 + 20 = 26, so it saves total 4 8 4 4 7 16 storage units. 5 0 5 5 8 1 2 3 4 5 6 7 6 9 6 7 4 1 0 0 6 0 9 0 0 7 1 10 First 2 2 0 0 7 8 0 4 column 8 3 12 for row 3 10 0 0 0 0 0 0 number 9 4 3 4 0 0 12 0 0 0 0 10 7 5 5 0 0 0 0 0 0 0 6 0 0 0 3 0 0 5 7/11/2024 11:23:08 AM 23 Stack Stacks are also an ordered collection of elements like array, but having a special feature that deletion and insertion of elements can be done only from one end called the top of the stack (TOP) Stack is sometimes called as Last-In-First-Out (LIFO) lists i.e. the element which is inserted first in the stack, will be deleted last from the stack. Representation of stack in memory - Bottom Top - - 5 4 7 2 - - - Top 2 7 4 Bottom 5 5 Stack- Examples Arrangements of disk plates in a rack Playing cards is example of stack Social media – Instagram posts \ \ Image source : Google Terminology in stack 1. TOP: The pointer at the top most position of stack is called as TOP. It is the more commonly accessible element of stack. Insertion and deletion occur at top of the stacks. 2. BOTTOM The pointer at the last position of stack is called as BOTTOM. It is least commonly accessible element of the stack. 3. Stack overflow: If the stack is full and we are trying to insert new element into the stack, then system will give the stack overflow error. 4. Stack underflow: If the stack is empty and we are trying to delete element from the top of the stack then system will give the stack underflow error. Stack Representation A stack can also be implemented by means of Array, Structure, Pointer, and Linked List. It can either be a fixed size one or it may have a sense of dynamic resizing. Now we are going to implement stack using arrays, which will make it a fixed size stack implementation. Image source : Google Applications of Stack Recursion Expression evaluations and conversions Parsing Browsers Editors Tree Traversals Pros of Stack 1. Helps managing the data in particular way (LIFO) which will not be possible with Linked list and array. 2. When function has been called the local variables are stored in stack and destroyed once returned. Stack is used when variable will not be used outside the function. So, it will give control over how memory is allocated and deallocated 3. Stack frees you from the burden of remembering to cleanup(read delete) the object 4. Not easily corrupted data structure (No one can easily inset data in middle) Cons of Stack: 1. Stack memory will be limited. 2. Creating too many objects on the stack can increase the chances of stack overflow 3. Random access is not possible/allowed Features of Stack Stack is an ordered list of similar type of data type. Stack is called a LIFO(Last in First out) structure or we can say FILO(First in Last out). push() function will be used to insert new elements into the Stack and pop() function will be used to remove an element from the stack. Both insertion and removal are allowed at only one end of Stack called Top. n Operations on Stack 1. PUSH : To insert an item into the stack data structure 2. POP : To remove an item from a stack data structure. 3. PEEP : To find I th element from stack data structure. 4. CHANGE : To change I th element from stack data structure. Algorithms – PUSH() - insert PUSH (Stack, TOP, Item) This procedure will insert an element Item into the stack which is represented by array containing N elements with the pointer TOP denoting top element in the stack. Step 1: [Check for stack overflow?] If TOP >= N then write(‘stack overflow’) Exit Step 2: [Increment the TOP pointer] TOP