Les 10 - Queue

• Informatica
• Middelbare school
• havo, vwo
• Leerjaar 4-6

Datastructuren

Queue

Leerdoel

Aan het eind van de les ken je de kenmerken van een queue, ken je het principe First-in, First-out (FIFO) en kan je een queue programmeren met python.

Wat is geen kenmerk van een verzameling

1. het heeft een index
2. de grootte is dynamisch
3. het kan dezelfde elementen bevatten

Bekijk onderstaande python code van een declaratie van een verzameling. Kan dit?

namen = {"Pieter", "pieter", "Sander", "Jan", "sander", "Karel"}

1. ja
2. nee

Wat is een voorwaarde als je verzamelingen wilt vergelijken?

1. Er moet minimaal één element anders zijn in de verzamelingen
2. Je moet twee verzamelingen hebben om te kunnen vergelijken
3. Er moet minimaal één element hetzelfde zijn in de verzamelingen

Je gaat twee verzamelingen vergelijken. bekijk de afbeelding rechts, naar de rode vlakken.

Dit zegt van de verzamelingen dat er sprake is van

1. een verschil
2. een doorsnede
3. een vereniging

Hieronder staan twee verzamelingen. Je wilt weten welke producten in beide verzamelingen zitten. Welke vergelijking ga je dan toepassen?

tomatensoep = {"tomaten", "bouillonblok", "ui"}

groentesoep = {"soepgroenten", "bouillonblok", "ui"}

1. verschil
2. doorsnede
3. vereniging

Hieronder staan twee verzamelingen. Je wilt weten welke producten in beide verzamelingen zitten. Je wilt dus een doorsnede bepalen van de verzamelingen. Geef de juiste python code om de vergelijking te maken.

tomatensoep = {"tomaten", "bouillonblok", "ui"}

groentesoep = {"soepgroenten", "bouillonblok", "ui"}

Antwoord:

verschil = tomatensoep.intersection(groentesoep)

Queue

Een queue is een speciaal soort lijst: het stelt een wachtrij voor. Het Engelse woord voor wachtrij is queue.

First-in, First-out (FIFO)

Je kunt de rij mensen die bij een kassa staan te wachten zien als een queue. De klant die het eerst in de rij is gaan staan, is ook de klant die het eerste aan de beurt is bij de kassa. En de klant die als laatste in de rij gaat staan, moet het langst wachten om aan de beurt te komen. In een queue worden alle elementen bewaard op volgorde van toevoeging.

Dit principe wordt First-in, First-out (FIFO) genoemd.

Werking

Een queue wordt veel gebruikt. Bijvoorbeeld door een processor van een computer. Alle verzoeken aan een processor worden in een queue geplaatst en volgens het FIFO-principe afgehandeld.

Kan je nog een voorbeeld noemen waarin sprake is van een queue?

Declaratie queue in python (1)

Een queue werkt niet direct in python. Hiervoor moet een zogenaamde library worden geïmporteerd.

from queue import Queue

Declaratie queue in python (2)

Om met een queue te kunnen werken moet er eerst een variabele worden gedeclareerd van het type queue.

kassa = Queue()

Toevoegen elementen aan een queue in python

Om een element toe te voegen aan de queue maak je gebruik van de functue put().

from queue import Queue

kassa = Queue()

kassa.put("klant 1")

kassa.put("klant 2")

kassa.put("klant 3")

Eelementen uit een queue ophalen in python

Om een element uit de queue op te halen maak je gebruik van de functie get().

from queue import Queue

kassa = Queue()

kassa.put("klant 1")

kassa.put("klant 2")

kassa.put("klant 3")

print(kassa.get())

Hoeveel elementen bevat de queue nog na het uitvoeren van onderstaande code?

from queue import Queue

kassa = Queue()

kassa.put("klant 1")

kassa.put("klant 2")

kassa.put("klant 3")

print(kassa.get())

1. 0
2. 1
3. 2
4. 3

Eelementen uit een queue ophalen

Als een element uit de queue is gehaald met de functie get() dan is dit element uit de queue gehaald en is dit element dus niet meer aanwezig in de queue!

Queue uitlezen tot deze leeg is in python

Om een queue uit te lezen tot deze leeg is kan er gebruik worden gemaakt van een iteratie en in combinatie met de functie empty().

from queue import Queue

kassa = Queue()

kassa.put("klant 1")

kassa.put("klant 2")

kassa.put("klant 3")

while not kassa.empty():

    volgendeKlant = kassa.get()

    print("De eerst volgende klant is: " + volgendeKlant)

Huidige aantal elementen in de queue

Het kan handig zijn om te weten hoeveel elementen er op een bepaald moment in de queue zitten. Om te controleren hoeveel elementen er in de queue zitten maak je gebruik van de functie qsize().

from queue import Queue

kassa = Queue()

kassa.put("klant 1")

kassa.put("klant 2")

kassa.put("klant 3")

print(kassa.qsize())