Wachtrijen

De eerste van 1000 waarden uit een JavaScript-array halen met shift verplaatst de andere 999; een ringbuffer doet hetzelfde in één stap.

Eerst erin, eerst eruit

Een wachtrij is een rij bij een winkelbalie. Mensen sluiten achteraan aan en worden vooraan geholpen, dus wie eerst kwam vertrekt eerst. De regel is eerst erin, eerst eruit (FIFO). De twee bewerkingen zijn enqueue, dat achteraan een waarde toevoegt, en dequeue, dat de voorste verwijdert. In de MIT-notities van 6.006 is een wachtrij de reeksinterface beperkt tot insert last(x) en delete first().

Wachtrijen zijn overal waar werk in aankomstvolgorde moet worden verwerkt: documenten voor een printer, toetsaanslagen voor een programma, berichten voor een server. Breedte-eerst zoeken, uit de algoritmen, bewaart de nog te bezoeken vakjes in een wachtrij. Daarom verkent het precies in ringen van gelijke afstand.

De eenvoudige manier en verborgen kosten

In JavaScript is een array de voor de hand liggende wachtrij: push voor enqueue achteraan en shift voor dequeue vooraan. Het werkt en is prima voor korte wachtrijen. Maar bekijk wat shift doet. MDN zegt dat het ‘alle waarden met 1 naar links verschuift’ en de ECMAScript-specificatie schrijft het als een lus die voor elke k element k naar positie k − 1 kopieert. De voorkant van een array is de dure kant, zoals je in het eerste hoofdstuk zag. Dequeue op n waarden kost 1 leesactie plus n − 1 verplaatsingen, dus een wachtrij van 1000 waarden kost 1000 stappen per dequeue. (Engines kunnen intern afkorten, maar de specificatie belooft niets.)

Als je 5 waarden aan een lege array toevoegt en ze daarna alle 5 verwijdert, kosten de enqueues 5 stappen en de dequeues 5 + 4 + 3 + 2 + 1 = 15, samen 20. Het meeste daarvan is waarden verplaatsen die niet eens worden verwijderd.

Verplaats niet de waarden, maar de voorkant

De oplossing is stoppen met waarden verplaatsen en in plaats daarvan onthouden waar de voorkant is. Bewaar een index head. Dequeue leest de waarde bij head en telt 1 bij head op; niets anders beweegt. Het nadeel is dat de cellen vóór head worden verspild. Een ringbuffer (circulaire buffer) hergebruikt ze: de array heeft een vast aantal cellen, bijvoorbeeld 8, en posities lopen rond, dus na cel 7 komt 0. Bewaar head en size. De volgende enqueue gaat naar cel (head + size) mod 8 en een dequeue neemt cel head en verandert head in (head + 1) mod 8. Beide bewerkingen kosten 1 stap. De prijs is vaste capaciteit: als size 8 bereikt is de wachtrij vol, tenzij je alles naar een grotere ring kopieert zoals een dynamische array zou doen.

Laden

Sleep om te draaien. Scroll of knijp om te zoomen.

Een wachtrij met vier waarden. Met ‘Array met shift’ verplaatst elke dequeue de rest van de rij. Zet het soort op ‘Ringbuffer’ en de waarden blijven staan terwijl head en tail rond de ring bewegen.

Probeer dit in het lab: schakel over op de ringbuffer, doe vier enqueues om alle 8 cellen te vullen en doe er nog één. Dat wordt geweigerd omdat een vaste ring geen negende cel heeft. Doe dan twee dequeues en weer een enqueue: de nieuwe waarde gaat naar cel 0, de ring rond.

Wachtrij op n waarden	Enqueue	Dequeue
Array met push en shift	1 (geamortiseerd)	1 leesactie + (n − 1) verplaatsingen
Array met een head-index	1 (geamortiseerd)	1, maar voorste cellen worden verspild
Ringbuffer met vaste grootte	1, of vol	1

Welke gebruik je? Voor een wachtrij met nooit meer dan enkele tientallen waarden zijn push en shift kort en duidelijk en kost het verplaatsen bijna niets. Voor een wachtrij waar duizenden items doorheen gaan, zoals de vakjes van een grote breedte-eerstzoekactie, houdt een head-index of ringbuffer elke dequeue op één stap. Het verschil groeit met de lengte van de rij.

FIFO	Eerst erin, eerst eruit: waarden vertrekken in aankomstvolgorde.
Enqueue / dequeue	Achteraan toevoegen / vooraan verwijderen.
shift	Verwijdert de eerste arraywaarde en verplaatst alle andere één cel naar links.
Ringbuffer	Een vaste array gebruikt als cirkel: de volgende vrije cel is (head + size) mod capaciteit.

In welke volgorde geeft een wachtrij waarden terug?
- Eerst erin, eerst eruit
- Laatst erin, eerst eruit
- Grootste eerst
- Willekeurige volgorde
Enqueue A, B, C. Doe eenmaal dequeue. Enqueue D. Doe nu dequeue tot leeg. Zet die waarden op volgorde.
Hoeveel stappen kost één dequeue met push en shift op een wachtrij van 4 waarden (1 leesactie plus verplaatsingen)?
Dezelfde methode, een wachtrij van 1000 waarden: hoeveel stappen voor één dequeue?
Begin met een lege array. Enqueue 5 waarden met push en doe daarna voor alle 5 dequeue met shift. Hoeveel stappen in totaal?
Een ringbuffer heeft 8 cellen (0 tot 7), head = 6 en size = 3. Welke cel gebruikt de volgende enqueue?
Hoeveel stappen kost een dequeue uit een ringbuffer, ongeacht het aantal waarden?
Een vaste ring van 8 cellen bevat 8 waarden. Wat gebeurt er bij enqueue?
- De voorste waarde wordt overschreven
- De wachtrij is vol en de waarde wordt geweigerd
- Elke waarde schuift naar links
- De waarden worden gesorteerd
Welke zoekmethode uit de algoritmen bewaart wachtende vakjes in een wachtrij?
- Binair zoeken
- Breedte-eerst zoeken
- Diepte-eerst zoeken
- Lineair zoeken
Welke twee reeksbewerkingen gebruikt een wachtrij in de termen van MIT 6.006?
- insert last en delete last
- insert last en delete first
- insert first en delete first
- get at en set at

Belangrijkste punten

Een wachtrij is eerst erin, eerst eruit: enqueue achteraan, dequeue vooraan.
shift verplaatst elke resterende waarde, dus dequeue op n waarden kost n stappen.
Een head-index of ringbuffer maakt dequeue 1 stap.
In een ring met grootte c is de volgende vrije cel (head + size) mod c.

Bronnen van deze cursus (11)

MIT OpenCourseWare 6.006 Introduction to Algorithms, Spring 2020 (Demaine, Ku, Solomon)
lecture notes 2 Data Structures (interface vs data structure, Sequence and Set interfaces, stack = insert_last/delete_last, queue = insert_last/delete_first, array, linked list, dynamic array, amortized Θ(1) append)
4 Hashing (chaining, pigeonhole collisions, chain length n/m)
6 Binary Trees Part 1 (height, traversal order, O(h) operations) and 7 Binary Trees Part 2: AVL (Adelson-Velsky and Landis, 1962) at ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/pages/lecture-notes
MDN Web Docs, Array.prototype.shift (shifts all values left by 1)
Array.prototype.unshift, Map (insertion order, Map vs Object, spec requires sublinear average access) and Set (developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects)
ECMAScript 2025 Language Specification (tc39.es/ecma262)
24.1 Map Objects and 24.2 Set Objects ("must be implemented using either hash tables or other mechanisms that, on average, provide access times that are sublinear on the number of elements")
Array.prototype.shift steps (Repeat, while k < len: move element k to k - 1)
D. E. Knuth, The Art of Computer Programming vol. 3 (2nd ed. 1998) section 6.4 History (H. P. Luhn, IBM internal memorandum January 1953, hashing with chaining; digit pairs added mod 10, 31415926 -> 4548) via gwern.net copy, and IEEE Spectrum, "Hans Peter Luhn and the Birth of the Hashing Algorithm" (2018)
"A brief history of the stack", SIGCIS (sigcis.org/files/A brief history.pdf: Bauer and Samelson applied for the patent in 1957, US 3,047,228 granted July 31, 1962; IPL list processing by Newell, Simon and Shaw at RAND 1956) and Wikipedia, Information Processing Language (Newell, Shaw, Simon, RAND and Carnegie Institute of Technology, about 1956).

Geraadpleegd: 2026-10-18