Wachtrij

Een wachtrij is een rij waar elementen aan kunnen worden toegevoegd en elementen uit kunnen worden weggenomen, zodanig dat wegnemen van een element altijd aan de andere kant gebeurt dan toevoegen. Met andere woorden: wie het langst in de rij staat wordt het eerst geholpen (FIFO-principe).

In winkels wordt de klanten bij binnenkomst vaak gevraagd een nummer te trekken. Hierdoor wordt op een onafhankelijk manier vastgelegd in welke volgorde de klanten zullen worden geholpen. Een fysieke rij is in een dergelijk geval niet noodzakelijk.

Wachtrijen worden bestudeerd in de wachtrijtheorie, een onderdeel van de stochastiek. Daarnaast zijn wachtrijen belangrijk als datastructuur en abstract datatype in de informatica, die ze echter meestal met hun Engelse naam queue aanduidt.

Wachtrijen in de wachtrijtheorie

Zie Wachtrijtheorie voor het hoofdartikel over dit onderwerp.

De wachtrijtheorie bestudeert wiskundige modellen van systemen waarin het werk wordt gedaan door een of meer verwerkingseenheden die maar een element tegelijk kunnen verwerken, zodat elementen voor verwerking in een wachtrij kunnen komen. Daarbij wordt aangenomen dat grootheden zoals de verwerkingstijd van elementen zich volgens gegeven stochastische functies gedragen. Het doel van de theorie is om hieruit andere informatie over het systeem af te kunnen leiden, bijvoorbeeld de totale gemiddelde wachttijd voor een element, of de gemiddelde rijlengte voor elke verwerkingseenheid. Zo kunnen bottlenecks en optimalisaties worden bepaald. Voorbeeld: hoeveel loketten moeten er opengaan om klanten te bedienen zonder dat de rijlengte groeit bij een gegeven frequentie waarmee de klanten binnenkomen.

De queue als abstract datatype

Zie Queue (informatica) voor het hoofdartikel over dit onderwerp.

In de informatica is een wachtrij een soort datastructuur, meestal queue genoemd of FIFO (First In First Out). De tegenhanger van de queue is de stack (stapel), die volgens het LIFO-principe werkt (Last In First Out).