Stacks in Java
(Again)
There is Top, Push, Pop, Peek, isEmpty, with O(1) run time complexity.
Stacks can be implemented with arrays and Linked Lists.
Useful for
Undo-redo
Program memory/running
cases where last element/case have priority among others
Google maps(kind of)
With Arraylist, for adding to head, it shifts everything, which is O(n) runtime.
Push to Stack
Node newNode = new Node(3);
newNode.setNext(top);
top = newNode;Pop from Stack
Assumes that there is at least one item in the stack.
returnVal = top.getItem;
top = top.getNext();Push to Array Stack
IF all positions of starting Array is full?
You can create a new array, and refill the old values into the new array.
top = 5;
stackArr[top] = 9;
top += 1;Pop from Array Stack
top = 6;
returnedElem = stackArr[top-1];
top -= 1;Peek to Array Stack
return stackArr[top];IF you have mutliple stacks and want to use it, it’s better to have an interface, so you can generalize it
With isempty()
use size <= 0, not ==, since if size is -1, it will still send it.
Push could send a boolean, on whether or not it worked.
Make ++, and - - size protected, with final public, so that other packages can’t use/modify it.