Schlange

Einführung

In der Informatik bezeichnet eine Warteschlange oder Schlange (englisch Queue) eine grundlegende und häufig eingesetzte dynamische Datenstruktur. Sie dient der geordneten Zwischenspeicherung von Datenobjekten, bevor diese systematisch weiterverarbeitet werden.

Warteschlangen verwalten beliebige Objekte nach dem strengen FIFO-Prinzip (First-In-First-Out). Das bedeutet: Das Element, welches zuerst in die Datenstruktur eingefügt wurde, wird auch als erstes wieder entnommen.

Alltagsanalogie: Man kann sich diese Datenstruktur wie eine Warteschlange von Kunden an einer Supermarktkasse vorstellen. Der Letzte, der sich in die Schlange stellt, wird am Kopfende (Back) als Letzter bedient. Umgekehrt wird derjenige, der sich als Erstes an die Spitze (Front) angestellt hat, als Erster bedient.

Funktionsweise und Visualisierung

Die grundlegenden Operationen einer Warteschlange verändern ihren Zustand, indem Elemente eingefügt oder entnommen werden. In der Abbildung unten ist die Funktionsweise schematisch dargestellt:

• Mit enter (bzw. enqueue) wird ein neuer Wert (im Beispiel die Zahl 3) am Ende der Schlange (Back) hinzugefügt.
• Mit leave (bzw. dequeue) wird das am längsten gespeicherte Element (im Beispiel 37) an der Spitze der Schlange (Front) herausgenommen.
• Der einzige lesende Zugriff erfolgt über die Operation front. Diese liefert das erste gespeicherte Element der Queue (hier 37), unter der Annahme, dass die entnehmende Operation noch nicht ausgeführt wurde.

Auch vertikal lässt sich das Konzept einer Queue anhand von Elementblöcken veranschaulichen. Hierbei rücken die Elemente wie auf einem Fließband weiter:

Aufbau und Spezifikation (API)

Im Kontext der objektorientierten Programmierung wird die abstrakte Datenstruktur (ADT) formal über eine wohldefinierte Schnittstelle abgebildet. Eine Queue sollte über die folgenden Methoden und Konstruktoren verfügen:

Konstruktor

• Queue()
  • Eine leere Schlange wird erzeugt. Der Zustand der initialisierten Schlange ist leer.

Methoden

• boolean isEmpty()
  • Die Anfrage liefert den Wert true, wenn die Schlange keine Objekte enthält. Andernfalls liefert sie false.
• void enqueue(Object pObject)
  • Das Objekt pObject wird an die Schlange (hinten) angehängt. Falls pObject gleich null ist, bleibt die Schlange unverändert.
• void dequeue()
  • Das erste Objekt (vorne) wird aus der Schlange entfernt. Falls die Schlange bereits leer ist, wird sie nicht verändert.
• Object front()
  • Die Anfrage liefert das erste Objekt der Schlange zurück, ohne dieses aus der Schlange zu entfernen (die Schlange bleibt unverändert). Falls die Schlange leer ist, wird null zurückgegeben.

Laufzeitanalyse (Komplexität)

Warteschlangen lassen sich in der Praxis äußerst effizient über Arrays mit Ringpuffer-Logik oder über einfach verkettete Listen implementieren. Eine Zeigerstruktur, die stets den Anfang (Front) und das Ende (Tail) speichert, garantiert hochperformante Speicher- und Lesezugriffe. Für die oben genannten Methoden ergibt sich gemäß der O-Notation folgende Laufzeitkomplexität:

Operation	1. Best-Case	2. Average-Case	3. Worst-Case
enqueue(Object pObject)	[math]\displaystyle{ \mathcal{O}(1) }[/math]	[math]\displaystyle{ \mathcal{O}(1) }[/math]	[math]\displaystyle{ \mathcal{O}(1) }[/math]
dequeue()	[math]\displaystyle{ \mathcal{O}(1) }[/math]	[math]\displaystyle{ \mathcal{O}(1) }[/math]	[math]\displaystyle{ \mathcal{O}(1) }[/math]
front()	[math]\displaystyle{ \mathcal{O}(1) }[/math]	[math]\displaystyle{ \mathcal{O}(1) }[/math]	[math]\displaystyle{ \mathcal{O}(1) }[/math]
isEmpty()	[math]\displaystyle{ \mathcal{O}(1) }[/math]	[math]\displaystyle{ \mathcal{O}(1) }[/math]	[math]\displaystyle{ \mathcal{O}(1) }[/math]

Implementierungsbeispiel (Java)

Die grundlegende Struktur einer objektorientierten Implementierung als Rumpf-Klasse orientiert sich exakt an den curricularen Vorgaben.

public class Queue {
    
    // Verweise auf den Anfang und das Ende der Queue
    private Node head;
    private Node tail;

    // Innere Knoten-Klasse für verkettete Listenstruktur
    private class Node {
        Object content;
        Node nextNode;

        public Node(Object pContent) {
            content = pContent;
            nextNode = null;
        }
    }

    /**
     * Konstruktor: Eine leere Schlange wird erzeugt.
     */
    public Queue() {
        head = null;
        tail = null;
    }

    /**
     * Prüft, ob die Schlange leer ist.
     */
    public boolean isEmpty() {
        return head == null;
    }

    /**
     * Fügt ein Objekt hinten an die Schlange an.
     */
    public void enqueue(Object pObject) {
        if (pObject != null) {
            Node newNode = new Node(pObject);
            if (this.isEmpty()) {
                head = newNode;
                tail = newNode;
            } else {
                tail.nextNode = newNode;
                tail = newNode;
            }
        }
    }

    /**
     * Entfernt das vorderste Element aus der Schlange.
     */
    public void dequeue() {
        if (!this.isEmpty()) {
            head = head.nextNode;
            if (this.isEmpty()) {
                tail = null;
            }
        }
    }

    /**
     * Gibt das vorderste Element zurück.
     */
    public Object front() {
        if (this.isEmpty()) {
            return null;
        } else {
            return head.content;
        }
    }
}