Stack

Stack using linked list
       1. Memory: ~40N
       2. Every operation takes constant time in the worst case.
       3. Uses extra spaces and time to deal with links.
       4. Slow performance.


Stack using arrary
       1. Memory: ~8N(when full) - ~32N(when one quarter full).
       2. Every operation takes constant amortized time.
       3. Less wasted space. Faster implementation.

import java.util.Iterator;

public class Stack<Item> implements Iterable<Item> {

 private Node first;

 public class Node {
  Item item;
  Node next;
 }

 public Stack() {

 }

 public void push(Item item) {
  if (isEmpty()) {
   first = new Node();
   first.item = item;
  } else {
   Node temp = new Node();
   temp.item = item;
   temp.next = first;

   first = temp;
  }

 }

 public Item pop() {
  Node top = first;
  Item item = top.item;

  first = first.next;

  return item;
 }

 private boolean isEmpty() {
  return first == null;
 }

 public int size() {
  int size = 0;

  Node temp = first;
  while (temp != null) {
   temp = temp.next;
   size++;
  }

  return size;
 }

 @Override
 public Iterator<Item> iterator() {
  return new StackIterator();
 }
 
 private class StackIterator implements Iterator<Item>{
  
  private Node current = first;

  @Override
  public boolean hasNext() {
   return current != null;
  }

  @Override
  public Item next() {
   Item item = current.item;
   current = current.next;
   return item;
  }

  @Override
  public void remove() throws UnsupportedOperationException{
   throw new UnsupportedOperationException();
  }
 }
}

//Stack implementation using array
public class StackArray {
 private String [] data;
 private int size = 0;
   
 public StackArray(){
  data = new String[1];
 }
 
 public void push(String item){
  if(size == data.length) reSize(data.length * 2);
  
  data[size++] = item;
 }
 
 public String pop(){
  
  String item = data[--size];
  data[size] = null;
  if(size < data.length/4) reSize(data.length/2);
  
  return item;
 }
 
 private boolean isEmpty(){
  return size == 0;
 }
 
 private int size(){
  return size;
 }
 
 private void reSize(int capacity){
  String[] temp = new String[capacity];
  int temp_count =0;
  for (int i = 0; i < size; i++) {
   temp[temp_count++] = data[i];
  }
  
  data = temp;
 }
}