Stack.pptx

Stack Introduction  Most commonly used linear data structure of variable size.  In linear data structure, insertion and deletion of elements takes place at any position  But in Stack , insertion and deletion of elements can occur only at one end known as TOP.  Hence it is known as Restrict...

Stack Introduction  Most commonly used linear data structure of variable size.  In linear data structure, insertion and deletion of elements takes place at any position  But in Stack , insertion and deletion of elements can occur only at one end known as TOP.  Hence it is known as Restricted type data structure.  Stack is also called LIFO (Last In First Out ) list as the last element added to the stack will be removed first from stack.  In stack , Insertion of elements known as “PUSH” while deletion or removal of elements known as “POP”. Operations on Stack PUSH POP 1) PUSH  Refers to insertion of new element in stack.  New element will be inserted on the top of the stack.  PUSH operation can be possible if stack is not filled i.e. it has sufficient space to accommodate new elements.  If stack is filled and if you want to insert new element in stack then condition is known as Overflow. 2) POP  Refers to deletion or removal of element from the top of stack.  We can perform POP operation if stack is not empty.  If stack is empty and want to remove an element from stack then the condition is known as Underflow. PUSH and POP operation PUSH and POP operation Memory representation of stack  Stack can be implemented in two ways 1) Array 2) Linked list  Array representation of stack is acceptable if size of stack is determined before program runs.  The linked list representation of stack is more suitable if size of stack is not estimated in advance. Array representation of stack  It is simplest form of representing Stack.  But it has certain restrictions 1) The stack must contain homogeneous data elements 2) One must specify Upper bound of an array i.e. maximum size of stack must be defined before implementing it.  In this , variable TOP is used to hold the index of stack’s topmost element.  Initially when stack is empty , TOP = 0 , during insertion operation value of Top is incremented by one while during deletion value of Top is decremented by 1.  Another variable Max is used to represent maximum number of elements that can be pushed into stack. Algorithm: PUSH operation Question: Insert a new element ‘ Data ‘ at the top of the stack represented by an Array ‘S’ of size ‘Max’ with stack index variable ‘Top’ pointing to the topmost element of the stack. Solution: Step 1 : If Top = Max , then Print: “ Stack is already full. Overflow Condition” Exit (End If) Step 2: Set Top = Top + 1 Step 3: Set S[Top] = Data Step 4 : Exit Algorithm: POP operation Question:Delete an element from the stack represented by an Array ‘S’ and returns the element ‘Data ‘ which is at the top of stack Solution: Step 1 : If Top = Null , then Print: “ Stack is already empty.Underflow Condition” Exit (End If) Step 2: Set Data = S[Top] Step 3: Set Top = Top – 1 Step 4 : Exit Linked list representation of stack  Stack also can be implemented by using linked list.  It is used to overcome the drawback of array that is maximum size of stack must be known in advance.  Linked list representation of stack allows it to grow without any prior fixed limit.  The PUSH and POP operation can be performed on the linked list implementation of the stack by inserting and deleting an element at the beginning of linked list. Top 2 9 6 5 Null Linked list representation of stack Question: Insert a new element ‘Data’ at the top of the stack represented by the linked list with a stack pointer variable ‘Top’ pointing to the topmost node of the stack. Solution: Step 1: If Free=Null, then Print: “Free node is not available , overflow condition” Exit [End If] Step 2: Allocate memory to a node New from free memory pool Set New Free and Free = Free Next Step 3: Set New Info = Data and New Next = Top Step 4 : Set Top = New Step 5 : Exit Question: Delete an element from the stack represented by the linked list and return the element ‘Data ‘ which is at the top of the stack. Solution: Step 1: If Top = Null , then Print: “ Stack is empty, underflow condition” Exit [End If] Step 2: Set Data = Top Info and Temp = Top Step 3: Set Top = Top Next Step 4: Deallocate the deleted node Temp to free storage list Set Temp Next = Free and Free = Temp Step 5 : Exit Applications of stack 1)Evaluation of Arithmetic Expressions  The important application of stack is the compilation of arithmetic expressions in the programming language.  The stack can be used to convert some infix expression into its postfix equivalent, or prefix equivalent. These postfix or prefix notations are used in computers to express some expressions.  Let us discuss various notations used for expressing arithmetic expressions. 1) Infix Notation  This most common method is used to express arithmetic expressions.  In this notation , operator is placed between operands.  For example , to multiply m and n , we write m x n.  While solving the Infix notation , main consideration is the precedence of the operator and their associativity.  For e.g. answer of (q x r ) + s and q x (r + s) is not going same always.  Let take values as q= 3 , r = 4 & s = 5 and solve above two expressions. Precedence Table of the various operators is given below Priorit Operator Associativity y 1 Brackets (Inner to out , left to right) 2 Exponent Left to right 3 X,/ Left to right 4 +,- Left to right 5 = Right to left Consider the following expressions 1) e = 4 – 2 4 + 8 x 3 + 18 / 3 + 2) e = 5 x 3 + ( 60 – 36 ) / 6 + 6 ( 3 x 10 ) + 7 e = 4 – 16 +24 + 6 + 6 e = 5 x 3 + 24 / 6 + 30 + 7 e= 40 – 16 e = 15 + 4 + 30 + 7 e = 24 e = 56 e = 4 – 16 + 8 x 3 + 18 / 3 + 6 e = 4 – 16 + 24 + 6 + 6 e = 4 – 16 + 36 e = 4 + 20 e = 24 2) Prefix Notation  In prefix notation , operator is placed before operands.  No precedence rule has to follow in this Operation Infix Notation Prefix Postfix notatio notatio n n Multiplication mxn x mn Division m/n / mn Addition m+n + mn Subtraction m–n - mn Exponential n Convert the following Infix expressions into prefix expressions Iin = ( a + b ) / c = [+ ab ] / c = / + abc Ipre = / + abc 3) postfix Notation  In postfix notation , operator is placed after operands.  No precedence rule has to follow in this Operation Infix Notation Postfix notation Multiplication mxn mn x Division m/n mn / Addition m+n mn + Subtraction m–n mn - Exponential n Convert the following Infix expressions into postfix expressions Iin = ( a + b ) / c = [ ab + ] / c = ab +c / Ipost = ab + c / Convert the following infix notations into postfix notations 1) (6+2) x 5 -8/4 2) (12-4) x 53 [12 4 -] Evaluate the following postfix notation P = 6 2 + 5 x 8 4 /- Character Scanned Status of Stack 6 6 2 6 2 + 8 5 8 5 X 40 8 40 8 4 40 8 4 / 40 2 - 38  Evaluate the following postfix notation P = 53+62/ x 35 x + Character Scanned Status of Stack 5 5 3 5 3 + 8 6 8 6 2 8 6 2 / 8 3 x 24 3 24 3 5 24 3 5 X 24 15 + 39  Evaluate the following postfix notation 1) 7 8 + 3 2 + / Character Scanned Status of stack 7 7 8 7 8 + 15 3 15 3 2 15 3 2 + 15 5 / 3 2) Recursion  The process in which a function calls itself directly or indirectly is called recursion and the corresponding function is called as recursive function.  Using recursive algorithm, certain problems can be solved quite easily.  Examples of some recursively solved problems are 1. Calculating sum of n terms. 2. Calculating the factorial of positive integer 3. Fibonacci series  Recursion is generally used for repetitive computations in which each action is defined in terms of previous result 1) Factorial Function  The factorial of positive number n is the product of positive integers from 1 to n.  The factorial of number is represented by writing “!” Sign after it.  n!= 1 x 2 x 3 x …………x (n-1) x n  Let us calculate factorial of some integers  3! = 3x2x1 = 6 3!= 3 x 2!  4! = 4x3x2x1 = 24 4! = 4 x 3!  5! =  6! =  0! = 1 Formal definition of factorial function is given by n! = 1 if n = 0 Question: Write down an algorithm for calculating the value of n! recursively. Solution: Factorial(n) If n = 0 , then Set Fact = 1 Return Else If n ≠ 0 , then Set Fact = n x Factorial (n -1) Return [End If] Let us calculate the value of 4! By recursive method Solution: Step 1 : 4! = 4 x 3! Step 2: 3! = 3 x 2! Step 3: 2! = 2 x 1! Step 4: 1! = 1 x 0! Step 5: 0! = 1 Step 6: 1! = 1 Step 7: 2!= 2 Step 8: 3! = 6 Step 9: 4! = 24 Let us calculate the value of 5! By recursive method Solution: Step 1 : 5! = 5 x 4! Step 2: 4! = 4 x 3! Step 3: 3! = 3 x 2! Step 4: 2! = 2 x 1! Step 5: 1! = 1 x 0! Step 6: 0!= 1 Step 7: 1!= 1 Step 8: 2! = 2 Step 9: 3!=6 Step 10: 4! = 24 Step 11: 5! = 120 2) Fibonacci Series  It is a sequence of numbers which is denoted by F0, F1……Fn.  Fibonacci series is given by  F = 0 , 1 , 1 , 2, 3, 5,8,13 , 21, 34 ……….  Here F0= 0 , F1 = 1 , F2 = 1 = F0 + F1 , F3 = 2 = F1 + F2 , F4= F2 + F3 Fibo ( n ) = n if n = 0 or 1 fibo (n-1) + fibo (n-2) if n >1 F= 0 ,1 , 1 , 2 , 3 , 5 , 8 , 13 , 21 , 34 , 55 ……………………. Question: Write down an algorithm for finding the value of nth term of Fibonacci series by recursively. Fibonacci(n) Else If n = 0 , then Set Fibo = Fibonacci ( n-1) + Set Fibo = 0 Fibonacci (n-2) Return Return Else [End If] If n = 1 , then Set Fibo = 1 Return