Queue: Unterschied zwischen den Versionen
(27 dazwischenliegende Versionen von 2 Benutzern werden nicht angezeigt) | |||
Zeile 3: | Zeile 3: | ||
[[Kategorie:Informatik-Abitur]] | [[Kategorie:Informatik-Abitur]] | ||
[[Kategorie:Datenstrukturen(IF)]] | [[Kategorie:Datenstrukturen(IF)]] | ||
=Fachbegriffe= | |||
Schlange (Queue), hinten anhängen (enqueue()), vorne entfernen (dequeue()), ist leer (isEmpty()) | |||
= Funktionsweise = | = 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. | 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. | ||
Zeile 15: | Zeile 22: | ||
Anfrage '''isEmpty() | Anfrage '''boolean isEmpty()''' | ||
Nachher: Die Anfrage liefert den Wert true, wenn die Schlange keine Elemente | Nachher: Die Anfrage liefert den Wert true, wenn die Schlange keine Elemente | ||
Zeile 35: | Zeile 42: | ||
Anfrage '''front() | Anfrage '''ContentType front()''' | ||
Vorher: Die Schlange ist nicht leer. | Vorher: Die Schlange ist nicht leer. | ||
Zeile 42: | Zeile 49: | ||
= Objektdiagramm einer Queue = | = Objektdiagramm einer Queue = | ||
[[Datei: | |||
[[Datei:Queue.png]] | |||
Die Queue selbst hat nur die beiden Attribute <code>'''front'''</code> und <code>'''last'''</code>, 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 <code>[[Node|Nodes]]</code> untereinander verbunden sind (jeder <code>[[Node]]</code> hat ein Attribut <code>next</code>, in dem eine Referenz auf das darunter liegende <code>[[Node]]</code>-Objekt gespeichert ist). | |||
= Veranschaulichung: Warteschlange = | = Veranschaulichung: Warteschlange = | ||
Die Queue funktioniert wie eine Warteschlange an einer (englischen!!) Bushaltestelle: Man kann sich hinten anstellen und vorne wieder eine Person entnehmen. | 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)==== | ====Veranschaulichung: enqueue(ContentType pContent)==== | ||
Zeile 53: | Zeile 63: | ||
====Erläuterung: dequeue()==== | ====Erläuterung: dequeue()==== | ||
[[Datei:DequeueJava.gif|border]] | [[Datei:DequeueJava.gif|border]] | ||
= Verwendung von Queues = | = Verwendung von Queues = | ||
Zeile 147: | Zeile 69: | ||
Die Verwendung von Queues wird hier aufgezeigt für Queues, die Objekte vom Typ Buch enthalten (vgl. Klassendiagramm rechts) | Die Verwendung von Queues wird hier aufgezeigt für Queues, die Objekte vom Typ Buch enthalten (vgl. Klassendiagramm rechts) | ||
'''Vorsicht:'''<br/> | |||
Wenn man einen Queue durchläuft, dann muss man die Inhalte auf einen Hilfs-Queue "retten" und am Ende wieder zurück auf den eigentlichen Queue übertragen! | |||
== Methode anzahl == | == Methode anzahl == | ||
<code> | <code> | ||
public int anzahl(Queue<Buch> pQueue) { | public int anzahl(Queue<Buch> pQueue) { | ||
int ergebnis = 0; | int ergebnis = 0; | ||
Zeile 165: | Zeile 90: | ||
return ergebnis; | return ergebnis; | ||
} | } | ||
</code> | </code> | ||
== Methode enthaelt== | == Methode enthaelt== | ||
<code> | <code> | ||
public boolean enthaelt(Queue<Buch> pQueue, String pTitel) { | public boolean enthaelt(Queue<Buch> pQueue, String pTitel) { | ||
boolean ergebnis = false; | boolean ergebnis = false; | ||
Zeile 187: | Zeile 112: | ||
return ergebnis; | return ergebnis; | ||
} | } | ||
</code> | </code> | ||
== Methode loeschen == | == Methode loeschen == | ||
<code> | <code> | ||
public void loeschen(Queue<Buch> pQueue, String pTitel) { | public void loeschen(Queue<Buch> pQueue, String pTitel) { | ||
Queue<Buch> hilfs = new Queue<Buch>(); | Queue<Buch> hilfs = new Queue<Buch>(); | ||
Zeile 206: | Zeile 131: | ||
} | } | ||
} | } | ||
</code> | </code> | ||
== Methode alphabetischErstes == | == Methode alphabetischErstes == | ||
<code> | <code> | ||
private Buch alphabetischErstes(Queue<Buch> pQueue) { | private Buch alphabetischErstes(Queue<Buch> pQueue) { | ||
Queue<Buch> hilfs = new Queue<Buch>(); | Queue<Buch> hilfs = new Queue<Buch>(); | ||
Zeile 230: | Zeile 155: | ||
return ergebnis; | return ergebnis; | ||
} | } | ||
</code> | </code> | ||
== Methode alphabetischRichtigEinfuegen == | == Methode alphabetischRichtigEinfuegen == | ||
<code> | <code> | ||
// '''Die Methode setzt voraus, dass pQueue schon alphabetisch sortiert und mit Strings gefüllt ist.''' | // '''Die Methode setzt voraus, dass pQueue schon alphabetisch sortiert und mit Strings gefüllt ist.''' | ||
private void alphabetischRichtigEinfuegen(Queue<String> pQueue, String pString) { | private void alphabetischRichtigEinfuegen(Queue<String> pQueue, String pString) { | ||
Zeile 252: | Zeile 177: | ||
} | } | ||
} | } | ||
</code> | </code> | ||
= Implementationsdiagramm = | |||
''Hier wird jetzt in einen <code>Queue</code> 'reingeschaut':''<br/> | |||
''Wie ist die Klasse <code>Queue</code> implementiert?''<br/> | |||
[[File:Implementationsdiagramm_Queue.png|thumb|Implementationsdiagramm Queue |628px]] | |||
* Die Queue ''hat'' zwei [[Node|Nodes]]: <code>front</code> und <code>last</code> (Wenn nur ein Node enthalten ist, ist dieser sowohl <code>front</code> als auch <code>last</code>). | |||
* Jeder der Nodes hat einen <code>content</code>; darin wird der eigentliche Inhalt gespeichert (z.B. ein Objekt vom Typ <code>Person</code> oder ein <code>String</code>). | |||
* Außerdem hat jeder [[Node|Node]] einen Verweis <code>next</code> auf den Nachfolgerknoten. | |||
= Implementierung = | |||
Für die Implementierung wird die Klasse '''[[Node]]''' verwendet, für die das Klassendiagramm rechts gilt. | |||
[[File:Klassendiagramm-Node.png|thumb|Klassendiagramm Node|322px]] | |||
<code> | |||
public class Queue<ContentType>{ | |||
private Node<ContentType> front; | |||
private Node<ContentType> last; | |||
/** | |||
* Eine leere Schlange wird erzeugt. | |||
* Objekte, die in dieser Schlange verwaltet werden, muessen vom Typ | |||
* ContentType sein. | |||
*/ | |||
public Queue() { | |||
front = null; | |||
last = 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 front == 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) { | |||
Node<ContentType> newNode = new Node<ContentType>(pContent); | |||
if (this.isEmpty()) { | |||
front = newNode; | |||
last = newNode; | |||
} else { | |||
last.setNext(newNode); | |||
last = newNode; | |||
} | |||
} | |||
} | |||
/** | |||
* Das erste Objekt wird aus der Schlange entfernt. | |||
* Falls die Schlange leer ist, wird sie nicht veraendert. | |||
*/ | |||
public void dequeue() { | |||
if (!this.isEmpty()) { | |||
front = front.getNext(); | |||
if (this.isEmpty()) { | |||
front = null; | |||
last = 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 front.getContent(); | |||
} | |||
} | |||
} | |||
</code> |
Aktuelle Version vom 23. Januar 2022, 16:46 Uhr
Fachbegriffe
Schlange (Queue), hinten anhängen (enqueue()), vorne entfernen (dequeue()), ist leer (isEmpty())
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 boolean isEmpty()
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 ContentType front()
Vorher: Die Schlange ist nicht leer.
Nachher: Die Anfrage liefert das vorderste Element der Schlange. Die Schlange ist unverändert.
Objektdiagramm einer Queue
Die Queue selbst hat nur die beiden Attribute front
und last
, 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 Nodes
untereinander verbunden sind (jeder Node
hat ein Attribut next
, in dem eine Referenz auf das darunter liegende Node
-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.
Veranschaulichung: enqueue(ContentType pContent)
Erläuterung: dequeue()
Verwendung von Queues
Die Verwendung von Queues wird hier aufgezeigt für Queues, die Objekte vom Typ Buch enthalten (vgl. Klassendiagramm rechts)
Vorsicht:
Wenn man einen Queue durchläuft, dann muss man die Inhalte auf einen Hilfs-Queue "retten" und am Ende wieder zurück auf den eigentlichen Queue übertragen!
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();
}
}
Implementationsdiagramm
Hier wird jetzt in einen Queue
'reingeschaut':
Wie ist die Klasse Queue
implementiert?
- Die Queue hat zwei Nodes:
front
undlast
(Wenn nur ein Node enthalten ist, ist dieser sowohlfront
als auchlast
). - 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
next
auf den Nachfolgerknoten.
Implementierung
Für die Implementierung wird die Klasse Node verwendet, für die das Klassendiagramm rechts gilt.
public class Queue<ContentType>{
private Node<ContentType> front;
private Node<ContentType> last;
/**
* Eine leere Schlange wird erzeugt.
* Objekte, die in dieser Schlange verwaltet werden, muessen vom Typ
* ContentType sein.
*/
public Queue() {
front = null;
last = 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 front == 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) {
Node<ContentType> newNode = new Node<ContentType>(pContent);
if (this.isEmpty()) {
front = newNode;
last = newNode;
} else {
last.setNext(newNode);
last = newNode;
}
}
}
/**
* Das erste Objekt wird aus der Schlange entfernt.
* Falls die Schlange leer ist, wird sie nicht veraendert.
*/
public void dequeue() {
if (!this.isEmpty()) {
front = front.getNext();
if (this.isEmpty()) {
front = null;
last = 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 front.getContent();
}
}
}