/**
   usa come struttura dati un array riempito parzialmente ridimensionabile
   FIFO: elementi inseriti all'indice vSize ed estratti all'indice 0
   LIFO: elementi inseriti ed estratti all'indice vSize
   
   Tutti i metodi della classe hanno complessita' temporale O(1) ad esclusione:
   - del metodo dequeue() che e' sempre O(n)
   - del metodo pushAndEnqueue() che e' O(n) nelle chiamate in cui avviene il
     ridimensionamento, O(1) altrimenti
*/

public class MySQ implements StackAndQueue
{
   private Object[] v;
   private int vSize;
   
   public MySQ()
   {
      makeEmpty();
   }
   
   /** O(1) senza ridimensionamento, O(n) con ridimensionamento */
   public void pushAndEnqueue(Object obj)
   {
      if (vSize >= v.length)
      {
        Object[] tmp = new Object[2 * v.length];
        for (int i = 0; i < v.length; i++)
          tmp[i] = v[i];
          
        v = tmp;
      }

      v[vSize] = obj;
      vSize++;
   }

   /** O(1) */
   public Object pop() throws EmptyStackException
   {
      Object tmpObj = top();
      v[vSize - 1] = null;
      vSize--;

      return tmpObj;
   }
   
   /* O(n) */
   public Object dequeue() throws EmptyQueueException
   {
      Object tmpObj = getFront();
      for (int i = 0; i < vSize - 1; i++)
        v[i] = v[i + 1];
      vSize--;

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

      return v[vSize - 1];
   }
   
   /** O(1) */
   public Object getFront() throws EmptyQueueException
   {
      if (isEmpty())
        throw new EmptyQueueException();

      return v[0];
   }
   
   /** O(1) */
   public void makeEmpty()
   {
      v = new Object[1];
      vSize = 0;
   }
   
   /** O(1) */
   public boolean isEmpty()
   {
      return vSize == 0;
   }
   
   /** O(1) */
   public int size()
   {
      return vSize;
   }
}