Stacks and queues using aaray line .pptx

about impl of stack using array

1. DS Module 2 Stacks and Queues

2. Module 2 : Stack and Queues Refer Module 2 of Syllabus [CSC303 (SE AI&DS/ SE Comps)] 2.1 Introduction, ADT of Stack, Operations on Stack, Array Implementation of Stack, Applications of Stack-Well form-ness of Parenthesis, Infix to Postfix Conversion and Postfix Evaluation, Recursion. 2.2 Introduction, ADT of Queue, Operations on Queue, Array Implementation of Queue, Types of Queue-Circular Queue, Priority Queue, Introduction of Double Ended Queue, Applications of Queue.

3. Stack Definition - A stack is an ordered collection of homogeneous data elements, where the insertion and deletion takes place at one end, known as TOP. The stack is also called LAST IN FIRST OUT(LIFO) It means: the element which is inserted last must be deleted first Example pile of plates in cafeteria Chapati stack in round box stack of coins

4. Stack maintains a pointer called top, which keeps track of the top most element in the stack. Any insertions or deletions should be based upon the value of top. It works on the basis of LIFO (Last in First out). According to the definition, new elements are inserted from top and the elements are deleted from same end i.e again top. This suggests that the element inserted most recently can only be deleted. In the stack, the elements are removed in the reverse order of that in which they were added to the stack i.e last element inserted is to be deleted first. So it is called last in first out.

5. Basic operations: The basic operations are insertion, deletion ,display. In stacks, special terms are given for insert and delete. i.e push for insert and pop is for delete. Push: inserting or adding element into the stack is called push. Pop: deleting or removing element from the stack is called pop.

6. Elements are inserted in the order as A,B,C,D,E It represents the stack of 5 elements. The top most element in the stack is E If we want to delete element E has to be deleted first

7. Pop operation- delete element from the stack

8. Example :-

9. Implementing stack using arrays Algorithm for creating empty stack: Step 1 -  Include all the  header files  which are used in the program and define a constant  'SIZE'  with specific value. Step 2 -  Declare all the  functions  used in stack implementation. Step 3 -  Create a one dimensional array with fixed size ( int stack[SIZE] ) Step 4 -  Define a integer variable  'top'  and initialize with  '-1' . ( int top = -1 ) Step 5 -  In main method, display menu with list of operations and make suitable function calls to perform operation selected by the user on the stack.

10. Algorithm for inserting element into the stack: push(value) - Inserting value into the stack Step 1 -  Check whether  stack  is  FULL . (if top = SIZE-1 ) Step 2 -  If it is  FULL , then display  "Stack is FULL!!! Insertion is not possible!!!"  and terminate the function. Step 3 -  If it is  NOT FULL , then increment  top  value by one ( top 🡨 top +1 ) and set stack[top] to value ( stack[top] 🡨 value ).

11. Explanation for Push The stack is of size max. This procedure inserts an element item on to the top of a stack which is represented by an array stack. The first step of this algorithm checks for an overflow condition. Overflow means inserting element into a stack which is full. If the top value reaches to maximum size of the stack then elements cannot be inserted into the stack i.e. stack is full. Otherwise top is incremented by one and element is inserted into the stack.

12. Algorithm to delete elements from the stack: pop() - Delete a value from the Stack Step 1 -  Check whether  stack  is  EMPTY . (if top = -1 ) Step 2 -  If it is  EMPTY , then display  "Stack is EMPTY!!! Deletion is not possible!!!"  and terminate the function. Step 3 -  If it is  NOT EMPTY , then delete  stack[top]  and decrement  top  value by one ( top 🡨 top -1 ).

13. Explanation for Pop() This procedure deletes an element from the stack. The first step of this algorithm checks for underflow condition. If the top value is -1 then stack is empty. Empty stack is known as underflow. Takeout the element from the location where, the top is pointing and then decrement top by one.

14. display() - Displays the elements of a Stack We can use the following steps to display the elements of a stack Step 1 -  Check whether  stack  is  EMPTY . (if top = -1 ) Step 2 -  If it is  EMPTY , then display  "Stack is EMPTY!!!"  and terminate the function. Step 3 -  If it is  NOT EMPTY , then define a variable ' i ' and initialize with top. Display  stack[i]  value and decrement  i  value by one ( i-- ). Step 3 -  Repeat above step until  i  value becomes '0'.

15. Image: Data Structures using C by Balagurusamy

16. Space complexity Time complexity of push(), pop(),size(), isEmpty(), isFull() will take O(1). Limitation in stack using array is that maximum size of the stack must be pre defined and it cannot be changed(fixed). When trying to add elements in the stack when the stack is full will rise the exception.

17. Consider size of the stack is 4 Insert following elements A,B,C,D Representing Stack with Dynamic array A A B A B C A B C D A B C D E Stack is full when E is inserted create a new stack with double size and copy all the old stack elements to new stack and named it as old stack

18. Representing Stack with Linked List Disadvantage of using an array to implement a stack or queue is the wastage of space. Implementing stacks as linked lists provides a feasibility on the number of nodes by dynamically growing stacks, as a linked list is a dynamic data structure. The stack can grow or shrink as the program demands it to. A variable top always points to top element of the stack. top = NULL specifies stack is empty.

19. In this representation, first node in the list is last inserted element hence top must points to the first element on the stack Last node in the list is the first inserted element in the stack. Thus, push operation always adds the new element at front of the list And pop operation removes the element at front of the list. Size of the stack not required. Test for overflow is not applicable in this case.

20. 10 NULL 1500 1800 1200 1400 20 1400 30 1200 40 1800 50 1500 1100 top Example: The following list consists of five cells, each of which holds a data object and a link to another cell. A variable, top, holds the address of the first cell in the list.

21. Applications of stacks Balancing symbols Parenthesis matching. Infix to prefix conversions. Infix to postfix conversions. Evaluation of postfix expressions. Implementing function calls (Recursion) Undo operations in text editors Matching tags in HTML and XML Quick sort.

22. Conversion of expressions Arithmetic expressions can be represented in three ways: Infix notation Prefix notation Postfix notation

23. Conversion of expressions Infix notation- In which operator should be placed in between the two operands. Example- A+B C-D E*F G/H. Prefix notation (polish notation)- Operator preceded by the operand is called prefix notation Examples +AB -CD *EF \GH. 3. Postfix notation(reverse polish notation or suffix notation)- Operator should be placed after operands. AB+ CD- EF* GH\

24. Notation– Conversions (Infix to Prefix) Consider the infix expression: 2 + 3 * (5 – 7) / 9 Let us insert implicit parentheses (2 + ((3 * (5 – 7)) / 9)) Transfer the operators to the beginning of parentheses (+ 2 (/ (* 3 (– 5 7)) 9)) Remove the parentheses: + 2 / * 3 – 5 7 9 This is the equivalent prefix expression.

25. Notations – Conversions (Infix to Postfix) Consider the infix expression: 2 + 3 * (5 – 7) / 9 Let us insert implicit parentheses (2 + ((3 * (5 – 7)) / 9)) Transfer the operators to the end of parentheses (2 ((3 (5 7 –) *) 9 /) +) Remove the parentheses: 2 3 5 7 – * 9 / + This is the equivalent postfix expression.

26. Examples Infix Expression Prefix Expression Postfix Expression 2 + 3 + 2 3 2 3 + 2 + 3 * 5 + 2 * 3 5 2 3 5 * + (2 + 3) * 5 * + 2 3 5 2 3 + 5 * 2 * 3 – (5 + 9) – * 2 3+ 5 9 2 3 * 5 9 + -

27. Convert infix to postfix expression 1. (A-B)*(D/E) 2. (A+B^D)/(E-F)+G 3. A*(B+D)/E-F*(G+H/K) 4. ((A+B)*D)^(E-F) 5. (A-B)/((D+E)*F) 6. ((A+B)/D)^((E-F)*G) 7. 12/(7-3)+2*(1+5) 8. 5+3^2-8/4*3+6 9. 6+2^3+9/3-4*5 10. 6+2^3^2-4*5

28. Infix to post fix (RPN-Reverse Polish Notation) Conversion Algorithm to convert infix expression to postfix expression(RPN): Declare a stack and postfix array (output : postfix expression) Repeat the following steps until the end of the infix expression is reached. Get input token (constant, variable, arithmetic operator, left parenthesis, right parenthesis) in the infix expression. If the token is A left parenthesis: Push it onto the stack. A right parenthesis: Pop the stack elements and add to postfix array until a left parenthesis is on the top of the stack. Pop the left parenthesis also, but do not add to postfix array An operator: While the stack is nonempty and token has lower or equal priority than stack top element, pop and add to postfix array. Else p ush token onto the stack. An operand: add to postfix array 3. When the end of the infix expression is reached, pop the stack elements and add to postfix array until the stack is empty. (Note: Left parenthesis in the stack has lowest priority)

29. Note the lower precedence operator never placed on top of the higher precedence.

30. Operator Precedence

31. Infix expression- (A+B)^C-(D*E)/F Infix Stack Post fix ( ( Empty A ( A + (+ A B (+ AB ) Empty AB+ ^ ^ AB+ C ^ AB+C - - AB+C^ ( -( AB+C^ D -( AB+C^D * -(* AB+C^D E -(* AB+C^DE ) - AB+C^DE* / -/ AB+C^DE* F -/ AB+C^DE*F Empty AB+C^DE*F/-

32. Convert infix to postfix expression using stack 1. (A-B)*(D/E) 2. (A+B^D)/(E-F)+G 3. A*(B+D)/E-F*(G+H/K) 4. ((A+B)*D)^(E-F) 5. (A-B)/((D+E)*F) 6. ((A+B)/D)^((E-F)*G) 7. 12/(7-3)+2*(1+5) 8. 5+3^2-8/4*3+6 9. 6+2^3+9/3-4*5 10. 6+2^3^2-4*5

33. Appln 2 . Postfix expression evaluation Algorithm Scan expression from left to right and repeat steps 2 and 3 for each element of expression. If an operand is encountered, push it on to stack. If an operator is encountered then remove the top two elements of stack, where A is the top and B is the next top element. evaluate B operator A push the result back on to the stack. set the top value on stack. stop

34. Evaluate the expression • Postfix:- 5,6,2,+,*,12,4,/,- Symbol scanned 5 6 2 + stack content 5 5 6 5 6 2 5 8 40 * 12 4 40 12 40 12 4 / 40 3 - 40-3 37

35. Evaluate the postfix expression 1. 5,3,+,2,*,6,9,7,-,/,- 2. 3,5,+,6,4,-,*,4,1,-,2,^,+ 3. 3,1,+,2,^7,4,1,-,2,*,+,5.-

36. 3.Parenthesis matching The objective of this function is to check the matching of parenthesis in an expression i.e In an expression the no of left parenthesis must be equal to no: of right parenthesis. Ex: ((A+B)*C) This is a valid expression because in this no of left parenthesis (2) = no: of right parenthesis (2).