WikiDer > Warteschlange (Informatik)
EIN Warteschlange (Englisch für Warteschlange) ist in der Informatik ein Datenstruktur zum Speichern einer unterschiedlichen Anzahl von Elementen, wobei das zuerst hinzugefügte Element zuerst entfernt wird (FIFO).
Die Operationen in einer Warteschlange sind:
- in die Warteschlange stellen (oder Gut): ein Element wird in die Warteschlange gestellt
- aus der Warteschlange (oder erhalten): ein Element wird aus der Warteschlange entfernt
- leer: testet, ob die Warteschlange leer ist
Manchmal wird es auch unterstützt:
- Größe: gibt die Anzahl der Elemente in der Warteschlange zurück
Folgende Fehler können auftreten:
- Unterlauf: ein Versuch, ein Element aus einer leeren Warteschlange abzurufen.
- Überlauf: ein Versuch, ein Element zu einer vollen Warteschlange hinzuzufügen. Dies ist nur möglich, wenn die Warteschlange eine begrenzte Größe hat.
Implementierung einer Queue-Datenstruktur
Eine Warteschlange kann implementiert werden als verlinkte Liste, oder, mit begrenzter Größe, als a Array.Um ein unbegrenztes Durchlaufen der Warteschlangendaten durch den Speicher zu vermeiden, wird ein solches Array normalerweise als RingPuffer: das vordere Element der Warteschlange steht dann nicht immer ganz vorne im Array, sondern wird durch ein Extra gekennzeichnet Zeiger die ständig verschoben wird. Wenn das Ende des Puffers erreicht ist, wird am Anfang fortgesetzt.
Beim Senden und Empfangen von seriellen Daten wird normalerweise eine Warteschlange verwendet - das Programm bereitet eine Reihe von Bytes zur Verarbeitung für die Übertragung vor, die dann nacheinander gesendet werden. Bei Erreichen eines bestimmten Füllgrads der Warteschlange wird ein „Hochwasser“-Signal ausgegeben, das anzeigt, dass für eine Weile kein Platz mehr ist; ist der Pufferinhalt unter ein bestimmtes Minimum gefallen, wird dieses Signal wieder entfernt und/oder ein 'Wassermangel'-Signal gesetzt.