Wachtrij
Van Wikipedia
Een wachtrij is een begrip in de stochastiek die abstract kan worden omschreven als een aantal elementen die in een bepaalde volgorde op een gebeurtenis wachten, bijvoorbeeld klanten aan een loket die wachten om te worden geholpen. In de wachtrijtheorie worden wachtrijsystemen geanalyseerd.
In de informatica is de wachtrij een van de mogelijke datastructuren die meestal queue (uitgeproken als 'kjoe') genoemd wordt. Kenmerk is dat wie het eerst in de rij staat, het eerst geholpen wordt: voordringen mag niet.
Als we deze laatste eis (i.e. niet voordringen) laten vallen en aan ieder element zowel een urgentie als een te verwachten verwerkingstijd koppelen, kunnen er interessante wiskundige modellen worden gebouwd om te voorspellen wat de efficiëntste volgorde van afhandelen is, of b.v. de vraag te beantwoorden hoeveel loketten er het beste open kunnen gaan als de klanten met een bepaalde gemiddelde frequentie binnen komen.
[bewerk] Meer informatie over begrip queue uit de informatica
In de informatica is men gewend het engelse woord queue te gebruiken en behoort het tot het jargon van dat kennisgebied. Het nederlandse equivalent is wachtrij. Een queue is in de informatica een datastructuur voor de opslag van een wisselend aantal elementen waarvan het element dat het eerst in de rij ging, er ook het eerst weer uit wordt opgehaald. Dit principe wordt ook wel FIFO (First In First Out) genoemd. De tegenhanger van de queue is de stack, dat volgens het LIFO (Last In First Out) principe werkt. Een queue is te vergelijken met een wachtrij in de winkel: degene die het eerst komt, wordt het eerst geholpen. Degene die het laatst komt is als laatste aan de beurt.
Mogelijke bewerkingen op een queue zijn:
- Een element in de queue plaatsen.
- Een element uit de queue ophalen.
Om onbeperkt door het geheugen wandelen van de queue-data te vermijden wordt bij de implementatie meestal gebruikgemaakt van een ringbuffer: als het einde van de gereserveerde hoeveelheid geheugen is bereikt, gaat men verder aan het begin. Er kan queue overflow optreden als er meer elementen worden geplaatst dan waar ruimte voor is, en queue underflow als er meer elementen worden verwijderd dan erin waren geplaatst.
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 één voor één 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.
