/**
realizza l'interfaccia Stack usando internamente un array riempito parzialmente.
@author Adriano Luchetta
@version 16-Nov-2003
@version 27-Nov-2004
*/

public class ArStack implements Stack
{
   //parte privata
   private Object[] list;
   private int listSize;
   
   public ArStack()
   {
      list = new Object[1];
      listSize = 0;
   }
   
   /**
     O(1)
   */
   public boolean isEmpty()
   {
      return listSize == 0;
   }
   
   /**
     O(1)
   */
   public void makeEmpty()
   {
      listSize = 0;
   }
   
   /**
     O(1)
   */
   public int size()
   {
      return listSize;
   }

   /**
     in media O(1)
   */
   public void push(Object obj)
   {
      if (listSize == list.length)
      {
         Object[] newList = new Object[2 * list.length];
         for (int i = 0; i < list.length; i++)
            newList[i] = list[i];
         list = newList;
      }
            
      list[listSize] = obj;
      listSize++;
   }

   /**
   O(1)
   */
   public Object top() throws EmptyStackException
   {
      if (isEmpty())
         throw new EmptyStackException();

      return list[listSize - 1];
   }

   /**
   O(1)
   */
   public Object pop() throws EmptyStackException
   {
      Object obj = top();
      list[listSize-1] = null;
      listSize--;
      return obj;
   }
}