Queue

Funktionsweise

Die Datenstruktur Schlange (engl. queue) entspricht einer Warteschlange mit höflichen Menschen: Jeder Neuankömmling stellt sich hinten an und wartet geduldig, bis er ganz vorne steht und an der Reihe ist. Wer also zuerst kommt, ist auch zuerst dran. Entsprechend spricht man bei Schlangen in Anlehnung an die englische Kurzform first in, first out vom FIFO-Prinzip.

Schnittstellenbeschreibung (Zentralabitur)

Queue Schnittstellenbeschreibung (PDF)

Konstruktor Queue<ContentType>()

Nachher Eine leere Schlange ist erzeugt. Nur Objekte vom Typ ContentType können eingefügt werden.

Anfrage isEmpty(): boolean

Nachher: Die Anfrage liefert den Wert true, wenn die Schlange keine Elemente enthält, sonst liefert sie den Wert false.

Auftrag enqueue (ContentType pContent)

Vorher: Die Schlange ist erzeugt.

Nachher: pContent ist als letztes Element an die Schlange gehängt.

Auftrag dequeue()

Vorher: Die Schlange ist nicht leer.

Nachher: Das vorderste Element ist aus der Schlange entfernt.

Anfrage front(): ContentType

Vorher: Die Schlange ist nicht leer.

Nachher: Die Anfrage liefert das vorderste Element der Schlange. Die Schlange ist unverändert.

Objektdiagramm eines Queue

TODO: Objektdiagramm erläutern

Veranschaulichung: Warteschlange

Die Queue funktioniert wie eine Warteschlange an einer (englischen!!) Bushaltestelle: Man kann sich hinten anstellen und vorne wieder eine Person entnehmen.

Veranschaulichung: enqueue(ContentType pContent)

Erläuterung: dequeue()

Implementationsdiagramm

Implementationsdiagramm Queue

• Die Queue hat zwei Nodes: front und last
• Jeder der Nodes hat einen value; darin wird der eigentliche Inhalt gespeichert (z.B. ein Objekt vom Typ Person oder ein String).
• Außerdem hat jeder Node einen Verweis next auf den Nachfolgerknoten.

Implementierung

Für die Implementierung wird die Klasse Node verwendet.

public class Queue<ContentType>{
   private Node<ContentType> frontNode;
   private Node<ContentType> lastNode;
 
   public Queue<ContentType>(){
   }

   public boolean isEmpty(){
       return (frontNode == null);
   }

   public ContentType front(){
       return frontNode.getValue();
   }

   public void enqueue(ContentType pObject){
       Node<ContentType> newNode = new Node<ContentType>(pObject);
       if(frontNode == null){
           frontNode = newNode;
           lastNode = newNode;
       }
       else{
           lastNode.setNext(newNode);
           lastNode = newNode;
       }
   }

   public void dequeue(){
       frontNode = frontNode.getNext();
       if(frontNode == null){
           lastNode = null;
       }
   }
}

Verwendung von Queues

Klassendiagramm der Klasse Buch

Die Verwendung von Queues wird hier aufgezeigt für Queues, die Objekte vom Typ Buch enthalten (vgl. Klassendiagramm rechts)

Methode anzahl

public int anzahl(Queue<Buch> pQueue) {
   int ergebnis = 0;
   Queue<Buch> hilfs = new Queue<Buch>();
   while (!pQueue.isEmpty()) {
      Buch vorderstesBuch = pQueue.front();
      hilfs.enqueue(vorderstesBuch);
      pQueue.dequeue();
      ergebnis++;
   }
   while (!hilfs.isEmpty()) {
      Buch vorderstesBuch = hilfs.front();
      pQueue.enqueue(vorderstesBuch);
      hilfs.dequeue();
   }
   return ergebnis;
}

Methode enthaelt

public boolean enthaelt(Queue<Buch> pQueue, String pTitel) {
   boolean ergebnis = false;
   Queue<Buch> hilfs = new Queue<Buch>();
   while (!pQueue.isEmpty()) {
      Buch vorderstesBuch = pQueue.front();
      if (vorderstesBuch.getTitel().equals(pTitel)) {
         ergebnis = true;
      }
      hilfs.enqueue(vorderstesBuch);
      pQueue.dequeue();
   }
   while (!hilfs.isEmpty()) {
      Buch vorderstesBuch = hilfs.front();
      pQueue.enqueue(vorderstesBuch);
      hilfs.dequeue();
   }
   return ergebnis;
}

Methode loeschen

public void loeschen(Queue<Buch> pQueue, String pTitel) {
   Queue<Buch> hilfs = new Queue<Buch>();
   while (!pQueue.isEmpty()) {
      Buch vorderstesBuch = pQueue.front();
      if (!vorderstesBuch.getTitel().equals(pTitel)) {
         hilfs.enqueue(vorderstesBuch);
      }
      pQueue.dequeue();
   }
   while (!hilfs.isEmpty()) {
      Buch vorderstesBuch = pQueue.front();         
      pQueue.enqueue(vorderstesBuch);
      hilfs.dequeue();
   }
}

Methode alphabetischErstes

private Buch alphabetischErstes(Queue<Buch> pQueue) {
   Queue<Buch> hilfs = new Queue<Buch>();
   Buch aktErstesBuch = pQueue.front();
   while (!pQueue.isEmpty()) {
      String vorderstesBuch = pQueue.front();
      // wenn der Titel von vorderstesBuch im Alphabet VOR dem titel von ergebnis steht, ...
      if (vorderstesBuch.getTitel().compareTo(aktErstesBuch.getTitel()) < 0) {
         // ... dann ergebnis updaten
         aktErstesBuch = vorderstesBuch;
      }
      hilfs.enqueue(vorderstesBuch);
      pQueue.dequeue();
   }
   while (!hilfs.isEmpty()) {
      Buch vorderstesBuch = hilfs.front();
      pQueue.enqueue(vorderstesBuch);
      hilfs.dequeue();
   }
   return ergebnis;
}

Methode alphabetischRichtigEinfuegen

 // Die Methode setzt voraus, dass pQueue schon alphabetisch sortiert und mit Strings gefüllt ist. 
 private void alphabetischRichtigEinfuegen(Queue<String> pQueue, String pString) {
   Queue<String> hilfs = new Queue<String>();
   boolean eingefuegt = false;
   while (!pQueue.isEmpty()) {
      String vorderstes = pQueue.front();
      if (vorderstes.compareTo(pString) > 0 && eingefuegt == false) {
         hilfs.enqueue(pString);
         eingefuegt = true;
      }
      hilfs.enqueue(vorderstes);
      pQueue.dequeue();
   }
   while (!hilfs.isEmpty()) {
      pQueue.enqueue(hilfs.front());
      hilfs.dequeue();
   }
}