Stack is a last in first out (LIFO) data structure. Program's calling stack is a LIFO -- the calling function can not continue until the function it called return.
The basic method includes push and pop.
It can be implemented with linked list or ArrayList.
Linked list nodes are added as last in first out -- start from head node, traversal down the links, the first node we meet is the last node we added, the last node we meet is the first node we added -- the linked list is a natural stack.
 |
| linked list as LIFO |
If implemented with linked list, the push can be implemented by inserting a node behind the header node; while pop can be implemented by deleting the node behind the header node. Both push and pop have time complexity O(1). We need N linked list nodes to implement a stack with size N, the space complexity is O(N).
If implemented with ArrayList, the push can be implemented by delegating to ArrayList's add method; while pop can be implemented by delegating to ArrayList's get method. Both push and pop have time complexity O(1). We need N ArrayList elements to implement a stack with size N, the space complexity is O(N) as well.
The LinkedList implementation has advantage for maxSize unlimited stack. We can keep add more node with cost O(1) for linked list. ArrayList implementation, on the other hand, is based on array, the size is not flexible. When stackSize is bigger than the existing array size, the ArrayList implementation has to create a bigger array, then copy the existing array elements to the new array, the cost will be proportional to O(N) for those array copy operation.
Example code:
LNode.java
StackImplLinkedList.java
StackImplList.java
