import java.util.EmptyStackException;
/** A simple recursive stack.
    @author Jed Yang, 2017-02-05

    Does not permit null values.
*/
public class RecursiveStack<T> implements Stack<T>
{
   private T top;                   // not null if 1+ elements
   private RecursiveStack<T> rest;  // not null if 2+ elements

   public RecursiveStack()
   {
      top = null;
      rest = null;
   }

   /** Adds an item to the top of this stack.
       @param item The item to add.
       @throws NullPointerException if element is null
   */
   public void push(T item)
   {
      // do not accept null values
      if (item == null)
         throw new NullPointerException("this stack does not permit null elements");

      if (top != null) // 1+ elements
      {
         // if 1 element, need to initialize rest stack
         if (rest == null)
            rest = new RecursiveStack<T>();
         rest.push(top);
      }
      top = item;
   }
   
   /** Removes and returns the item from the top of this stack.
       @return The item at the top of the stack.
       @throws EmptyStackException if stack is empty.
   */
   public T pop()
   {
      if (top == null) // 0 elements
         throw new EmptyStackException();

      T toReturn = top; // save the top value
      if (rest == null) // 1 element
      {
         top = null;
      }
      else // 2+ elements
      {
         top = rest.pop();
         if (rest.isEmpty())
            rest = null; // de-allocate empty stack
      }
      return toReturn;
   }
   
   /** Returns the item on top of the stack, without removing it.
       @return The item at the top of the stack.
       @throws EmptyStackException if stack is empty.
   */
   public T peek()
   {
      if (top == null)
         throw new EmptyStackException();
      return top;
   }
   
   /** Returns whether the stack is empty. 
       @return True if the stack is empty; false otherwise.
   */
   public boolean isEmpty()
   {
      return top == null;
   }
   
   /** Removes all items from the stack. */
   public void clear()
   {
      top = null;
      rest = null;
   }
}