StacksWhat is a stack?Constructing a stackStack operations IStack operations IIStacks as VectorsA balancing actPerforming calculationsExample: 1+2*3+4Stacks in JavaThe EndJan 14, 2019StacksWhat 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 insertedConstructing a stackTo use stacks, you need import java.util.*;There is just one stack constructor: Stack stack = new Stack();Stack operations Istack.push(object)Adds the object to the top of the stack; the item pushed is also returned as the value of pushobject = stack.pop();Removes the object at the top of the stack and returns itobject = stack.peek();Returns the top object of the stack but does not remove it from the stackStack operations IIstack.empty() Returns true if there is nothing in the stackint 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 stackStacks as VectorsThe 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!A 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 emptyPerforming calculationsTo evaluate an expression, such as 1+2*3+4, you need two stacks: one for numbers, the other for operations: going left to right,If you see a number, push it on the number stackIf you see an operation,If the operation stack is empty, push the operationIf the top of the operation stack holds a lower precedence operation, push the operationIf the top of the operation stack holds a higher precedence operation, pop it, perform the operation on the top two values in the number stack, push the result on the number stack, and push the new operation on the operation stackAt the end, perform any remaining operationsExample: 1+2*3+41 : push 1 on number stack+ : push + on op stack2 : push 2 on number stack* : compare * to +, then push * onto op stack3 : push 3 onto number stack+ : compare + to *, pop 3, 2, and *, compute 2*3=6, push 6 onto number stack, push + 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 (top of stack) is the answerStacks in JavaStacks are used for local variablesvoid methodA() { int x, y; // puts x, y on stack y = 0; methodB(); y++;}void methodB() { int y, z; // puts y, z on stack y = 5; return; // removes y, z}xyyzThe
View Full Document
Unlocking...