Warteschlange (Datenstruktur)

In der Informatik bezeichnet eine Warteschlange (englisch queue [kju]) eine häufig eingesetzte Datenstruktur. Sie dient als Puffer zur Zwischenspeicherung von Objekten in einer Reihenfolge, bevor diese weiterverarbeitet werden.

Funktionsprinzip

Eine Warteschlange kann, im Gegensatz zum später beschriebenen Ringpuffer, 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 Objekts und
• dequeue zum Zurückholen und Entfernen eines Objektes bereit.

Während die Warteschlange theoretisch unendlich viele Objekte aufnehmen kann, kann beim Ringpuffer bei Erschöpfung ein Überlauf eintreten, für den eine Bearbeitung vereinbart werden muss (siehe Abschnitt Implementierung als Ringpuffer).

Dabei wird nach dem Prinzip First In – First Out (kurz FIFO, wörtlich zuerst hinein – zuerst heraus) gearbeitet, das heißt, es wird von dequeue immer das Objekt aus der Warteschlange zurückgegeben, welches von den in der Warteschlange noch vorhandenen Objekten als erstes mit enqueue hineingelegt wurde.

Illustration

Man kann sich eine Warteschlange wie eine Warteschlange von Kunden an einer Kasse vorstellen. Der Letzte, der sich in die Schlange stellt, wird auch als letzter bedient. Umgekehrt wird derjenige, der sich als erstes angestellt hat, als erster bedient.

Mit enter wird ein neuer Wert (3) der Schlange hinzugefügt, und mit leave das am längsten gespeicherte Element (37) herausgenommen. Der einzige lesende Zugriff erfolgt mit front $\to$ und liefert das erste gespeicherte Element der Queue (hier im Beispiel 37, natürlich unter der Annahme, dass die Operation leave noch nicht ausgeführt wurde!).

Anwendung

Die zur Interprozesskommunikation verwendete Pipe ist eine der wichtigsten Anwendungen für Warteschlangen.

Durch Warteschlangen werden auch langsame externe Geräte, z. B. Drucker, von der Programmabarbeitung entkoppelt. Nach dem Einstellen eines Druckauftrages in die Warteschlange wird dem Programm der Auftrag als „gedruckt“ signalisiert, tatsächlich wird der Auftrag jedoch erst später bei Verfügbarkeit des Gerätes ausgeführt.

Warteschlangen werden außerdem häufig zur Datenübergabe zwischen asynchronen Prozessen in verteilten Systemen verwendet, wenn also Daten vor ihrer Weiterverarbeitung gepuffert werden müssen. Der Zugriff erfolgt dabei durch im Betriebssystem verankerte APIs. Die Größe der Warteschlange wird durch das Betriebssystem limitiert.

Graphische Benutzeroberflächen puffern Ereignisse der Maus und Tastatur in einer sogenannten Message Queue nach dem FIFO-Prinzip, d. h. in der Reihenfolge ihres Auftretens. Anschließend leiten sie diese dann, abhängig von Position und Eingabefokus, an die korrekten Prozesse weiter.

Eine Warteschlange kann auch für Parallele Programmierung verwendet werden. Dies kann man sich wie in einer Behörde vorstellen, bei dem es mehrere Schalter für eine Warteschlange gibt. So können Aufgaben eingestellt werden, die später parallel abgearbeitet werden.

Implementierung als Ringpuffer

Ringpuffer mit In-Pointer und Out-Pointer. Ungelesene Elemente sind grün, gelesene orange und geleerte grau dargestellt. Angezeigt ist auch die Richtung, in die der Puffer gefüllt wird.

→ Hauptartikel: Ringpuffer

Warteschlangen sind häufig als Ringpuffer mit je einem Zeiger auf das Ende (In-Pointer) und den Anfang (Out-Pointer) der Warteschlange implementiert. Die Besonderheit des Ringpuffers ist, dass er eine feste Größe besitzt. Dabei zeigt der In-Pointer auf das erste freie Element im Array, das den Ringpuffer repräsentiert, und der Out-Pointer auf das erste belegte Element in dem Array. Im Unterschied zum Array werden die ältesten Inhalte überschrieben, wenn der Puffer voll ist, um weitere Elemente in den Ringpuffer ablegen zu können. Eine Implementierung des Ringpuffers sollte für den Fall, dass der Ringpuffer voll ist, entweder einen Pufferüberlauf signalisieren oder zusätzlichen Speicherplatz bereitstellen. In anderen Fällen kann das Überschreiben alter Elemente der Warteschlange und damit der Datenverlust gewollt sein.

Zusammenhang mit Stapelspeichern (Stacks)

Warteschlangen kann man sich als Bücherstapel vorstellen, die von unten befüllt werden. Dementsprechend gibt es Implementierungen, die gar keinen prinzipiellen Unterschied zwischen Stacks und Queues machen. In REXX steht das Leseende einer Queue fest. Mit PUSH abgelegte Einträge werden nach dem LIFO-Prinzip gelesen (Last In – First Out), mit QUEUE abgelegte nach dem FIFO-Prinzip. Zur Interprozesskommunikation sind insbesondere Queues interessant.

Programmierung

C++

Das folgende Beispiel in der Programmiersprache C++ mit Spielkarten zeigt die Verwendung einer Warteschlange der Klasse queue der C++-Standardbibliothek (siehe auch Template (C++) - Klassen-Templates). Bei der Ausführung des Programms wird die Methode main verwendet.

#include <queue> // Bindet den Datentyp queue in das Programm ein
#include <iostream>

int main()
{
   using namespace std;
   queue<string> myQueue; // Deklariert eine Queue mit dem Elementtyp string

   // Fügt der Queue 3 Elemente vom Typ string hinzu.
   myQueue.push("Herz Dame");
   myQueue.push("Karo König");
   myQueue.push("Kreuz Ass");

   queue<string>::size_type n;
   n = myQueue.size(); // Weist die Anzahl der Elemente der Variablen n zu
   cout << "Die Länge der Queue ist "
        << n << "." << endl; // Ausgabe auf der Konsole
		
   string card = myQueue.front(); // Weist das Element am Anfang ("Herz Dame") der Variablen card zu
   cout << "Die Karte am Anfang der Queue ist: "
        << card << "." << endl; // Ausgabe auf der Konsole
		
   myQueue.pop(); // Entfernt das Element am Anfang

   n = myQueue.size(); // Weist die Anzahl der Elemente der Variablen n zu
   cout << "Nach dem Löschen der Karte ist die Länge "
        << n << "." << endl; // Ausgabe auf der Konsole
		
   card = myQueue.front(); // Weist das Element am Anfang ("Karo König") der Variablen card zu
   cout << "Nach dem Löschen ist die Karte am Anfang der Queue: "
        << card << "." << endl; // Ausgabe auf der Konsole
}

Eine mögliche Implementierung einer Warteschlange als einfach verkettete Liste wäre Folgende:

#ifndef __QUEUE_HPP__
#define __QUEUE_HPP__

template <typename T>
class Queue {

    private:
        
        struct Element {
            T value;
            Element* next = nullptr;

            Element(const T& v) : value(v) {
            }
        };

        Element* head = nullptr;
        Element* tail = nullptr;

        unsigned int numberOfElements = 0;

        void clear() {
            while (!empty()) {
                pop();
            }
        }

        void copy(const Queue& arg) {
            Element* ptr = arg.head;

            while (ptr != nullptr) {
                push(ptr->value);
                ptr = ptr->next;
            }
        }

    public:

        Queue() = default;

        Queue(const Queue& arg) {
            copy(arg);
        }

        Queue& operator=(const Queue& arg) {
            clear();
            copy(arg);
            return *this;
        }

        ~Queue() {
            clear();
        }
        
        void push(const T& arg) {
            if (empty()) {

                // Nachdem das erste Element eingefügt wurde, ist das vorderste
                // Element gleich das hinterste Element
                head = tail = new Element(arg);

            } else {

                // Das neue Element wird am Ende der Warteschlange eingefügt
                // und wird zum hintersten Element
                tail->next = new Element(arg);
                tail = tail->next;

            }

            ++numberOfElements;
        }

        void pop() {

            // Falls das vorderste Element gleich das hinterste Element ist
            // befindet sich nur noch ein Element in der Warteschlange
            if (head == tail) {

                delete head;
                head = tail = nullptr;
                numberOfElements = 0;

            } else {

                // Das vorderste Element wird entfernt und das zweitvorderste
                // Element wird zum vordersten Element
                Element* tmp = head;
                head = head->next;
                delete tmp;
                --numberOfElements;
            }

        }

        T front() const {
            return head->value;
        }

        bool empty() const {
            return head == nullptr;
        }

        unsigned int size() const {
            return numberOfElements;
        }

};

#endif

C#

Das folgende Beispiel in der Programmiersprache C# zeigt die Implementierung einer Warteschlange in der Klasse Queue und die Verwendung dieser Klasse in einer Hauptklasse. Die Klasse Queue enthält eine doppelt verkettete Liste, die in diesem Beispiel ein generischer Typ mit einem Typparameter ist.

// Deklariert die Klasse Queue mit Typparameter T, die mit einer doppelt verketteten Liste implementiert ist.
public class Queue<T>
{
	// Initialisiert die doppelt verkettete Liste der Queue
	private readonly System.Collections.Generic.LinkedList<T> list = new System.Collections.Generic.LinkedList<T>();
	
	// Gibt die Anzahl der Elemente zurück
	public int Count()
	{
		return list.Count;
	}
	
	// Fügt ein Element am Ende ein
	public void Enqueue(T element)
	{
		list.AddLast(element);
	}
	
	// Löscht das Element am Anfang und gibt es zurück
	public T Dequeue()
	{
		T first = list.First.Value;
		list.RemoveFirst();
		return first;
	}
	
	// Gibt die Queue als Text zurück
	public String ToString()
	{
		return list.ToString();
	}
}

Die Hauptklasse Program mit der Methode Main ist entsprechend wie das Code-Beispiel in C++ (siehe oben) implementiert:

class Program
{
	public static void Main(string[] args)
	{
		Queue<string> myQueue = new Queue<string>();
		myQueue.Enqueue("Herz Dame");
		myQueue.Enqueue("Karo König");
		myQueue.Enqueue("Kreuz Ass");
		
		int n = myQueue.Count();
		Console.WriteLine("Die Länge der Queue ist " + n);
		
		string card = myQueue.Dequeue();
		Console.WriteLine("Die Karte am Anfang der Queue ist: " + card);
		
		n = myQueue.Count();
		Console.WriteLine("Nach dem Löschen der Karte ist die Länge " + n);
		
		card = myQueue.Dequeue();
		Console.WriteLine("Nach dem Löschen ist die Karte am Anfang der Queue: " + card);
		
		Console.ReadLine();
	}
}

Für die Programmierung von Kartenspielen und Gesellschaftsspielen mit Stapeln, bei denen während des Spiels Karten auf einen Stapel gelegt oder von einem Stapel gezogen wird, sind stattdessen Stacks geeignet (siehe Stapelspeicher - Beispiel mit Spielkarten).

Siehe auch

• Datenstruktur
• Deque
• Last In – First Out
• Puffer
• Pipe (Informatik)
• Stapelspeicher
• Warteschlange
• Warteschlangentheorie

Weblinks

www.geeksforgeeks.org: Array implementation of queue (Simple)