StacksWhat is a stack?Constructing a stackStack operations IStack operations IIStack ancestrySome uses of stacksA balancing actExpression evaluationPerforming calculationsExample: 1+2*3+4Handling parenthesesHandling variablesHandling the = operatorAt the endSome things that can go wrongTypes of storageStacks in JavaSupporting recursionFactorial (animation 1)Factorial (animation 2)Factorial (animation 3)Factorial (animation 4)Factorial (animation 5)Factorial (animation 6)Stack framesGeneric Stacks in Java 5SummaryThe EndStacks2What is a stack?A stack is a Last In, First Out (LIFO) data structureAnything added to the stack goes on the “top” of the stackAnything removed from the stack is taken from the “top” of the stackThings are removed in the reverse order from that in which they were inserted3Constructing a stackTo use stacks, you need import java.util.*;There is just one stack constructor: Stack stack = new Stack();4Stack operations I stack.push(object)Adds the object to the top of the stack; the item pushed is also returned as the value of push object = stack.pop();Removes the object at the top of the stack and returns it object = stack.peek();Returns the top object of the stack but does not remove it from the stack5Stack operations II stack.empty() Returns true if there is nothing in the stack int i = stack.search(object);Returns the 1-based position of the element on the stack. That is, the top element is at position 1, the next element is at position 2, and so on.Returns -1 if the element is not on the stack6Stack ancestryThe Stack class extends the Vector classHence, anything you can do with a Vector, you can also do with a StackHowever, this is not how stacks are intended to be usedA “stack” is a very specific data structure, defined by the preceding operations; it just happens to be implemented by extending VectorUse only the stack operations for Stacks!The Vector class implements the Collection interfaceHence, anything you can do with a Collection, you can also do with a StackThe most useful operation this gives you is toArray()7Some uses of stacksStacks are used for:Any sort of nesting (such as parentheses)Evaluating arithmetic expressions (and other sorts of expression)Implementing function or method callsKeeping track of previous choices (as in backtracking)Keeping track of choices yet to be made (as in creating a maze)8A balancing act([]({()}[()])) is balanced; ([]({()}[())]) is notSimple counting is not enough to check balanceYou can do it with a stack: going left to right,If you see a (, [, or {, push it on the stackIf you see a ), ], or }, pop the stack and check whether you got the corresponding (, [, or {When you reach the end, check that the stack is empty9Expression evaluationAlmost all higher-level languages let you evaluate expressions, such as 3*x+y or m=m+1The simplest case of an expression is one number (such as 3) or one variable name (such as x)These are expressionsIn many languages, = is considered to be an operatorIts value is (typically) the value of the left-hand side, after the assignment has occurredSituations sometimes arise where you want to evaluate expressions yourself, without benefit of a compiler10Performing calculationsTo evaluate an expression, such as 1+2*3+4, you need two stacks: one for operands (numbers), the other for operators: going left to right,If you see a number, push it on the number stackIf you see an operator,While the top of the operator stack holds an operator of equal or higher precedence:pop the old operatorpop the top two values from the number stack and apply the old operator to them push the result on the number stackpush the new operator on the operator stackAt the end, perform any remaining operations11Example: 1+2*3+41 : push 1 on number stack+ : push + on op stack2 : push 2 on number stack* : because * has higher precedence than +, push * onto op stack3 : push 3 onto number stack+ : because + has lower precedence than *: pop 3, 2, and *compute 2*3=6, and push 6 onto number stackpush + onto op stack4 : push 4 onto number stackend : pop 4, 6 and +, compute 6+4=10, push 10; pop 10, 1, and +, compute 1+10=11, push 1111 (at the top of the stack) is the answer12Handling parenthesesWhen you see a left parenthesis, (, treat it as a low-priority operator, and just put it on the operator stackWhen you see a right parenthesis , ), perform all the operations on the operator stack until you reach the corresponding left parenthesis; then remove the left parenthesis13Handling variablesThere are two ways to handle variables in an expression:When you encounter the variable, look up its value, and put its value on the operand (number) stackThis simplifies working with the stack, since everything on it is a numberWhen you encounter a variable, put the variable itself on the stack; only look up its value later, when you need itThis allows you to have embedded assignments, such as 12 + (x = 5) * x14Handling the = operatorThe assignment operator is just another operatorIt has a lower precedence than the arithmetic operatorsIt should have a higher precedence than (To evaluate the = operator:Evaluate the right-hand side (this will already have been done, if = has a low precedence)Store the value of the right-hand side into the variable on the left-hand sideYou can only do this if your stack contains variables as well as numbersPush the value onto the stack15At the endTwo things result in multiple special casesYou frequently need to compare the priority of the current operator with the priority of the operator at the top of the stack—but the stack may be emptyEarlier, I said: “At the end, perform any remaining operations”There is a simple way to avoid these special casesInvent a new “operator,” say, $, and push it on the stack initiallyGive this operator the lowest possible priorityTo “apply” this operator, just quit—you’re done16Some things that can go wrongThe expression may be ill-formed: 2 + 3 +When you go to evaluate the second +, there won’t be two numbers on the stack 1 2 + 3When you are done evaluating the expression, you have more than one number on the stack (2 + 3You have an unmatched ( on the stack 2 + 3)You can’t find a matching ( on
View Full Document
Unlocking...