Eine Weiterentwicklung der Datenstruktur Stack ist die Datenstruktur Queue. Diese ist, wie der Name schon sagt, beispielsweise wie eine Schlange im Supermarkt aufgebaut. Das bedeutet, dass sie immer Elemente hinten angefügt bekommt, und immer nur das vorderste Element wieder aus der Queue gelöscht werden kann.
Das oberste Element wird dabei immer head, und das unterste immer tail genannt.
Methoden
isEmpty()
Die isEmpty() Methode ist die selbe Methode, wie bei dem Stack:
public boolean isEmpty() {
return head == null;
}enqueue()
Die enqueue() Methode fügt eine neue Node am Ende der Queue ein. Dabei muss zwischen zwei Fällen unterschieden werden.
- Die Queue ist leer
- Die Queue ist nicht leer
Sollte die Queue leer sein, so müssen sowohl head als auch tail neu gesetzt werden. Ist die Queue noch nicht leer, so muss nur tail auf die neue Node gesetzt werden. Die Node aus dem alten tail muss auf das neue tail (also die neue Node) zeigen.
public void enqueue(ContentType pContent) {
if (pContent != null) {
QueueNode temp = new QueueNode(pContent);
if (isEmpty()) {
tail = temp;
head = temp;
head.setNext(tail);
} else {
tail.setNext(temp);
tail = temp;
}
}
}dequeue()
Die dequeue() Methode entfernt das vorderste Element aus der Queue. Deshalb wird in dieser Methode der head auf die nach dem head kommende Node gesetzt. Natürlich kann nur ein Element aus der Queue entfernt werden, wenn überhaupt Elemente in der Queue vorhanden sind.
public void dequeue() {
if (head != null) {
head = head.nextNode;
}
}front()
Die front() Methode gibt den Inhalt des obersten Elementes der Queue wieder. Um eine NullPointerException zu vermeiden wird mit isEmpty() überprüft, ob der head vorhanden ist.
public ContentType front() {
if (!isEmpty()) return head.getContent();
else return null;
}Iterieren über die Queue
Bei der Queue gibt es zwei mögliche Wege, wie man über alle Elemente iterieren kann.
- Man erzeugt eine temporäre Queue, in die alle Elemente aus der Queue eingefügt werden. Dabei werden die Elemente aus der Queue gelöscht.
Queue<String> temp = new Queue<String>();
while(!queue.isEmpty()){
temp.enqueue(queue.front());
queue.dequeue();
size++;
}
// Elemente werden wieder in die alte Queue eingefügt
while(!temp.isEmpty()){
queue.enqueue(temp.front());
temp.dequeue();
}- Man merkt sich das oberste Element in einer temporären Variable. Dannach fügt man solange wieder das oberste Element an das Ende der Queue an, bis man wieder bei dem Element der temporären Variable angelangt ist.
top = queue.front();
queue.enqueue(queue.front());
queue.dequeue();
while(queue.front() != top){
playlist.enqueue(playlist.front());
playlist.dequeue();
}Anwendungsbeispiel
Musikplayer
Bei dem Musikplayer ist es dem Benutzer möglich, einen Song in seine Playlist anzufügen. Die Lieder werden dabei der Reihe nach abgespielt und dann wieder hinten angefügt. Für die Umsetzung benutzen wir eine Queue, die die Playlist speichert, sowie eine Variable aktuell, die das aktuell gespielte Lied speichert. Sowohl die Nodes in der Queue, als auch das aktuelle Lied sind ein Lied Objekt.
Um nun ein neues Lied in die Playlist einzufügen, wird die Methode hinzufuegen() verwendet. In dieser wird dann die enqueue() Methode für die playlist aufgerufen.
public void hinzufuegen(String mp3Name) {
try {
MP3File mp3 = new MP3File(mp3Name);
AbstractID3v2 tags = mp3.getID3v2Tag();
playlist.enqueue(new Lied(tags.getSongTitle(), tags.getLeadArtist(), mp3Name));
} catch (Exception e) {
}
}Soll nun ein Lied abgespielt werden, so wird die Methode abspielen() aufgerufen. Sie speichert das oberste Element aus playlist in aktuell. Das oberste Element in der Queue wird nun nach unten verschoben. Mit dem Lied aus aktuell wird dann anschließend die Wiedergabe gestartet.
public void abspielen() {
playlist.enqueue(playlist.front());
aktuell = playlist.front();
playlist.dequeue();
this.start();
}Da der Benutzer auch eine Übersicht über die gespielten Titel haben möchte, wird die Methode anzeigen() benötigt. Sie iteriert über die Queue und fügt jeden Titel eines Liedes an eine String Variable an. Diese Variable wird dann zurückgegeben.
public String anzeigen() {
Lied top = playlist.front();
String rueckgabe = top.getTitel();
playlist.enqueue(playlist.front());
playlist.dequeue();
while(!(playlist.front() == top)){
rueckgabe += "\n"+ playlist.front().getTitel();
playlist.enqueue(playlist.front());
playlist.dequeue();
}
return rueckgabe;Priority Queue
Bei der Priority Queue handelt es sich um eine Weiterentwicklung der Queue. Wir fügen jeder Node noch zusätzlich zu ihrem Content noch eine Priorität hinzu. Diese Priorität bestimmt dann, an welcher Stelle in der Queue die Node eingefügt wird.
Sowohl die Queue, als auch die Node muss deshalb angepasst werden. Bei der Node fügen wir noch das Attribut prio ein, welches auch seine eigene get-Methode bekommt.
In der Queueklasse muss dann noch die enqueue() Methode angepasst werden. Auch hierbei muss man wieder zwischen verschiedenen Fällen unterscheiden.
- Die Queue beinhaltet noch gar kein Element. Dann wird, wie bei der normalen Queue auch head und tail auf die selbe Node gesetzt.
- Die neue Node muss am Ende einsortiert werden.
- Die neue Node muss am Anfang einsortiert werden.
- Die neue Node muss innerhalb der Queue einsortiert werden, außer eine der oben beschriebenen Situationen (1-3) tritt ein.
public void enqueue(ContentType pContent, int prio) {
if (pContent != null) {
if (prio < 0) prio = 0;
PriorityNode newNode = new PriorityNode(pContent, prio);
PriorityNode top = head;
if (isEmpty()) { //kein Element in der Queue vorhanden
head = newNode;
tail = head;
} else if (newNode.getPrio() <= tail.getPrio()) { //newNode muss am Ende einsortiert werden
tail.setNext(newNode);
tail = newNode;
} else if (newNode.getPrio() > head.getPrio()) { //newNode muss am Anfang einsortiert werden
newNode.setNext(head);
head = newNode;
} else { //alle anderen Fälle
PriorityNode temp = head;
while (temp.getNext().getPrio() >= prio) temp = temp.getNext();
newNode.setNext(temp.getNext());
temp.setNext(newNode);
}
}
}Außerdem bekommt die Queue noch eine Methode, die die Priorität des obersten Elementes zurückgibt. Sollte dabei die PriorityQueue leer sein, so wird -1 zurückgegeben.
public int frontPriority(){
if (this.isEmpty()) return -1;
else return head.getPrio();
}Anwendungsbeispiel
Musiplayer mit Prioritäten
Die Priority Queue kann nun zur Erweiterung des Musiplayers verwendet werden. Dabei kann der Benutzer für jedes Lied, dass er hinzufügt eine Priorität angeben. Abhängig von dieser Priorität wird das Lied dann in die Playlist einsortiert. Wurde das Lied dann einmal gespielt wird seine Priorität dekrementiert und wieder in die Playlist eingefügt.
Für die Implementierung muss nun nur überall die enqueue() Methode angepasst werden, da diese nun als zweiten Parameter noch die jeweilige Priorität übergeben bekommt.
playlist.enqueue(new Lied(tags.getSongTitle(), tags.getLeadArtist(), mp3Name), prio);