Gepubliceerd op 2 september 2026 · 14 min leestijd

Queues uitgelegd

Een fotozuil heeft één printer, maar meerdere klanten kunnen afdruktaken indienen terwijl die bezig is. Ava stuurt twaalf foto’s. Een paar seconden later stuurt Bo er één en daarna stuurt Chen er zes. De printer kan de drie taken niet tegelijk verwerken. De zuil moet de wachtende taken dus ergens bewaren. Normaal gesproken hoort de taak van Ava voor die van Bo te worden afgedrukt, en die van Bo voor die van Chen, omdat ze in die volgorde binnenkwamen.

Eén variabele kan niet meerdere wachtende taken bevatten. Een array kan dat wel. Een array is een rij genummerde plaatsen in het geheugen. Iedere plaats kan een waarde bevatten of een verwijzing naar een waarde die elders in het geheugen staat. We kunnen de eerstvolgende taak op plaats 0 zetten, de taak daarna op plaats 1, enzovoort. Het probleem ontstaat wanneer de taak van Ava vertrekt. Het verwijderen van plaats 0 laat een gat achter. Als we eisen dat de volgende taak altijd op plaats 0 staat, moet het programma de verwijzing naar Bo één plaats naar links kopiëren, daarna die naar Chen en vervolgens iedere andere wachtende verwijzing. Om één taak uit een queue van een miljoen taken te verwijderen, moeten dan mogelijk 999.999 verwijzingen worden gekopieerd.

Een queue geeft ons een betere regel. Nieuwe items komen aan het ene uiteinde binnen en wachtende items vertrekken aan het andere. Een circulaire array kan deze regel uitvoeren zonder na iedere verwijdering de overgebleven items te verplaatsen. Het programma onthoudt waar het volgende item staat en waar de volgende lege plaats is. Een gewone toevoeging of verwijdering kost daardoor een vaste hoeveelheid werk, ongeacht of de queue drie of drie miljoen taken bevat. Een vaste circulaire array heeft wel een grens. Zodra iedere plaats bezet is, moet het programma nieuw werk weigeren, op vrije ruimte wachten of bewust een ander beleid toepassen.

Hoe werkt een queue?

Een queue is een regel die bepaalt welk opgeslagen item als volgende naar buiten komt. Bij een gewone first-in, first-out-queue vertrekt het item dat als eerste binnenkwam ook als eerste. Deze regel wordt meestal afgekort tot FIFO. Een item toevoegen heet enqueueing. Het nieuwe item sluit achteraan aan bij de staart. Het oudste item verwijderen heet dequeueing. Dat item vertrekt vanaf de kop. Met peeking lees je het item bij de kop zonder het te verwijderen.

De regel is belangrijker dan de onderliggende opslag. Het ene programma bewaart zijn queue in een array. Een ander verbindt los toegewezen stukken geheugen die we gekoppelde knooppunten noemen. Beide kunnen dezelfde FIFO-werking aanbieden aan de code die de queue gebruikt.

Niet iedere verzameling met “queue” in de naam volgt FIFO. Een priority queue kiest op basis van een rangorde, terwijl een double-ended queue toevoegingen en verwijderingen aan beide uiteinden toestaat. Dit artikel gaat over de gewone FIFO-queue.

Waarom verwijderen we niet de eerste plaats van de array?

We beginnen met vier plaatsen in een array. Iedere bezette plaats bevat een verwijzing naar een afdruktaak. Een verwijzing is een waarde die het programma vertelt waar de volledige taak in het geheugen staat. Het kopiëren van een verwijzing kopieert niet alle foto’s, maar honderdduizenden verwijzingen kopiëren kost nog steeds werk.

positie:  0      1       2       3
taak:     Ava    Bo      Chen    leeg

Als dequeue altijd positie 0 verwijdert, blijft er na het verwijderen van Ava een gat voor Bo over. Het programma kan de indeling herstellen door de verwijzing naar Bo naar positie 0 en die naar Chen naar positie 1 te kopiëren.

positie:  0      1       2       3
taak:     Bo     Chen    leeg    leeg

Deze indeling ziet er netjes uit, maar die netheid kost iets. Iedere overgebleven verwijzing is verplaatst. Naarmate de queue groeit, kan iedere verwijdering meer kopieerwerk vragen.

De volgende taak hoeft niet op positie 0 te blijven staan. Het programma kan in plaats daarvan een getal met de naam headPosition bewaren. Dat getal wijst de plaats met de volgende taak aan. Nadat Ava is verwijderd, wist het programma positie 0 en verandert het de kop van 0 in 1. Bo en Chen blijven staan.

positie:  0       1       2       3
taak:     leeg    Bo      Chen    leeg
                 ^ kop            ^ staart

Het wissen van de oude plaats is belangrijk. De queue bezit de taak van Ava niet meer en hoort dus geen verwijzing ernaar te bewaren. Als geen ander deel van het programma nog naar die taak verwijst, kan het geheugenbeheer het bijbehorende geheugen vrijgeven.

Het tweede onthouden getal is tailPosition. Het wijst de lege plaats aan waar de volgende toegevoegde taak terechtkomt. De queue verandert nu posities in plaats van alle actieve verwijzingen te verplaatsen.

De array als cirkel hergebruiken

Door de kop en staart naar rechts te verplaatsen, ontstaan lege plaatsen aan het begin van de array. Uiteindelijk bereikt de staart de laatste positie, terwijl die eerdere plaatsen beschikbaar zijn. Een circulaire array lost dit op door de positie na de laatste plaats als positie 0 te behandelen. Er bestaat geen fysieke cirkel in het geheugen. Het programma bezit nog steeds één gewone rij plaatsen. Alleen de positieberekening loopt rond.

We gebruiken een array met vijf plaatsen en onthouden drie getallen. headPosition wijst het volgende te verwijderen item aan. tailPosition wijst de volgende te vullen plaats aan. itemCount houdt bij hoeveel items aanwezig zijn.

Aan het begin is iedere plaats leeg. De kop en de staart staan beide op positie 0 en het aantal items is 0.

positie:            0       1       2       3       4
opgeslagen waarde:  leeg    leeg    leeg    leeg    leeg
headPosition:       0
tailPosition:       0
itemCount:          0
logische volgorde:  leeg

Voeg Ava, Bo en Chen toe. Iedere bewerking schrijft één verwijzing naar de plaats die de staart aanwijst, schuift de staart door en telt één bij het aantal op.

positie:            0       1       2       3       4
opgeslagen waarde:  Ava     Bo      Chen    leeg    leeg
headPosition:       0
tailPosition:       3
itemCount:          3
logische volgorde:  Ava, Bo, Chen

Verwijder nu twee keer een item. De eerste aanroep leest Ava op positie 0 en wist die plaats. De tweede doet hetzelfde met Bo op positie 1. De kop schuift twee keer door en het aantal daalt twee keer. De verwijzing naar Chen beweegt niet.

positie:            0       1       2       3       4
opgeslagen waarde:  leeg    leeg    Chen    leeg    leeg
headPosition:       2
tailPosition:       3
itemCount:          1
logische volgorde:  Chen

Voeg Dina en Eli toe. Hun verwijzingen komen op posities 3 en 4 terecht. Na het schrijven van Eli op positie 4 moet de staart doorschuiven. Positie 5 bestaat niet en daarom loopt de staart rond naar 0.

Het programma kan dit berekenen door één bij de huidige positie op te tellen, het resultaat door de capaciteit van de array te delen en de rest te bewaren. De rest is wat overblijft nadat zo veel mogelijk volledige groepen zijn gemaakt. Vijf gedeeld door vijf heeft rest 0. Positie 4 doorschuiven in een array met vijf plaatsen levert dus positie 0 op.

positie:            0       1       2       3       4
opgeslagen waarde:  leeg    leeg    Chen    Dina    Eli
headPosition:       2
tailPosition:       0
itemCount:          3
logische volgorde:  Chen, Dina, Eli

Voeg Faye toe. Haar verwijzing komt op de vrije positie 0 terecht en de staart schuift door naar positie 1.

positie:            0       1       2       3       4
opgeslagen waarde:  Faye    leeg    Chen    Dina    Eli
headPosition:       2
tailPosition:       1
itemCount:          4
logische volgorde:  Chen, Dina, Eli, Faye

De bezette plaatsen van links naar rechts lezen geeft Faye, Chen, Dina en Eli. Dat is niet de volgorde van de queue. De logische volgorde begint bij de bewegende kop, loopt door tot het einde van de array en gaat daarna verder aan het begin. De volgende dequeue geeft Chen terug, niet Faye.

Het aantal items lost ook een minder zichtbare dubbelzinnigheid op. Wanneer de kop en de staart beide 0 zijn, kan de queue leeg zijn, zoals aan het begin. Ze kunnen elkaar ook ontmoeten nadat de staart een volledige ronde heeft gemaakt en iedere plaats heeft gevuld. Een aantal van 0 betekent leeg en een aantal van 5 betekent vol. De posities alleen vertellen niet in welke toestand de queue verkeert.

Hoe werkt een queue in code?

De pseudocode hieronder bouwt dezelfde queue met vijf plaatsen. noItem stelt een lege plaats voor en kan geen geldige afdruktaak zijn. De code geeft queueFull of queueEmpty terug in plaats van stilzwijgend een taak te overschrijven of een lege plaats te lezen.

; Het geheugen begint met vijf lege plaatsen en drie beheersgetallen.
(define capacity 5)
(define storedJobs (makeArray capacity noItem))
(define headPosition 0)
(define tailPosition 0)
(define itemCount 0)

(define advancePosition (function currentPosition)
  ; Positie 4 gaat naar 0 omdat 5 gedeeld door 5 rest 0 heeft.
  (return (remainder (add currentPosition 1) capacity))))

(define enqueue (function job)
  (if (equals itemCount capacity)
    (return queueFull))

  ; Voor deze schrijfactie wijst tailPosition een lege plaats aan.
  ; Daarna bevat die plaats een verwijzing naar de nieuwe taak.
  (arraySet storedJobs tailPosition job)
  (set tailPosition (advancePosition tailPosition))
  (set itemCount (add itemCount 1))
  (return added)))

(define dequeue (function)
  (if (equals itemCount 0)
    (return queueEmpty))

  (define nextJob (arrayGet storedJobs headPosition))

  ; Verwijder de verwijzing van de queue voordat de kop doorschuift.
  (arraySet storedJobs headPosition noItem)
  (set headPosition (advancePosition headPosition))
  (set itemCount (subtract itemCount 1))
  (return nextJob)))

(define peek (function)
  ; Peeking leest de plaats bij de kop zonder geheugen te veranderen.
  (if (equals itemCount 0)
    (return queueEmpty))
  (return (arrayGet storedJobs headPosition))))

(enqueue "Ava")
(enqueue "Bo")
(enqueue "Chen")
; Plaatsen: [Ava, Bo, Chen, noItem, noItem]
; Kop: 0, staart: 3, aantal: 3

(dequeue)
; Geeft Ava terug, wist plaats 0 en schuift de kop door naar 1.

(dequeue)
; Geeft Bo terug, wist plaats 1 en schuift de kop door naar 2.

(enqueue "Dina")
(enqueue "Eli")
; Eli komt op plaats 4, daarna loopt de staart rond naar 0.

(enqueue "Faye")
; Plaatsen: [Faye, noItem, Chen, Dina, Eli]
; Logische volgorde: Chen, Dina, Eli, Faye

(dequeue)
; Geeft Chen terug. De meest linkse bezette plaats is niet de kop.

Echte programmeerinterfaces handelen lege en volle toestanden op verschillende manieren af. Sommige geven een fout, sommige geven naast het resultaat een succesvlag terug en andere gebruiken een speciale waarde. Welke aanpak een interface ook kiest, die moet de bijzondere uitkomst van een geldig opgeslagen item kunnen onderscheiden.

Hoeveel werk verricht een queue?

Een gewone enqueue schrijft één plaats in de array en verandert de staart en het aantal. Een gewone dequeue leest en wist één plaats en verandert daarna de kop en het aantal. Het aantal wachtende taken voegt aan geen van beide bewerkingen extra stappen toe. Dit heet constante tijd en wordt meestal als O(1) geschreven. Constante tijd betekent niet dat de bewerking geen tijd kost. Het betekent dat de hoeveelheid werk niet met de lengte van de queue groeit.

Peeking kost ook constante tijd, omdat het de bekende plaats bij de kop leest zonder het geheugen te veranderen. Naar een bepaalde taak zoeken is anders. Een FIFO-queue vertelt het programma alleen welk item het volgende is. Er bestaat geen regel om rechtstreeks naar Chen te springen, dus een zoekopdracht moet mogelijk ieder wachtend item bekijken.

Voor een queue die zijn array vergroot, geldt één aanvulling. Als de huidige opslag vol is, kan de queue een grotere array toewijzen en de actieve verwijzingen ernaartoe kopiëren. Die ene enqueue is duur, omdat het kopieerwerk met het aantal wachtende items groeit. Als de array steeds met een grote factor groeit, bijvoorbeeld door te verdubbelen, voeren de meeste enqueues nog altijd alleen het kleine vaste aantal bewerkingen uit. De incidentele kopieerkosten worden over veel goedkope enqueues verdeeld. Dit heet geamortiseerde constante tijd.

Wanneer worden queues gebruikt?

Queues zijn nuttig wanneer werk met de ene snelheid binnenkomt en een ander deel van een systeem het met een andere snelheid verwerkt. De fotozuil accepteert een korte piek aan afdruktaken, hoewel één printer maar één taak tegelijk kan afronden. De code die inzendingen ontvangt is een producent, omdat die werk voor de queue maakt. De printer is een consument, omdat die het werk verwijdert en verwerkt. Dezelfde opzet komt voor bij het bezorgen van e-mail, beeldverwerking en webservers die verzoeken laten wachten tot een verwerker beschikbaar is.

Een queue vangt een tijdelijk snelheidsverschil op. Ze maakt geen extra verwerkingscapaciteit. Als klanten langdurig sneller taken indienen dan de printer ze voltooit, raakt de queue uiteindelijk vol of gebruikt ze steeds meer geheugen. Bij een queue met een vaste capaciteit moet de systeemontwerper kiezen wat er daarna gebeurt. De producent kan wachten tot ruimte vrijkomt, de nieuwe taak weigeren of die in duurzamere opslag bewaren. De producent laten wachten of vertragen is een vorm van backpressure. De beperkte snelheid van de consument werkt terug naar de bron, in plaats van het wachtende werk onbeperkt te laten groeien.

Queues helpen algoritmen ook om mogelijkheden laag voor laag te onderzoeken. Stel dat we een route met het kleinste aantal treinverbindingen zoeken. We beginnen bij Thuis, met rechtstreekse verbindingen naar Museum en Park. Voeg beide stations aan de queue toe en markeer ze meteen als ontdekt, zodat een andere route geen van beide stations nogmaals kan toevoegen. Verwijder Museum en voeg zijn nog niet bezochte buur Bibliotheek toe. Verwijder daarna Park en voeg Stadion toe. Ieder station op één verbinding afstand kwam in de queue voordat een station op twee verbindingen afstand werd toegevoegd. Het algoritme bezoekt daardoor eerst de nabijgelegen lagen. Deze methode heet breadth-first search. Ze vindt een route met het kleinste aantal verbindingen wanneer iedere verbinding dezelfde kosten heeft. Routes met verschillende reistijden hebben een regel nodig die rekening houdt met die kosten.

Message brokers gebruiken een verwant idee tussen losse programma’s. Een uitgever stuurt een bericht naar de broker en een consument ontvangt het later. De broker kan berichten op schijf bewaren, op bevestigingen wachten, mislukt werk opnieuw aanbieden of berichten over meerdere consumenten verdelen. Door die functies zijn de toezeggingen ingewikkelder dan bij onze lokale array. De basisscheiding blijft nuttig. Producenten kunnen werk indienen zonder het zelf uit te voeren.

Capaciteit en voltooiingsvolgorde

Een vaste circulaire queue reserveert één compact blok plaatsen en maakt de geheugengrens expliciet. De normale bewerkingen wijzen niet voor ieder item een nieuw stuk geheugen toe. Daar staat een vast maximum tegenover. Een uitbreidbare array neemt dat specifieke maximum weg, maar één groeibewerking moet nieuwe opslag toewijzen en iedere actieve verwijzing kopiëren.

Een gekoppelde queue maakt een andere afweging. Ze wijst voor ieder toegevoegd item één knooppunt toe. Een knooppunt bewaart het item en een verwijzing naar het volgende knooppunt. De queue onthoudt het knooppunt bij de kop en dat bij de staart. Ze kan met één knooppunt tegelijk groeien zonder bestaande items te kopiëren, maar ieder item heeft een extra verwijzing en meestal een losse toewijzing nodig. Beide vormen kunnen enqueue en dequeue in constante tijd aanbieden. Geen van beide verandert de FIFO-regel die de aanroeper ziet.

FIFO beschrijft ook de volgorde waarin items de queue verlaten, niet noodzakelijk de volgorde waarin het werk klaar is. Stel dat één werker Ava uit de queue haalt en een andere werker daarna Bo. De queue gaf Ava als eerste door. Als de taak van Bo veel kleiner is, kan Bo toch eerder klaar zijn. Mislukkingen en nieuwe pogingen kunnen de zichtbare resultaten verder veranderen. Voor een strikte voltooiingsvolgorde is meer nodig dan een FIFO-container, vaak één consument en een zorgvuldig omschreven beleid voor fouten.

Samenvatting

Een FIFO-queue voegt nieuwe items aan de staart toe en verwijdert het oudste item vanaf de kop. Een eenvoudige array kan die volgorde bewaren door na iedere verwijdering alle overgebleven verwijzingen te verschuiven, maar het werk groeit met de queue mee. Een circulaire array vermijdt dat verschuiven. Ze verplaatst de kop- en staartposities door dezelfde opslag, laat ze aan het einde rondlopen naar positie 0 en bewaart een aantal om een lege queue van een volle te onderscheiden.

Onthoud vooral dat de volgorde van de queue uit de bewegende kop volgt, niet uit de fysieke volgorde van bezette geheugenplaatsen van links naar rechts. De implementatie kan een circulaire array, gekoppelde knooppunten of opslag in een message broker gebruiken. Het FIFO-contract beantwoordt steeds dezelfde vraag. Welk wachtend item hoort als volgende te vertrekken? Capaciteit, foutafhandeling en het aantal consumenten zijn losse keuzes die bepalen wat het omliggende systeem kan beloven.

Meer lezen

De handleiding over datastructuren van Python legt uit waarom bij het verwijderen van het eerste item uit een lijst de overgebleven elementen moeten verschuiven. De documentatie over deque beschrijft een verzameling die is ontworpen voor efficiënte toevoegingen en verwijderingen aan beide uiteinden. Java’s Queue-interface laat zien hoe echte interfaces op verschillende manieren onderscheid maken tussen bewerkingen die een lege of volle toestand melden. De queue-handleiding van RabbitMQ legt aan de hand van een gedistribueerd voorbeeld uit hoe meerdere producenten, consumenten en nieuwe bezorgpogingen de volgorde beïnvloeden die een toepassing waarneemt.