/**
  * RecursiveQueueBySingleStack
  * realizza una coda, usando una sola pila e la ricorsione
  * L'algoritmo funziona perche' l'esecuzione avviene tramite
  * un altro stack: il Java Stack!
  * classe per esercitazione: laboratorio 8
  * La realizzazione e', ovviamente, inefficiente
  * @author Adriano Luchetta
  * @version 24.Nov.2006
  * @version 21-Nov-2005
  * @version 3-Dic-2004
  * @see Queue
*/
public class RecursiveQueueBySingleStack implements Queue
{
   //parte privata
   Stack pila;
   
   //parte pubblica
   public RecursiveQueueBySingleStack()
   {
      pila = new ArStack();
   }

   public boolean isEmpty()
   {
      return pila.isEmpty();
   }
   
   public void makeEmpty()
   {
      pila.makeEmpty();
   }
   
   public int size()
   {
      return pila.size();
   }

   public void enqueue(Object obj)
   {
      pila.push(obj);
   }

   /**
      ispeziona l'elemento in testa alla coda.
      O(n)
      @return elemento in testa alla coda
      @throws EmptyQueueException se la coda e' vuota
   */
   public Object getFront() throws EmptyQueueException
   {
      if (isEmpty())
         throw new EmptyQueueException();

      return getFront(pila);
   }

   /**
      estrae l'elemento in testa alla coda.
      O(n)
      @return elemento in testa alla coda
      @throws EmptyQueueException se la coda e' vuota
   */
   public Object dequeue() throws EmptyQueueException
   {
       if (isEmpty())
         throw new EmptyQueueException();

      return dequeue(pila);
   }
   
   // metodo ricorsivo
   private Object getFront(Stack pila)
   {
      // caso base
      if (pila.size() == 1)
         return pila.top();
         
      // chiamata ricorsiva
      Object obj = pila.pop();
      Object front = getFront(pila);
      pila.push(obj);
      
      return front;
   }
   
   // metodo ricorsivo
   private Object dequeue(Stack pila)
   {
      if (pila.size() == 1)
         return pila.pop();
         
      // chiamata ricorsiva
      Object last = pila.pop();
      Object first = dequeue(pila);
      pila.push(last);

      return first;
   }
}