/**
 * Klasse Queue zur Umsetzung des ADT Schlange entsprechend der Vorgaben
 * des KC Informatik für die gymnasiale Oberstufe in Niedersachsen
 * @author Landesnetzwerk Informatik Niedersachsen, Carsten Rohe
 * @version 0.8_20200429
 */
public class Queue
{
  private int length;
  private Element head;

  /**
   * Eine leere Schlange wird angelegt.
   */
  public Queue()
  {
    length = 0;
    head = null;
  }   
  
  /**
   * Es wird geprüft, ob die Schlange leer ist.
   * @return Wenn die Schlange kein Element enthält, wird der Wert true zurückgegeben, sonst der Wert false.
   */
  public boolean isEmpty()
  {
    if (length==0)
      return true;
    //else 
    return false;
  }
  
  /**
   * Der Inhalt des ersten Elements der Schlange wird ausgelesen.
   * Das Element wird dabei aber nicht aus der Schlange entfernt.
   * @return Der Inhalt des ersten Elements der Schlange.
   */
  public Object head()
  {
    if (!isEmpty())
      return head.data;
    //else
    return null;
  }
  
  /**
   * Ein neues Element mit dem übergebenen Inhalt wird an die Schlange angehängt.
   * @param data Der Inhalt für das neue Element.
   */ 
  public void enqueue(Object data)
  {
    if (!isEmpty())
    {
      getElement(length-1).next = new Element(data);
    }
    else
    {
      head = new Element(data);
    }
    length++;
  }
  
  /**
   * Das erste Element der Schlange wird entnommen und dessen Inhalt zurückgegeben. 
   * @return Der Inhalt des entnommenen Elements.
   */
  public Object dequeue()
  {
    if (!isEmpty())
    {
      Element temp = head;
      head = head.next;
      length--;
      return temp.data;
    }
    // else
    return null;
  }

  private Element getElement(int index)
  {  
    // Interne Hilfsoperation zum vereinfachten Zugriff auf die Elemente der Reihung
    // durch die öffentlichen Operationen
    if (length >= index)
    {
      Element current = head;
      for (int i=0; i < index; i++)
      {
        current = current.next;
      }
      return current;
    }
    return null;
  }

  // Klasse Element zur internen Verwaltung der einzelnen Elemente der Schlange
  private class Element
  {
    public Object data;
    public Element next;

    public Element(Object d)
    {
      data = d;
      next = null;
    }
  } //Ende der Klasse Element
} //Ende der Klasse Queue
