Stack Data Structure PDF

Unit 1: Stack Structure 1.0 Introduction 1.1 Objectives 1.2 Stack 1.3 Array Representation of Stack 1.4 Operations on stack 1.5 Evaluation of Arithmetic expression (infix, postfix and prefix notions) using stack 1.6 Applications of Stack 1.7 Summary 1.0 Introduction Thi...

Unit 1: Stack Structure 1.0 Introduction 1.1 Objectives 1.2 Stack 1.3 Array Representation of Stack 1.4 Operations on stack 1.5 Evaluation of Arithmetic expression (infix, postfix and prefix notions) using stack 1.6 Applications of Stack 1.7 Summary 1.0 Introduction This unit is introducing the concept of another linear data structure i.e. Stack. It provides the definition of stack, its representation in memory, implementation procedure and different common and important operations those can perform on the elements of stack. This unit also includes the method for evaluation of arithmetic expressions using stack. In the end it highlights about the multiple stack concept and the different applications of the stack. 1.1 Objectives After going through this unit, you should be able to:  Understand for the concept of stack  Implementation of the stack using array.  Implementation for the various operations on stack (Push, Pop).  Understanding for the method of evaluation of arithmetic expressions using stack (infix, prefix and postfix representation).  Understanding the concept of multiple stacks and its application. 1.2 Stack A stack is a linear data structure where all the elements in the stack can insert and delete from one side only rather than at the middle or from both the side. Thus, from the stack the elements may be added or removed only from one side. The following figure shows the three everyday common use examples of such structure i.e. a stack of dishes, a stack of coins and a stack of folded towels. As the items in this type of data structure can be added or removed from the top, it means the last item to be added to the stack is the first item to be removed. Therefore stacks are also called Last –in-First-out lists. Thus, the stack follows the principle of Last-in-First-out (LIFO) or First-in- Last-Out (FILO) type working system. Thus, the element which is inserted first in the stack will remove or delete last from the stack. The other names used for the stacks are “piles” and “push- down list”. Therefore we can understand that a stack is a list of elements in which an element may be inserted or deleted only at the end, called the Top of the stack. A stack of elements of any particular type is a finite sequence of elements of that together with the following operations:  Initialize the stack to be empty.  Determine whether stack is empty or not.  Determine if stack is full or not.  If stack is not full, then add or insert a new node at the Top. This operation is called push.  If the stack is not empty, then retrieve the node at its Top.  If the stack is not empty, then delete the node at its Top. This is called pop. The above definition of stack produces the concept of stack as an abstract data type. 1.3 Array Representation of Stack Generally a stack may be represented with a linear array or one way list. In the stack, a pointer variable TOP contains the location of the top element of the stack. The variable N provides the maximum number of elements that can be stored or held in the stack or size of the linear array. Sometimes it is also called as the size of the Stack. The condition where TOP is NULL, indicate that the stack is empty and when the TOP is N, the stack is full. The following figure shows the array representation of a stack. The TOP is pointing to 3 which says that stack has three items and as the N = 6, there is still space for accommodating four items. ITEM 1 ITEM 2 ITEM 3 0 1 2 3 4 5 6 Top N Array Representation of a Stack Example: Suppose the following elements are inserted in order in an empty stack of size 7: AA, BB, CC, DD, EE, FF This stack can represent in following ways using a linear array: 0 1 2 3 4 5 6 AA BB CC DD EE FF TOP  6 5 FF TOP 4 EE 3 DD 2 CC 1 BB 0 AA 1.4 Operation on Stack The operation to add an element into the stack (push) and the operation to remove an element from the stack (pop) can be implemented using the PUSH and POP functions. When we add a new element into the stack, first we check that whether there is a free space in the stack for the new element or not. If there is no free space available for the new element then we have the condition of overflow. In the same way for the function POP we must first check the condition that whether there is an element in the stack to be deleted or not. If there is no element in the stack to delete then we have the condition of underflow. These functions are defined as follows: Function PUSH (STACK, TOP, N, ITEM) [This function adds or pushes an ITEM in the stack] If (TOP == N) Printf (“stack is overflow”); exit; Else { TOP = TOP+1; STACK [TOP] = ITEM; } RETURN Function POP (STACK, TOP, ITEM) [This function deletes or pops the TOP element of STACK and assigns it to the variable ITEM]  If (TOP == -1) Printf (“stack is underflow”); exit; Else { ITEM = STACK [TOP]; TOP = TOP – 1; } /* Decrease TOP by 1] RETURN We can see from the above defined functions that the value of TOP is changed before adding the element in the stack in function PUSH but the value of TOP is changed after removing the element from stack in function POP. Example: Consider the following stack with size of 9. XX YY ZZ 0 1 2 3 4 5 6 7 8 TOP N If we perform the operation PUSH (STACK, WW); then the status of the stack can determine as: Since TOP = 2, so TOP = 2 + 1 = 3. And STACK [ TOP ] = STACK = WW. Therefore the item WW is now top element of the stack. This can represent as: XX YY ZZ WW 0 1 2 3 4 5 6 7 8 TOP N Now, on the same stack we perform the operations POP (STACK, ITEM); POP (STACK, ITEM); then the status of the stack can determine as:  Right now the TOP = 3 and the operation POP is performed two times. So, after the execution of first POP operation: ITEM = WW and TOP = 3-1 = 2 Now after the execution of second POP operation: ITEM = ZZ and TOP = 2-1 = 1 Therefore STACK [TOP] = STACK = YY is now the top element in the stack. XX YY 0 1 2 3 4 5 6 7 8 TOP N 1.5 Evaluation of Arithmetic expression (infix, postfix and prefix notions) using stack This is well known that the computer system can understand and work only on binary paradigm. In which an arithmetic operation can take place between two operands only like A + B, C * D, D / A. generally an arithmetic expression may consist of more than one operator and two operands, for example (A + B) * (D / (J + D)). Such form of the arithmetic expression is commonly known as the infix expression. Normally the evaluation of the any arithmetic expression does not take place in its infix form. Here we are introducing the method for evaluating the infix expression form computation point of view. The stack is found to be more efficient to evaluate an infix arithmetical expression by first converting to a prefix or postfix expression and then evaluating these converted expressions. This approach will eliminate the repeated scanning of an infix expression in order to obtain its value. Therefore there are three basic notations are referred for the representation of any complex arithmetic expression. These forms are as follows:  If the operator symbols are placed before its operands, then the expression is in prefix form.  If the operator symbols are placed after its operands, then the expression is in postfix form.   If the operator symbols are placed between the operands then the expression is in infix form. Hence, a normal arithmetic expression is normally called as infix expression i.e. A+B. A Polish mathematician found a way to represent the same expression called polish notation or prefix expression by keeping operators as prefix i.e. +AB. We use the reverse way of the above expression for our evaluation. The representation is called Reverse Polish Notation (RPN) or postfix expression i.e. AB+. Let Q be an infix arithmetic expression involving constants and operations. This expression will be evaluated with the common rule of arithmetic evaluation with the following level of operator precedence: Highest: Exponentiation (  ) Next highest: Multiplication (*) and division (/) Lowest: Addition (+) and Subtraction (-) Now let we evaluate the following parenthesis free arithmetic expression: 2  3  5 * 2  2  12 / 6 First we evaluate the exponentiations to obtain: 8 + 5 * 4 – 12 / 6 Then we evaluate the multiplication and division to obtain 8 + 20 – 2. Last, we evaluate the addition and subtraction to obtain the final result i.e. 26. We can observe that in this evaluation the whole expression is traversed three times, each time corresponding to a level of precedence of the operations. Second important issue about the infix notation is that these expressions use parentheses for clarity and to make the evaluation convenient like (A + (B – C)) * D) / E. On the other hand the polish notation expression i.e. prefix and reverse polish notation expression i.e. postfix do not include any parentheses for clarity. Now we consider for example the step by step translation of following infix expression into polish notation using square brackets i.e. [ ] to indicate a partial translation:  ( A  B ) * C  [  AB ] * C  *  ABC A  ( B * C )  A  [* BC ]   A * BC ( A  B ) /( C  D )  [  AB ] /[  CD ]  /  AB  CD The fundamental property of Polish notation is that the order in which the operations are to be performed is completely determined by the positions of the operators and operands in the expression. There is no need of parentheses when writing expressions in Polish notation. The computer usually evaluates an arithmetic expression written in infix notation in following two steps.  Coverts the expression in Reverse Polish notation form (post fix notation).  Evaluate the post fix expression using stack. Algorithm for transforming Infix Expression into Postfix Expression Let Q be an arithmetic expression written in infix notation. The following algorithm transforms the given infix expression Q into its equivalent postfix expression P. This algorithm uses a stack to temporarily hold operators and left parentheses. The postfix expression P will be constructed from left to right using the operands from Q and the operators which are removed from STACK. We begin by pushing a left parenthesis onto STACK and adding a right parenthesis at the end of Q. The algorithm is completed when STACK is empty: Algorithm: Conv_POLISH (Q, P) [Suppose Q is an arithmetic expression written in infix notation. The algorithm finds the equivalent postfix expression P] 1. Push “(“onto STACK, and add “)” to the end of Q. 2. Scan Q from left to right and repeat step3 to 6 for each element of Q until the STACK is empty. 3. If an operand is encountered, add it to P. 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 P 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 P each operator (on top of STACK) until a left parenthesis is encountered. b. Remove the left parenthesis. [Do not add the left parenthesis to P.]  [End of if] [End of step 2 loop] 7. Exit. Example: Consider the following arithmetic infix expression: Q: A + ( B * C - ( D / E  F ) * G ) * H ) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 The elements of Q have now been labeled from left to right for easy reference. Following table shows the status of STACK and of the Postfix string P as each element of Q is scanned to follow the following steps of algorithm. 1. Each element is simply added to P and does not change STACK from A to C; operators +. (, * are pushed to stack and A, B, C are added to P. 2. The subtraction operator (- in row 7 sends * from STACK to P before it (-) is pushed onto the STACK. 3. The right parenthesis in row 14 sends  and then / from STACK to P and then removes the left parenthesis from the STACK. 4. The right parenthesis in row 20 sends * then + from STACK to P and then removes the left parenthesis from the top of STACK. After step 20 is executed, the stack is empty. Symbol Scanned STACK Expression P (1) A ( A (2) + (+ A (3) ( (+( A (4) B (+( AB (5) * (+(* AB  (6) C (+(* ABC (7) - (+(- ABC* (8) ( (+(-( ABC* (9) D (+(-( ABC*D (10) / (+(-(/ ABC*D (11) E (+(-(/ ABC*DE (12)  (+(-(/  ABC*DE (13) F (+(-(/  ABC*DEF (14) ) (+(- ABC*DEF  / (15) * (+(-* ABC*DEF  / (16) G (+(-* ABC*DEF  /G (17) ) (+ ABC*DEF  /G*- (18) * (+* ABC*DEF  G*- (19) H (+* ABC*DEF  G*-H (20) ) ABC*DEF  G*-H*+ Evaluation of Post Fix Expression As we know that in the infix expression it is difficult for the computer to keep track of precedence of operators. On the other hand, a postfix expression itself determines the precedence of operators due to the placement of the operator. Hence it is easier for the computer to perform the evaluation of a postfix expression. The evaluation rule for the postfix expression is stated as: 1. Read the expression from left to right. 2. If it is an operand then push the element into the stack.  3. If the element is an operator except NOT operator, pop the two operands from the stack and evaluate them with the read operator and push back the result of the evaluation into the stack. 4. If it is the NOT operator then pop one operand from the stack and then evaluate it and push back the result of the evaluation into the stack. 5. Repeat it till the end of stack. Now we define the algorithm for evaluation of postfix expression using STACK. Let P be a arithmetic expression written in postfix notation. The following algorithm uses the STACK to hold the operands and evaluate expression P. [This algorithm finds VALUE of an arithmetic expression P written in postfix notation.] 1. Add a right parenthesis “)” at the end of P. 2. Scan P from left to right and repeat step 3 and 4 for each element until “)” is not encountered. 3. If an operand is encountered , put it on STACK 4. If an operator is encountered then: a. Remove the two top elements of STACK, where A is the top element and B is the next –to-top element. b. Evaluate B and A for the encountered operator. c. Place the result of evaluation on step b back on STACK [End of if] [End of step 2 loop]. 5. Set VALUE equal to the top element on STACK. 6. Exit. Example Evaluate the following arithmetic expression Q written in infix notation: Q: 10 * (8 + 4) – 6 / 3 The equivalent postfix notation for the given infix notation is: P: 10, 8, 4, +, *, 6, 3, /, - [Here Commas are used to separate the elements of P ] Now we apply the algorithm to evaluate the postfix notation: First we add „)‟ at the end of right side in expression P. P: 10, 8, 4, +, *, 6, 3, /, -, )  (1) (2) (3) (4) (5) (6) (7) (8) (9) (10) The evaluation procedure with contents of STACK can consider from the following table: Symbol Scanned Stack (1) 10 10 (2) 8 10, 8 (3) 4 10, 8, 4 (4) + 10, 12 (5) * 120 (6) 6 120, 6 (7) 3 120, 6, 3 (8) / 120,2 (9) – 118 (10) ) The final number in STACK is 118, which will assign to the VALUE when „)‟ encounters. Thus the evaluation of postfix notation P is 118. Algorithm to convert infix into prefix expression form Suppose Q is an arithmetic expression written in infix form. The following steps find its equivalent prefix expression P. 1. Push „)‟ onto STACK and add „(„to the begin of Q. 2. Scan Q from right to left and repeat steps 3 to 6 for each element of P until the STACK is empty. 3. If an operand is encountered add it to P. 4. If a right parenthesis is encountered, push it onto stack. 5. If an operator is encountered then: a. Repeatedly pop from STACK and add to P each operator (on the top of STACK) which has same or higher precedence than the operator. b. Add operator to STACK. 6. If a left parenthesis is encountered then a. Repeatedly pop from the STACK and add to P until a right parenthesis is encountered. b. Remove the Right parenthesis 7. Exit Example: Convert the following given infix expression in its equivalent prefix notation form. Q: (A + B * C – D + E / (F + G)) The procedure for converting the given infix expression into its equivalent prefix notation form by applying the algorithm can represent in following table: Symbol Scanned Stack Prefix expression ) ) )) G )) G + )) + G F ))+ FG ( Empty +FG / )/ +FG E )/ E+FG + )+ / E+FG D )+ D/E+FG - )+- D/E+FG C )+- CD/E+FG * )+-* CD/E+FG B )+-* BCD/E+FG + )+-+ *BCD/E+FG A )+-+ A*BCD/E+FG ( Empty +-+A*BCD/E+FG Hence the resultant equivalent prefix notation for the given infix notation is: P: +, -, *, +, A, B, C, D, / E + F G Algorithm for evaluation of Prefix Expression [This algorithm performs the evaluation for the infix notation expression. Here the expression will read from right to left] 1. Read the next element. 2. If element is operand then  a. Push the element in the stack 3. If element is operator then a. Pop two operands from the stack b. Evaluate the expression formed by two operands and the operator c. Push the results of the expression in the stack 4. If no more elements then a. Pop the result Else Go to step 1. Example: Evaluate the following prefix notation expression. P: +2*3+4 5 Now we start to read it from right to left: +2 * 3 + 45 Symbol Scanned Stack 5 5 (push) 4 4, 5 (push) + 9 (pop, push) 3 3, 9 (push) * 27 (pop, push) 2 2, 27 (push) + 29 (pop, push) The final number in STACK is 29. Thus the evaluation of prefix notation P is 29. 1.6 Application of Stacks The stack has various applications in computer science. It includes the application of the level of computer organization and programming level. Generally being a linear data structure the following applications of stacks are highlighted:   The stack is used for reversal of a given list. We can accomplish this task by pushing each element onto the stack as it is read. When the line is finished, elements are then popped off the stack, so they come off in reverse order.  The important application of the stack in computer organization is for the evaluation of arithmetic expressions. It accomplishes by converting first the given expression in reverse polish notation and then evaluates the expression.  It is also used for the zero address instruction implementation in computer organization.  Stacks are used for the address holding in function calling procedure of programming.  The stacks are used to implement recursive procedures. Recursion is useful in developing algorithm for specific problems. Suppose a function contains either a call statement to itself or a call statement to a second function that may eventually result in a call statement back to the original function. Then such a function is called recursive function. The stacks are used generally for the implementation of such type of recursive functions. 1.7 Summary In this unit we presented another important linear data structure i.e. Stack. A stack is a linear data structure where all the elements in the stack can insert and delete from one side only rather than at the middle or from both the side. We have explored the implementation of stack in static manner using array. The two basic operations of PUSH and POP are discussed with example for the stack. The contents can be summarized as follows:  A stack is a linear structure implemented in LIFO (Last In First Out) manner where insertions and deletions take place at the same end.  An insertion is a stack is called pushing and deletion from a stack is called popping.  When a stack implemented as an array, is full and no new element can be accommodated, it is called OVERFLOW.  When a stack is empty and an attempt is made to delete an element from the stack, it is called UNDERFLOW.  The main application of stack can be implementation of Polish notation which refers to a notation in which operator symbol is placed either before its operands (prefix notation) or  after its operands (postfix notation). The usual form, in which operator is placed in between the operands, is called infix notation.  The other application of stack can be reversing a list and providing recursion in various programs.  It is also used for the zero address instruction implementation in computer organization.  Stacks are used for the address holding in function calling procedure of programming. Bibliography  Horowitz, E., S. Sahni: “Fundamental of computer Algorithms”, Computer Science Press, 1978  J. P. Tremblay, P. G. Sorenson “An Introduction to Data Structures with Applications”, Tata McGraw-Hill, 1984  M. Allen Weiss: “Data structures and Problem solving using C++”, Pearson Addison Wesley, 2003  Ulrich Klehmet: “Introduction to Data Structures and Algorithms”, URL: http://www7. Informatik.uni-erlangen.de/~klehmet/teaching/SoSem/dsa  Markus Blaner: “Introduction to Algorithms and Data Structures”, Saarland University, 2011  M. E. D‟imperio, “Data structures and their representation in storage”, Annual Review in Automatic programming, Vol. 5 pp. 1-75, Pergammon Press, Oxford, 1969.  B. Flaming, “Practical Data Strcture in C++”, Jhon Wiley & Sons, New York, 1983  D. E. Knuth, “The art of Computer programming”, Vol. 2: Seminumerical Algorithms, 3rd edition, Addison-Wesley, 1997.  Self Evaluation Multiple Choice Questions: 1......................... form of access is used to add and remove nodes from a stack (a) LIFO (b) FIFO (c) Both (a) and (b) (d) None of these 2. A data structure in which elements are added and removed only at one end is know as: (a) Queue (b) Stack (c) Array (d) None of these 3. Underflow is a condition where you: (a) Insert a new node when there is no free space for it (b) Delete a non-existent node in the list (c) Delete a node from the empty list (d) None of the above 4. Stack is: (a) Static data structure (b) Dynamic data structure (c) A built in data structure (d) None of these 5. Which operation in the stack is used for getting value of most recent node and delete the node: (a) PUSH (b) POP (c) Empty (d) None of these 6. If A, B, C are inserted into a stack in the lexicographic order, the order of removal will be: (a) A, B, C (b) C, B, A (c) B, C, A (d) None of these. Fill in the blank: 1. A stack may be represented by a …………… linked list. (linear / non-linear) 2. Push operation in stack may result in……………… (overflow / underflow) 3. If TOP points to the top of stack, then TOP is……. (increased / decreased) State whether True or False 1. Push operation in stack is performed at the rear end. 2. PUSH operation in stack may result in underflow 3. For a stack implemented with linear array arbitrary amount of memory can be allocated. Descriptive Questions 1. Consider the following stack, where STACK is allocated N = 6 memory cells. STACK: AA, DD, EE, FF, GG………………….. Describe the stack as the following operations take place and also consider the overflow condition. a. PUSH (STACK, KK) b. POP (STACK, ITEM) c. PUSH (STACK, LL) d. PUSH (STACK, SS) e. POP (STACK, ITEM) f. PUSH (STACK, TT) 2. Write an algorithm which upon user‟s choice, either pushes or Pops an element from the stack implemented as an array (the element should not shifted after the push or pop). 3. Write a program to convert an infix arithmetic expression into a prefix arithmetic expression. The algorithm for your program should use the following expression: Q: (A – B) * (C / D) + E Show in tabular form the changing status of stack. 4. Convert the expression (A + B) / (C – D) into postfix expression and then evaluate it for A = 10, B = 20, C = 15, D = 5. Display the stack status after each operation. 5. Write a program to read a string (one line of characters) and push any vowels in the string to a stack. Then pop your stack repeatedly and count the number of vowels in the string.