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 einer Queue

Klassendiagramm der Klasse QueueNode

Die Queue selbst hat nur die beiden Attribute head und tail, sie kann demnach nur auf den ersten und den letzten Knoten direkt zugreifen. Dies reicht aus, da Queue-Operationen immer nur ganz vorne (Anschauen, Löschen) bzw. ganz hinten (Hinzufügen) möglich sind und die QueueNodes untereinander verbunden sind (jeder QueueNode hat ein Attribut nextNode, in dem eine Referenz auf das darunter liegende QueueNode-Objekt gespeichert ist).

Veranschaulichung: Warteschlange

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

(In der Animation heißen die beiden Attribute der Klasse Queue front und last (statt head und tail wie in der Abi-Schnittstelle).)

Veranschaulichung: enqueue(ContentType pContent)

Erläuterung: dequeue()

Implementationsdiagramm

Implementationsdiagramm Queue

• Die Queue hat zwei Nodes: head und tail (Wenn nur ein Node enthalten ist, ist dieser sowohl head als auch tail).
• Jeder der Nodes hat einen content; darin wird der eigentliche Inhalt gespeichert (z.B. ein Objekt vom Typ Person oder ein String).
• Außerdem hat jeder Node einen Verweis nextNode auf den Nachfolgerknoten.

Implementierung

Für die Implementierung wird die Klasse QueueNode verwendet.

public class Queue<ContentType>{
   private QueueNode head;
   private QueueNode tail;

  /**
  * Eine leere Schlange wird erzeugt.
  * Objekte, die in dieser Schlange verwaltet werden, muessen vom Typ
  * ContentType sein.
  */
  public Queue() {
     head = null;
     tail = null;
  }

  /**
  * Die Anfrage liefert den Wert true, wenn die Schlange keine Objekte enthaelt,
  * sonst liefert sie den Wert false.
  *
  * @return true, falls die Schlange leer ist, sonst false
  */
  public boolean isEmpty() {
     return head == null;
  }

  /**
  * Das Objekt pContentType wird an die Schlange angehaengt.
  * Falls pContentType gleich null ist, bleibt die Schlange unveraendert.
  *
  * @param pContent
  * das anzuhaengende Objekt vom Typ ContentType
  */
  public void enqueue(ContentType pContent) {
     if (pContent != null) {
        QueueNode newNode = new QueueNode(pContent);
        if (this.isEmpty()) {
           head = newNode;
           tail = newNode;
        } else {
           tail.setNext(newNode);
           tail = newNode;
        }
     }
  }

  /**
  * Das erste Objekt wird aus der Schlange entfernt.
  * Falls die Schlange leer ist, wird sie nicht veraendert.
  */
  public void dequeue() {
     if (!this.isEmpty()) {
        head = head.getNext();
        if (this.isEmpty()) {
           head = null;
           tail = null;
        }
     }
  }

  /**
  * Die Anfrage liefert das erste Objekt der Schlange.
  * Die Schlange bleibt unveraendert.
  * Falls die Schlange leer ist, wird null zurueckgegeben.
  *
  * @return das erste Objekt der Schlange vom Typ ContentType oder null,
  * falls die Schlange leer ist
  */
  public ContentType front() {
     if (this.isEmpty()) {
        return null;
     } else {
        return head.getContent();
     }
  }
}

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();
   }
}