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.