Queue: Unterschied zwischen den Versionen

Aus SibiWiki
Zur Navigation springen Zur Suche springen
 
(19 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(): boolean'''
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(): ContentType'''
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:Klassendiagramm_QueueNode.png|300px|thumb|right|Klassendiagramm der Klasse QueueNode]]


[[Datei:Queue_ab_Abi2017.png]]
[[Datei:Queue.png]]


Die Queue selbst hat nur die beiden Attribute <code>'''head'''</code> und <code>'''tail'''</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>[[QueueNode|QueueNodes]]</code> untereinander verbunden sind (jeder <code>[[QueueNode]]</code> hat ein Attribut <code>nextNode</code>, in dem eine Referenz auf das darunter liegende <code>QueueNode</code>-Objekt gespeichert ist).
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.
   
   
(In der Animation heißen die beiden Attribute der Klasse <code>Queue</code> ''front'' und ''last'' (statt ''head'' und ''tail'' wie in der Abi-Schnittstelle).)


====Veranschaulichung: enqueue(ContentType pContent)====
====Veranschaulichung: enqueue(ContentType pContent)====
Zeile 58: Zeile 63:
====Erläuterung: dequeue()====
====Erläuterung: dequeue()====
[[Datei:DequeueJava.gif|border]]
[[Datei:DequeueJava.gif|border]]
= Implementationsdiagramm =
[[File:Implementationsdiagramm-Queue.png|thumb|Implementationsdiagramm Queue |628px]]
* Die Queue ''hat'' zwei [[QueueNode|Nodes]]: <code>head</code> und <code>tail</code> (Wenn nur ein Node enthalten ist, ist dieser sowohl <code>head</code> als auch <code>tail</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 [[QueueNode|Node]] einen Verweis <code>nextNode</code> auf den Nachfolgerknoten.
= Implementierung =
Für die Implementierung wird die Klasse [[QueueNode]] verwendet.
<code>
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();
      }
  }
}
</code>


= Verwendung von Queues =
= Verwendung von Queues =
Zeile 150: 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 168: 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 190: 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 209: 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 233: 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 255: 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

Queue.png

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)

Enqueue Java.gif

Erläuterung: dequeue()

DequeueJava.gif

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)

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?

Implementationsdiagramm Queue
  • Die Queue hat zwei Nodes: front und last (Wenn nur ein Node enthalten ist, ist dieser sowohl front als auch last).
  • 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 next auf den Nachfolgerknoten.

Implementierung

Für die Implementierung wird die Klasse Node verwendet, für die das Klassendiagramm rechts gilt.

Klassendiagramm Node

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