Stack
Basics#
- Stack Implements Vector(sync), Vector implements List
- Anything you can do with Stack you can do with linkedlist, the only reason to use stack will be to utilize synchronous ability of Vector, since Stack implements a Vector
- common menthods:
Methods#
| empty() | O(1) | To test if this stack is empty | boolean |
|---|---|---|---|
| peek() | O(1) | looks at the top of the stack without removing it from the stack | E |
| pop() | O(1) | Removes the object at the top of this stack and returns that object as the value of this function. | E |
| push() | O(1) | Pushes an item onto the top of this stack. | E |
| search(Object o) | O(n) | Returns the 1-based position where an object is on this stack. | int |
Implementation#
- list: push is to add node to the front of list and pop is to remove from front of list
- array: topOfStack is initialized to -1, when push, arr[topOfStack++]=element; when pop, return arr[--topOfStack]; use topOfStack==-1 to check if emtpy
Applications#
- balance symbols
- postfix expression
- infix to postfix conversion
- method calls