Queue: Unterschied zwischen den Versionen
Zeile 42: | Zeile 42: | ||
= Objektdiagramm einer Queue = | = Objektdiagramm einer Queue = | ||
[[Datei: | [[Datei:Klassendiagramm-Queue.png]] | ||
TODO: Objektdiagramm erläutern | TODO: Objektdiagramm erläutern | ||
Version vom 9. August 2016, 07:29 Uhr
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
Datei:Klassendiagramm-Queue.png 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
- Die Queue hat zwei Nodes:
head
undtail
- Jeder der Nodes hat einen
content
; darin wird der eigentliche Inhalt gespeichert (z.B. ein Objekt vom TypPerson
oder einString
). - 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
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();
}
}