ADT Schlange

Ein Keller ermöglicht direkten Zugriff auf das jeweils zuletzt gespeicherte Element. Für manche Anwendungen ist es praktischer, direkten Zugriff auf das zuerst gespeicherte Element zu haben (FIFO = first in / first out - Speicher). Ein linearer abstrakter Datentyp, der dies leistet, heißt Schlange (engl. queue).

Während man sich einen Keller als eine vertikal angeordnete Speicherkette vorstellt (Elemente werden übereinander gespeichert), hilft bei einer Schlange die Vorstellung von einer horizontalen Anordnung der Elemente (Elemente werden hintereinander gespeichert). In einer Schlange stellt man sich hinten an, und wird vorne bedient.

public interface Schlange {

  public void enq(Object x); // Fuegt x hinten ein

  public void deq(); // Entfernt vorderstes Element

  public Object front(); // Liefert vorderstes Element

  public boolean empty(); // Testet, ob Schlange leer ist

}

Schlange.java

Das ADT Schlange soll hier auf Grundlage des ZeigerKellers implementiert werden. Den Anfang der Schlange merkt man sich in der globalen Klassenvariable head (entspricht top beim Keller). Die Methoden deq (von engl. dequeue - aus einer Warteschlange entfernen), front und empty wirken auf den Anfang der Schlange und entsprechen somit den ZeigerKeller-Operationen pop, top und empty. Die Operation enq (von engl. enqueue - einreihen) wirkt auf das (hintere) Ende der Schlange und muss neu formliert werden. Damit man zum Einfügen eines Elementes nicht jedes Mal die gesamte Speicherkette von vorne nach hinten durchgehen muss, ist es sinnvoll, sich in einer weiteren Klassenvariable tail (engl. Schwanz) ihr hinteres Ende zu merken.

public class ZeigerSchlange implements Schlange {

  private class SchlangenEintrag { // innere Klasse
    Object inhalt; // Inhalt des SchlangenEintrags
    SchlangenEintrag next; // Verweis auf naechsten SchlangenEintrag
  }

  private SchlangenEintrag head; // zeigt auf das erste Element
  private SchlangenEintrag tail; // zeigt auf das letzte Element

  public ZeigerSchlange(){
    head = null;
    tail = null;
  }

  public void enq(Object x) {
    SchlangenEintrag hilf = new SchlangenEintrag();
    hilf.inhalt = x;

    if(empty()){
      head = hilf;
    }
    else{
      tail.next = hilf;
    }
    tail = hilf;
  }

  public void deq() {
    head = head.next;
  }

  public Object front() {
    return head.inhalt;
  }

  public boolean empty() {
    return head==null;
  }

}

ZeigerSchlange.java

Anmerkung zum Einfügen:

Hier müssen zwei Fälle unterschieden werden:

1. die Schlange ist noch leer: Nach dem Einfügen müssen sowohl head als auch tail auf das neu eingefügte, einzige Element der Schlange verweisen.
2. die Schlange ist nicht leer: head braucht nicht verändert zu werden, aber das neue Element muss an das Ende der Schlange (tail.next) gehängt werden.

» drucken: pdf | html