Queue neu: Unterschied zwischen den Versionen

Aus SibiWiki
Zur Navigation springen Zur Suche springen
(Die Seite wurde neu angelegt: „Kategorie:Informatik Kategorie:Informatik-Q1 Kategorie:Informatik-Abitur Kategorie:Datenstrukturen(IF) = Funktionsweise = Die Datenstruktur Sch…“)
 
(Die Seite wurde geleert.)
 
(Eine dazwischenliegende Version desselben Benutzers wird nicht angezeigt)
Zeile 1: Zeile 1:
[[Kategorie:Informatik]]
[[Kategorie:Informatik-Q1]]
[[Kategorie:Informatik-Abitur]]
[[Kategorie:Datenstrukturen(IF)]]
= 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) =
[[Medium:Queue-Schnittstelle-Zentralabitur-2012.pdf|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 eines Queue =
[[Datei:QueueNodes.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)====
[[Datei:Enqueue_Java.gif|border]]
====Erläuterung: dequeue()====
[[Datei:DequeueJava.gif|border]]
= Implementationsdiagramm =
[[File:Implementationsdiagramm-Queue.png|thumb|Implementationsdiagramm Queue |628px]]
* Die Queue ''hat'' zwei [[Node|Nodes]]: <code>front</code> und <code>last</code>
* Jeder der Nodes hat einen <code>value</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]] einen Verweis <code>next</code> auf den Nachfolgerknoten.
= Implementierung =
Für die Implementierung wird die Klasse [[Node]] verwendet.
<code>
public class Queue<ContentType>{
    private Node<ContentType> frontNode;
    private Node<ContentType> lastNode;
 
    public Queue<ContentType>(){
    }
    public boolean isEmpty(){
        return (frontNode == null);
    }
    public ContentType front(){
        return frontNode.getValue();
    }
    public void enqueue(ContentType pObject){
        Node<ContentType> newNode = new Node<ContentType>(pObject);
        if(frontNode == null){
            frontNode = newNode;
            lastNode = newNode;
        }
        else{
            lastNode.setNext(newNode);
            lastNode = newNode;
        }
    }
    public void dequeue(){
        frontNode = frontNode.getNext();
        if(frontNode == null){
            lastNode = null;
        }
    }
}
</code>
= Verwendung von Queues =
[[Datei:Klassendiagramm_Buch.png|405px|thumb|right|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 ==
<code>
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;
}
</code>
== Methode enthaelt==
<code>
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;
}
</code>
== Methode loeschen ==
<code>
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();
    }
}
</code>
== Methode alphabetischErstes ==
<code>
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;
}
</code>
== Methode alphabetischRichtigEinfuegen ==
<code>
  // '''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();
    }
}
</code>

Aktuelle Version vom 2. September 2015, 20:40 Uhr

Abgerufen von „https://sibiwiki.de/wiki/index.php?title=Queue_neu&oldid=1989“