DSA Chap 3.pptxDSA Chap 3.pptxDSA Chap 3.pptx

DSA Chap 3.pptxDSA Chap 3.pptxDSA Chap 3.pptxDSA Chap 3.pptxDSA Chap 3.pptxDSA Chap 3.pptxDSA Chap 3.pptxDSA Chap 3.pptxDSA Chap 3.pptxDSA Chap 3.pptxDSA Chap 3.pptxDSA Chap 3.pptxDSA Chap 3.pptxDSA Chap 3.pptxDSA Chap 3.pptx

1. Welcome

2. Puntland State University Faculty of Computing

3. http://www.mahergelle.com By Eng.Adulahi M. Adan Data Structure and Algorithm

4. Chapter Three: - Stack

5. Lesson Objectives Stack: what is it? 01 Implementation of stack 03 Applications of stack 04 Basic operations of stack 02

6. Stack Stack is A data structure in which insertion and deletion occur at the same end ( TOP ) is called a stack . It is a LIFO (Last In First Out) structure. The operations of insertion and deletion are called PUSH and POP . Push - push (put) item onto stack Pop - pop (get) item from stack Data Structure and Algorithm

7. … A stack of coins 7 7

8. Stack Data Structure and Algorithm push() push() pop() pop() Remove ‘A’ Remove ‘B’ Insert ‘B’ in the stack Insert ‘A’ in the stack Definition Stack is a “ Last in First Out ” data structure, which means elements inserted are popped in the reversed order Insert ‘A’ Insert ‘B’ Remove ‘B’ Remove ‘A’

9. Stack Data Structure and Algorithm D A B C A A A B B C top top top top A B C top D

10. Stack a Data Structure and Algorithm

11. Stack A stack is a homogeneous collection of elements in which an element may be inserted or deleted only at one end, called the top of the stack. Stack is a collection of similar data items in which both insertion and deletion operations are performed based on LIFO principle”. Data Structure and Algorithm

12. Stack Usage Both hardware and software stacks have been used to support four major computing areas in computing requirements: function calls expression evaluation subroutine return address storage(always called subtask) dynamically allocated local variable storage subroutine parameter passing. Data Structure and Algorithm

13. ARRAY REPRESENTATION OF STACKS In the computer’s memory, stacks can be represented as a linear array. Every stack has a variable called TOP associated with it, which is used to store the address of the topmost element of the stack. It is this position where the element will be added to or deleted from. There is another variable called MAX , which is used to store the maximum number of elements that the stack can hold. Data Structure and Algorithm

14. Operations on a Stack

15. Operations on a Stack These are the basic operations that can be performed on a stack. Assume Maximum size of n. Push : This operation adds or pushes another item onto the stack. The number of items on the stack is less than n. Pop : This operation removes an item from the stack. The number of items on the stack must be greater than . Top : This operation returns the value of the item at the top of the stack. Note : It does not remove that item. Is Empty : This operation returns true if the stack is empty and false if it is not. Is Full : This operation returns true if the stack is full and false if it is not. Data Structure and Algorithm

16. Push Operation The push operation is used to insert an element into the stack. The new element is added at the top most position of the stack. However, before inserting the value, we must first check if TOP=MAX–1 , because if that is the case, then the stack is full and no more insertions can be done. If an attempt is made to insert a value in a stack that is already full, an OVERFLOW message is printed Data Structure and Algorithm

17. Push Operation To insert an element with value 6, we first check if TOP=MAX–1 . If the condition is false, then we increment the value of TOP and store the new element at the position given by stack[TOP]. Thus, the updated stack becomes as shown in Fig. 7.6. Data Structure and Algorithm

18. Pushing Data Structure and Algorithm If ITEM=80 is to be inserted, then TOP=TOP+1=4 STACK[TOP]:= STACK[4]:= ITEM=80 N=5 MAXSTACK=10 top = 3 N = 4 17 23 97 44 0 1 2 3 4 5 6 7 8 9 STACK 0 1 2 3 4 5 6 7 8 9 top = 4 N = 5 17 23 97 44 STACK 80

19. Push Operation 1.push(): When an element is added to a stack, the operation is performed by push(). Below Figure shows the creation of a stack and addition of elements using push(). Data Structure and Algorithm

20. Push Operation Algorithm: Procedure for push(): Step 1: START Step 2: if top>=size-1 then Write “ Stack is Overflow” Step 3: Otherwise 3.1: read data value ‘x’ 3.2: top=top+1; 3.3: stack[top]=x; Step 4: END Data Structure and Algorithm

21. Push Operation void push() { int x; if(top >= n-1) { c out <<"Stack Overflow.."; return; } else { c out <<"Enter data: "; cin << x; stack[top] = x; top = top + 1; c out <<"Data Pushed into the stack"; } } Data Structure and Algorithm

22. Pop Operation The pop operation is used to delete the topmost element from the stack. However , before deleting the value, we must first check if TOP=NULL because if that is the case, then it means the stack is empty and no more deletions can be done. If an attempt is made to delete a value from a stack that is already empty, an UNDERFLOW message is printed. Data Structure and Algorithm

23. Pop Operation Data Structure and Algorithm If ITEM=80 is to be deleted, then ITEM:=STACK[TOP]= STACK[4]= 80 TOP=TOP-1=3 N=4 MAXSTACK=10 top = 3 N = 4 17 23 97 44 0 1 2 3 4 5 6 7 8 9 STACK 0 1 2 3 4 5 6 7 8 9 top = 4 N = 5 17 23 97 44 STACK 80

24. Pop Operation 2.Pop(): When an element is taken off from the stack, the operation is performed by pop(). Below figure shows a stack initially with three elements and shows the deletion of elements using pop(). Data Structure and Algorithm

25. Pop Operation Algorithm: procedure pop(): Step 1: START Step 2: if top==-1 then Write “ Stack is Underflow ” Step 3: otherwise 3.1: print “deleted element” 3.2: top=top-1; Step 4: END Data Structure and Algorithm

26. Pop Operation Void pop() { If(top==-1) { cout <<“Stack is Underflow”; } else { cout <<“Delete data ”,stack[top]; top=top-1; } } Data Structure and Algorithm

27. Application Areas of Stack

28. Application Areas of Stack Some stack applications include: Evaluating Postfix expression Convert infix expression to postfix Convert infix expression to Prefix Function call ( creates new instance of return addresses for each call to a function) To reverse a word. You push a given word to stack - letter by letter - and then pop letters from the stack. Data Structure and Algorithm

29. Application Areas of Stack An "undo" mechanism in text editors; this operation is accomplished by keeping all text changes in a stack Backtracking (game playing, finding paths, exhaustive searching ) Memory management, run-time environment for nested language features Parsing Recursive Function Data Structure and Algorithm

30. Evaluation of Algebraic Expressions Humans usually write algebraic expressions like this: a + b This is called infix notation, because the operator (“+”) is inside the expression A problem is that we need parentheses or precedence rules to handle more complicated expressions: a + b * c = (a + b) * c ? = a + (b * c) ? 2 + 3 * 4 4 / 2 * 6 Data Structure and Algorithm

31. Infix, postfix, and prefix notation There is no reason we can’t place the operator somewhere else. infix notation: a + b prefix notation: + a b postfix notation: a b + Data Structure and Algorithm Prefix notation was introduced by the Polish logician Lukasiewicz , and is sometimes called “ Polish notation” Postfix notation is sometimes called “reverse Polish notation” or RPN

32. Infix, postfix, and prefix notation Question: Why would anyone ever want to use anything so “unnatural,” when infix seems to work just fine? Answer: With postfix and prefix notations, parentheses are no longer needed! infix postfix prefix (a + b) * c a b + c * * + a b c a + (b * c) a b c * + + a * b c Data Structure and Algorithm

33. The valuable aspect of postfix Parentheses are unnecessary Easy for a computer (compiler) to evaluate an arithmetic expression Postfix (Reverse Polish Notation) Fairly simple algorithm exists to evaluate such expressions based on using a stack Data Structure and Algorithm Binary operators : + , - , * , / , etc.,   Unary operators : unary minus , square root , sin , cos , exp , etc.,  

34. Postfix Evaluation Postfix notation In postfix notation, the operator comes after its operands. Postfix notation is also known as reverse Polish notation (RPN) and is commonly used because it enables easy evaluation of expressions. Syntax : operand1 operand2 operator Example : AB+C*DEF+/- Data Structure and Algorithm

35. Postfix Evaluation Example 7.1: Convert the following infix expressions into postfix expressions Solution (a) (A–B) * (C+D) [AB–] * [CD+] AB–CD+* (b) (A + B) / (C + D) – (D * E) [AB+] / [CD+] – [DE*] [AB+CD+/] – [DE*] AB+CD+/DE*– Data Structure and Algorithm

36. Postfix Evaluation Using Stack   Consider the postfix expression : 6 5 2 3 + 8 * + 3 + * Data Structure and Algorithm So for evaluating 6 5 2 3 + 8 * + 3 + * the first item is a value (6) so it is pushed onto the stack the next item is a value (5) so it is pushed onto the stack the next item is a value (2) so it is pushed onto the stack the next item is a value (3) so it is pushed onto the stack and the stack becomes

37. Postfix Evaluation Using Stack Data Structure and Algorithm the remaining items are now: + 8 * + 3 + * So next a '+' is read (a binary operator), so 3 and 2 are popped from the stack and their sum '5' is pushed onto the stack:

38. Postfix Evaluation Using Stack Data Structure and Algorithm Next 8 is pushed and the next item is the operator * :

39. Postfix Evaluation Using Stack Data Structure and Algorithm Next the operator + followed by 3 :

40. Postfix Evaluation Using Stack Data Structure and Algorithm Next is operator + , so 3 and 45 are popped and 45+3= 48 is pushed Next is operator * , so 48 and 6 are popped , and 6*48= 288 is pushed

41. Class Activity Evaluate the postfix expression 7 8 + 3 2 + / Data Structure and Algorithm

42. Answer Data Structure and Algorithm

43. Converting Infix to Postfix (RPN) conversion The rules to be remembered during infix to postfix conversion are: 1. Parenthesize the expression starting from left to right. 2. During parenthesizing the expression, the operands associated with operator having higher precedence are first parenthesized. For e xample in the above expression B * C is parenthesized first before A + B. 3. The sub-expression (part of expression), which has been converted into postfix, is to be treated as single operand. 4. Once the expression is converted to postfix form, remove the parenthesis. Data Structure and Algorithm

44. Converting Infix to Postfix (RPN) conversion Converting from infix notation to postfix notation Assume that your infix expression is of the form < identifier> <operator> <identifier> A postfix expression is created by rewriting this as < identifier> <identifier> <operator> Data Structure and Algorithm

45. Converting Infix to Postfix (RPN) conversion Scan the infix expression  from left to right .  If the scanned character is an operand , put it in the postfix exp Otherwise, do the following If the precedence of the current scanned operator is higher than the precedence of the operator on top of the stack, or if the stack is empty, or if the stack contains a ‘(‘, then push the current operator onto the stack. Else, pop all operators from the stack that have precedence higher than or equal to that of the current operator. After that push the current operator onto the stack. If the scanned character is a ‘ ( ‘, push it to the stack.  If the scanned character is a ‘ ) ’, pop the stack and output it until a ‘ ( ‘ is encountered, and discard both the parenthesis.  Repeat steps  2-5  until the infix expression is scanned.  Data Structure and Algorithm

46. Stack Data Structure and Algorithm

47. Stack What is the postfix form of the following expression? 1. A + ( (B + C) + (D + E) * F ) / G ? ABC + DE + F * + G / + 2. (A + B) * C - (D - E) * (F + G)? AB + C * DE - FG + * - Note: Postfix notation is of little use unless there is an easy method to convert standard (infix) expressions to postfix. Again a simple algorithm exists that uses a stack. Data Structure and Algorithm

48. Converting Infix to Postfix (RPN) conversion Consider the following arithmetic infix expression P P = A + (B / C - (D * E ^ F ) + G ) * H Data Structure and Algorithm

49. Stack

50. Converting Infix to Postfix (RPN) conversion How does the above algorithm convert the following arithmetic infix expression P = A * B + C * D in to postfix expression? Data Structure and Algorithm

51. Converting Infix to Postfix (RPN) conversion a Data Structure and Algorithm

52. Exercise: Convert the following infix expressions to their postfix equivalents : (a) A – B + C (b) A * B + C / D (b) (A – B ) + C * D / E – C (c) (A * B) + (C / D) – ( D + E ) Data Structure and Algorithm

53. Prefix Polish Notation (prefix ) : Polish notation, also known as prefix notation, is a form of notation for logic, arithmetic, and algebra . Its distinguishing feature is that it places operators to the left of their operands. Lacking parentheses or other brackets. Syntax : operator operand1 operand2 Example : -*+ABC/D+EF Data Structure and Algorithm

54. Prefix Example 7.2 Convert the following infix expressions into prefix expressions Solution (a) (A + B) * C (+AB)*C *+ABC (b) (A–B) * (C+D) [–AB] * [+CD] *–AB+CD (c) (A + B) / ( C + D) – ( D * E) [+AB] / [+CD] – [*DE] [/+AB+CD] – [*DE] –/+AB+CD*DE Data Structure and Algorithm

55. Chapter End

56. Thank you @ Eng.Abdulahi Mohamed