Stacks - L12 PDF

Stacks Ratna Choudhury The University of Winnipeg Collegiate Stacks A stack is a list of elements in which an element may be inserted or deleted only at one end called the top of the stack. The last item to be added to a stack is the first item to be removed. Stacks are also calle...

Stacks Ratna Choudhury The University of Winnipeg Collegiate Stacks A stack is a list of elements in which an element may be inserted or deleted only at one end called the top of the stack. The last item to be added to a stack is the first item to be removed. Stacks are also called last-in first-out (LIFO) lists. Basic Operations Special terminology for basic operations: ❖ Push: to insert an element into a stack. ❖ Pop: to delete an element from a stack. These terms are used only with stacks, not with other data structures.  Example Suppose the following 6 elements are pushed onto an empty stack: AAA, BBB, CCC, DDD, EEE, FFF 1 AAA 2 BBB TOP 3 TOP CCC 4 DDD FFF 5 EEE EEE 6 FFF AAA BBB CCC DDD EEE FFF ….. DDD 7 1 2 3 4 5 6 7 8 9 N-1 N CCC 8 BBB 9 TOP AAA … N-1 N Array Representation of Stacks Stacks may be represented by a linear array STACK TOP: pointer variable which contains the location of the top element MAXSTK: variable gives the maximum number of elements that can be held by the stack If TOP = 0 or TOP = NULL, the stack is empty. XXX YYY ZZZ 1 2 3 4 5 6 7 8 TOP 3 MAXSTK 8 TOP = 3 as the stack has three elements, XXX, YYY and ZZZ. MAXSTK = 8 as there is room for 5 more items PUSH operation PUSH(STACK, TOP, MAXSTK, ITEM) 1. [Stack already filled?] If TOP = MAXSTK, then Print: OVERFLOW, and Return. 2. Set TOP = TOP +1. [increases TOP by 1.] 3. Set STACK[TOP] = ITEM [Inserts ITEM in new TOP position.] 4. Return. Example PUSH (STACK, WWW) 1. Since TOP = 3, control is transferred step 2. 2. TOP = 3+1 = 4 3. STACK[TOP] = STACK = WWW 4. Return. POP operation POP(STACK, TOP, ITEM) 1. [Stack has an item to be removed?] If TOP = 0, then Print: UNDERFLOW, and Return. 2. Set ITEM = STACK[TOP]. [Assigns TOP element to ITEM.] 3. Set TOP = TOP - 1 [Decreases TOP by 1.] 4. Return. Example POP(STACK, TOP, ITEM) 1. Since TOP = 3, control is transferred to step 2. 2. ITEM = ZZZ 3. TOP = 3-1 = 2 4. Return Arithmetic Expressions: Polish Notation Infix Notation: For most common arithmetic operations, the operator symbol is placed between its two operands. This is called Infix notation. A+B C–D E*F and G / H  Polish Notation: It is named after the Polish mathematician Jan Lukasiewiez. It refers to the notation in which the operator symbol is placed before its two operands. It is also known as Prefix notation. +AB -CD *EF /GH  Translate from Infix to Polish Notation: (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: - The order in which the operations are to be performed is completely determined by the positions of the operators and operands in the expression. - One never needs parentheses when writing expressions in Polish notation.  Reverse Polish Notation: It refers to the analogous notation in which the operator symbol is placed after its two operands. It is also known as Postfix or Suffix notation. AB+ CD- EF* GH/ One never needs parentheses when writing expressions in reverse Polish notation. Transform: Postfix to Infix Expression Consider Postfix expression: P: 5 6 2 + * 12 4 / - Equivalent Infix expression: Q: 5 * ( 6 + 2 ) – 12 / 4 Add a right parentheses at the end of P: P: 5 6 2 + * 12 4 / - ) (1) (2) (3) (4) (5) (6) (7) (8) (9) (10) Symbol Scanned STACK (1) 5 5 (2) 6 5, 6 (3) 2 5, 6, 2 (4) + 5, 8 (5) * 40 (6) 12 40, 12 (7) 4 40, 12, 4 (8) / 40, 3 (9) - 37 (10) ) Transform: Infix to Postfix Expression Consider Infix expression: Q: A + (B * C – (D / E F) * G) * H Equivalent Postfix expression: P: ABC*DEF /G*-H*+ First push “(” onto STACK and then add a “)” at the end of Q: 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) (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*+ Quicksort An application of Stacks. Let A be a list of n data items. Sorting A refers to the operation of rearranging the elements of A so that they are in some logical order. - numerically ordered when A contains numerical data - alphabetically ordered when A contains character data Quicksort is an algorithm of the divide and conquer type.  Suppose A is the following list of 12 numbers: 44, 33, 11, 55, 77, 90, 40, 60, 99, 22, 88, 66 Reduction step: Quicksort algorithm finds the final position of the first number 44. Step 1: Beginning with last number 66, scan the list from right to left, comparing each number with 44 and stopping at the first number less than 44. Interchange 44 and 22. 22, 33, 11, 55, 77, 90, 40, 60, 99, 44, 88, 66  Step 2: Beginning with 22, next scan the list in the opposite direction, from left to right, comparing each number with 44 and stopping at the first number greater than 44. Interchange 44 and 55. 22, 33, 11, 44, 77, 90, 40, 60, 99, 55, 88, 66 Step 3: Beginning this time with 55, scan the list from right to left, comparing each number with 44 and stopping at the first number less than 44. Interchange 44 and 40. 22, 33, 11, 40, 77, 90, 44, 60, 99, 55, 88, 66  Step 4: Beginning with 40, scan the list in the opposite direction, from left to right, comparing each number with 44 and stopping at the first number greater than 44. Interchange 44 and 77. 22, 33, 11, 40, 44, 90, 77, 60, 99, 55, 88, 66 Step 5: Beginning with 77, scan the list from right to left, comparing each number with 44 and stopping at the first number less than 44. We do not meet such number before 44. This means all numbers have been scanned and compared with 44. Also, all numbers less than 44 form the sublist of numbers to the left of 44 and all numbers greater than 44 form the sublist of numbers to the right of 44. 22, 33, 11, 40, 44, 90, 77, 60, 99, 55, 88, 66 First sublist Second sublist Thus 44 is correctly placed in its final position. The task of sorting the original list A has now been reduced to the the task of sorting each of the above sublists. Complexity Worst-case running time of order: n2/2 Average-case running time of order: n log n Best-case running time of order: O (n log n)