2.3 🚧 Warteschlange und Ringpuffer

Synopsis: [Wikipedia: Warteschlange_(Datenstruktur)]

Elemente werden mit enqueue(e:Typ) in die Schlange vorne hinzugefügt.
Mit dequeue():Typ werden die Elemente hinten weggenommen.
istLeer():Boolean gibt true zurück, wenn Stapel leer ist
anzahlElemente():GZ gibt die Anzahl der Elemente zurück
Stacks werden auch FIFO (First In First Out) Speicher genannt.

Warteschlange mit Liste implementieren

Ergänzen Sie den Code für dequeue()

public class Warteschlange <Typ>{
  private Knoten <Typ> kopf;
  private Knoten <Typ> ende;
  public boolean istLeer(){
    return kopf==null;
  }
  public void enqueue(Typ e){
      Knoten  k = new Knoten(e);
      if(kopf==null)ende=k;
      k.setzeNaechsten(kopf);
      kopf=k;
  }
   public Typ dequeue(){
     if(kopf!=null){
       ...
     }
     return null;
  }
  public int anzahlElemente(){
     int i = 0;
     Knoten k = kopf;
     while (k!=null){
         i++;
         k=k.gibNaechsten();
     }
     return i;
  }
  public void ausgebenWarteschlange(){
    if(kopf==null){
        System.out.println("Warteschlange ist leer");
    }
    else{
      System.out.print("Schlangeninhalt: ");
      Knoten k = kopf;
      while (k!=null){
        System.out.print(k.gibInhalt()+" ");
        k=k.gibNaechsten();
      }
      System.out.println();
    }
  }
}

public class Knoten <Typ>{
  private Typ inhalt;
  private Knoten<Typ> naechster;
  public Knoten(Typ e){
    inhalt = e;    
  }
  public void setzeNaechsten(Knoten <Typ> n){
    naechster = n;
  }
  public Knoten<Typ> gibNaechsten(){
      return naechster;
  }
  public Typ gibInhalt(){
      return inhalt;
  }
}

public class Test{
  public static void teste(){
    System.out.print("\f"); // Konsole leeren
    Warteschlange<Integer> w = new Warteschlange();
    w.ausgebenWarteschlange();
    w.enqueue(3);
    w.enqueue(5);
    System.out.println("Anzahl: "+w.anzahlElemente());
    w.ausgebenWarteschlange();
    System.out.println("dequeue: "+w.dequeue());
    w.ausgebenWarteschlange();
    System.out.println("dequeue: "+w.dequeue());
    System.out.println("dequeue: "+w.dequeue());
  }
}

Lösungsvorschlag dequeue()

public Typ dequeue(){
     if(kopf!=null){
       Typ ret = ende.gibInhalt();
       if(kopf==ende){ // nur ein Element
         kopf=ende=null;
       }
       else{ // mehrere Elemente
         Knoten k = kopf;
         while (k!=null){
           if(k.gibNaechsten()==ende){
             k.setzeNaechsten(null);
             ende=k;
             break;
           }
           k=k.gibNaechsten();
         }    
       }
       return ret;
     }
     return null;
  }