Queue

aus ZUM-Wiki, dem Wiki für Lehr- und Lerninhalte auf ZUM.de

Wechseln zu: Navigation, Suche
Kurzinfo
Links
 Dieser Artikel gehört zum Thema Programmieren in Java.
Bildbeschreibung
 Diese Seite enthält Unterrichtsideen, die du ausprobieren oder hier diskutieren kannst.
Links
 Dieser Artikel beinhaltet eine Linksammlung für den Unterricht.
In der Informatik bezeichnet eine Warteschlange (engl. Queue) eine häufig eingesetzte spezielle Datenstruktur.

Eine Warteschlange kann eine beliebige Menge von Objekten aufnehmen und gibt diese in der Reihenfolge ihres Einfügens wieder zurück. Dazu stellen Warteschlangen die Operationen

  • enqueue zum Hinzufügen eines Objekt und
  • dequeue zum Zurückholen und Entfernen eines Objektes

Dabei wird nach dem First In – First Out-Prinzip (deutsch zuerst hinein – zuerst hinaus, kurz FIFO) gearbeitet, das heißt, es wird von dequeue immer das Objekt aus der Warteschlange zurückgegeben, welches als erstes mit enqueue hineingelegt wurde."

W-Logo.gif Warteschlange (Datenstruktur), Wikipedia – Die freie Enzyklopädie, 06.12.2005 - Der Text ist unter der Lizenz „Creative Commons Attribution/Share Alike“ verfügbar; zusätzliche Bedingungen können anwendbar sein. Siehe die Nutzungsbedingungen für Einzelheiten. In der Wikipedia ist eine Liste der Autoren verfügbar.

Schlange und Beispiel Postschalter.png
California on a Saturday afternoon
Hand.gif   Ãœbung
  1. Analysieren Sie das Klassendiagramm und den Quelltext zu Schlange.
  2. Das Bild rechts zeigt einen Stau. Vergleichen Sie einen Stau mit dem Datentypen Schlange.

Vorgegeben ist eine Schlange mit den Grundmethoden. Ergänzen Sie die folgenden Methoden:

  1. laenge() - Ermitteln Sie die Länge der Schlange (Zusatzaufgabe: Durchschnitt)
  2. uebertragen (Schlange schlange1) - Ãœbertragen Sie alle Elemente von einer Schlange zu einer anderen.
  3. ausgabeOhneLoeschen() - Schreiben Sie eine Ausgabe, die die ursprüngliche Schlange beibehält (Tipp: hin und her schieben mit Hilfe einer "lokalen" Schlange - oder lokale Variablen verwenden).
  4. verdoppeln() - Verdoppeln Sie die Länge der Schlange (durch beliebige Elemente)
  5. laengstesElement() - Lassen Sie das von der Zeichenzahl längste Element (bei Zahlen: größte) innerhalb einer Schlange suchen.

Inhaltsverzeichnis

Die Datenstruktur Queue nach den Zentralabiturvorgaben NRW - Eine mögliche Implementierung

Mit Hilfe des Datentypen List aus den Zentralabivorgaben (vgl. Java/List)) lässt sich die Schlange so implementieren. 

public class Queue
{
// Eigenschaften
List liste;
 
// Konstruktor
    public Queue()
    {
        liste = new List();
    }
 
// Methoden
    public boolean isEmpty(){
        return liste.isEmpty();   
    }
 
    public void enqueue(Object pObject){
        liste.toLast();
        liste.insertBehind(pObject);
    }    
 
    public void dequeu() {
        liste.toFirst();
        liste.delete();
    }
 
    public Object front() {
        liste.toFirst();
        return liste.getItem();
    }   
} // Ende von Queue

Testprogramm

public class Postschalter
{
// Eigenschaften
Queue schlange;
 
// Konstruktor
    public Postschalter()
    {
    schlange = new Queue();
    schlange.enqueue ("Herr Meier");
    schlange.enqueue ("Frau Müller");
    schlange.enqueue ("Ilse");
    schlange.enqueue ("Frau Gans");
    }
 
// Methoden
 
    public void bediene()
    {
        if (!schlange.isEmpty()){
            System.out.println("Guten Tag, "+schlange.front());
            System.out.println("Auf Wiedersehen, "+schlange.front());
            schlange.dequeu();
            if (!schlange.isEmpty()) {
                System.out.println("Der nächste ist "+schlange.front());
            }
            else {
                System.out.println("Puh, endlich ist die Schlange abgearbeitet.");
            }
        }
        else {
            System.out.println("Kein Kunde da, den ich bedienen kann");   
        }
    }
} // Ende von Postschalter

Zahlenschlange

public class Zahlenschlange
{
// Eigenschaften
Queue schlange;
 
// Konstruktor
    public Zahlenschlange()
    {
        schlange = new Queue();
        schlange.enqueue (3);
        schlange.enqueue (6);
        schlange.enqueue (1);
        schlange.enqueue (4);   
    }
 
// Methoden
 
    // beispielMethode ist ein Beispiel für den Aufbau einer Methode
    public void verdoppeleErstesElementUndHaengeEsHintenAn()
    {   
        int zwischenspeicher;
        if (!schlange.isEmpty()){
            zwischenspeicher = 2 * (Integer) schlange.front();
            schlange.dequeu();
            schlange.enqueue (zwischenspeicher);
        }
    }
 
    public void ausgeben()
    {   
        Queue zwischenspeicher=new Queue();
        while (!schlange.isEmpty()){
            System.out.println(schlange.front());
            zwischenspeicher.enqueue(schlange.front());
            schlange.dequeu();
        }
        while (!zwischenspeicher.isEmpty()){
            schlange.enqueue(zwischenspeicher.front());
            zwischenspeicher.dequeu();
        }        
 
    }    
 
} // Ende von Zahlenschlange

Quelltext in Java auf Grundlage eines Vectors

KlassendiagrammSchlange.png 

 import java.util.Vector;
 
 public class Schlange
 // Diese Schlange arbeitet mit Vector
 // Didaktische Reduktion:
 // Als Daten werden nur Strings gespeichert
 {
  public Vector schlange;
 
  public Schlange()
  {
    schlange = new Vector();
  }
 
  public boolean empty()
  {
    // prüft, ob die Schlange leer ist
    return schlange.isEmpty();
  }
 
  public String front()
  {
    // gibt den Wert des ersten Elements
    return (String) schlange.elementAt(0);
  }
 
  public void enq(String txt)
  {
    // hängt ein Element an
    schlange.add(txt);
  }
 
  public String deq()
  {
    // entfernt das erste Element und gibt es zurück
    String s = front();
    schlange.remove(0);
    return  s;
  }
 
 }

Weblinks

Siehe auch

Von „http://wiki.zum.de/Java/Queue“