Queue (informatica)
Een queue (Engels voor wachtrij) is in de informatica een datastructuur voor de opslag van een wisselend aantal elementen waarbij geldt dat het element dat het eerst werd toegevoegd het eerst wordt verwijderd (FIFO).
De operaties op een queue zijn:
- enqueue (of put): een element wordt in de queue geplaatst
- dequeue (of get): een element wordt uit de queue gehaald
- empty: test of de queue leeg is
Soms wordt ook wel ondersteund:
- size: retourneert het aantal elementen in de queue
Daarbij kunnen de volgende fouten optreden:
- underflow: een poging om een element uit een lege queue te halen.
- overflow: een poging om een element aan een volle queue toe te voegen. Dit kan alleen als de queue een begrensde grootte heeft.
Implementatie van een queue-datastructuur
[bewerken | brontekst bewerken]Een queue kan worden geïmplementeerd als gelinkte lijst, of, bij begrensde grootte, als een array. Om onbeperkt door het geheugen wandelen van de queue-data te vermijden wordt zo'n array meestal gebruikt als ringbuffer: het voorste element van de queue staat dan niet altijd vooraan de array, maar wordt aangegeven door een extra pointer die steeds verschoven wordt. Als het einde van de buffer bereikt is gaat men verder aan het begin.
Bij het verzenden en ontvangen van seriële data wordt meestal van een queue gebruikgemaakt - het programma zet een aantal te verwerken bytes klaar voor verzending die dan een voor een worden verzonden. Wordt een bepaalde mate van vulling van de queue bereikt, dan wordt een 'hoog water'-signaal van kracht dat aangeeft dat er even niets meer bij kan; is de bufferinhoud onder een bepaald minimum gedaald dan wordt dit signaal weer verwijderd en/of een 'laag water'-signaal gezet.