Linear Data Structures, array, stack, queue

Linear Data Structures, array, stack, queue

• 1.
  STACK
• 2.
  Introduction to Array Anarray is defined as a set of finite number of homogeneous elements or same data items. It means an array can contain one type of data only, either all integer, all float-point number or all character. Simply, declaration of array is as follows: int arr[10] ; Where int specifies the data type or type of elements arrays stores. “arr” 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.
• 3.
  Introduction to Array Theelements of array will always be stored in the consecutive (continues) memory location. The number of elements that can be stored in an array, that is the size of array or its length is given by the following equation: (Upperbound-lowerbound)+1 For the above array it would be (9-0)+1=10,where 0 is the lower bound of array and 9 is the upper bound of array. Array can always be read or written through loop. for(i=0;i<=9;i++) { scanf(“%d”,&arr[i]); printf(“%d”,arr[i]); }
• 4.
  Representation of One DimensionalArray An array with only one row or column is called one-dimensional array. It is finite collection of n number of elements of same type such that: ◦ can be referred by indexing. ◦ The Elements are stored in continuous locations. Syntax: Datatype Array_Name [Size]; Where, Datatype : Type of value it can store (Example: int, char, float) Array_Name: To identify the array. Size : The maximum number of elements that an array can hold.
• 5.
  Initializing One DimensionalArray An array can also be created by specifying the size and assigning array elements at the time of declaration. Syntax for initialization: int arr[10]= {2,4,6,7,5,8}; char word[5]= {‘h’, ‘e’, ‘l’, ‘l’, ‘o’}; Write program to show use of initializers.
• 6.
  Accessing One DimensionalArray Elements Individual element of array can be accessed using the following syntax: array_name[index]; e.g., to assign a value to second location of the array, arr[1]=90; Similarly to read a particular value, scanf(“%d”, &arr[2]); Above statement reads a value from keyboard and assigns it to third location of the array. Write a program to illustrate reading and writing of the array.
• 7.
  Memory Allocation ofArray The elements of linear array are stored in consecutive memory locations. It is shown below: Address of element a[k]=B + w * k
• 8.
  Arrays types Single DimensionArray ◦ Array with one subscript Two Dimension Array ◦ Array with two subscripts (Rows and Column) Multi Dimension Array ◦ Array with Multiple subscripts
• 9.
  Initializing Two DimensionalArray An array can also be created by specifying the size and assigning array elements at the time of declaration. Syntax for initialization: int arr[3][3]= {2,4,6,7,5,8,9,3,1}; Write program to show use of initializers.
• 10.
  Accessing Two DimensionalArray Elements Individual element of array can be accessed using the following syntax: array_name[row_index][col_index]; e.g., to assign a value to first row and first column location of the array, arr[0][0]=9; Similarly to read a particular value, scanf(“%d”, &arr[1][0]); Above statement reads a value from keyboard and assigns it to second row and first column location of the array. Write a program to illustrate reading and writing of the 2-D array.
• 11.
  Basic operations ofArrays Some common operation performed on array are: ◦ Traversing ◦ Searching ◦ Insertion ◦ Deletion ◦ Sorting ◦ Merging
• 12.
  STACK • Common Example: • Suppose at your home you have multiple chairs then you put them together to form a vertical pile. From that vertical pile the chair which is placed last is always removed first. Chair which was placed first is removed last. In this way we can see how stack is related to us.
• 13.
  What is Stack? • Stack is used as Linear data structure which can be accessed from only one end . • Stack is LIFO Structure [ Last in First Out ] • Stack is Ordered List of Elements of Same Type. • Stack is Linear List • In Stack all Operations such as Insertion and Deletion are permitted at only one end called Top
• 14.
  Visual Representation ofStack : • View 1 : When Stack is Empty When Stack is said to empty then it does not contain any element inside it. Whenever the Stack is Empty the position of topmost element is -1.
• 15.
  • View 2: When Stack is Not Empty • Whenever we add very first element then topmost position will be incremented by 1. After adding First Element top = 0.
• 16.
  • View 3: • After Deletion of 1 Element Top Will be Decremented by 1
• 17.
  Array Representation ofStack in C Programming : • 1-D array is used to hold the element of the stack. • Variable “top” keeps track of “Topmost” Element in the stack. • “MAX” is used as Constant which gives maximum size of Stack.
• 19.
  Operations on Stack Representationof Stack in Memory The stack  •PUSH: It adds a new element to the top of the stack. After every push operation top of stack incremented by one. If stack is full no new element can be accommodated, this condition is called stack overflow or stack is full.
• 20.
  PUSH operation onstack
• 21.
  Operations on Stack Representationof Stack in Memory The stack  •POP: I It removes the top element from the stack.): After every pop operation top of stack decremented by one. If stack is empty and pop operation performed this will result into stack underflow condition or stack empty. he stack
• 22.
  POP operation onstack
• 23.
  APPLICATION OF THESTACK 1. Mathematical Expression Evaluation 2. Calculation of Postfix Expression 3. Expression conversion a.Infix to Postfix. b.Infix to Prefix. c.Postfix to Infix. d.Prefix to Infix. 4. Function call and recursion 5. Stack frame 6. Reversing a String