Stacks Jan 14 2019 What is a stack A stack is a Last In First Out LIFO data structure Anything added to the stack goes on the top of the stack Anything removed from the stack is taken from the top of the stack Things are removed in the reverse order from that in which they were inserted Constructing a stack To use stacks you need import java util There is just one stack constructor Stack stack new Stack Stack operations I stack push object object stack pop Adds the object to the top of the stack the item pushed is also returned as the value of push 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 stack Stack 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 stack Stacks as Vectors The Stack class extends the Vector class Hence anything you can do with a Vector you can also do with a Stack However this is not how stacks are intended to be used A stack is a very specific data structure defined by the preceding operations it just happens to be implemented by extending Vector Use only the stack operations for Stacks A balancing act is balanced is not Simple counting is not enough to check balance You can do it with a stack going left to right If you see a or push it on the stack If 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 empty Performing calculations To 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 stack If you see an operation If the operation stack is empty push the operation If the top of the operation stack holds a lower precedence operation push the operation If 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 stack At the end perform any remaining operations Example 1 2 3 4 1 push 1 on number stack push on op stack 2 push 2 on number stack compare to then push onto op stack 3 push 3 onto number stack compare to pop 3 2 and compute 2 3 6 push 6 onto number stack push onto op stack 4 push 4 onto number stack end pop 4 6 and compute 6 4 10 push 10 pop 10 1 and compute 1 10 11 push 11 11 top of stack is the answer Stacks in Java Stacks are used for local variables void 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 z y y x The End
View Full Document
Unlocking...