Wat is Python-wachtrij?
Een wachtrij is een container die gegevens bevat. De gegevens die als eerste worden ingevoerd, worden eerst verwijderd en daarom wordt een wachtrij ook wel "First in First Out" (FIFO) genoemd. De wachtrij heeft twee uiteinden voor en achter. De items worden van achteren ingevoerd en vanaf de voorkant verwijderd.
In deze Python-tutorial leer je:
- Wat is Python-wachtrij?
- Hoe werkt Python Queue?
- Typen wachtrijen in Python
- Installatie van Python-wachtrij
- Beschikbare methoden in de Queue- en LifoQueue-klasse
- Voorbeeld van een First In First Out-wachtrij
- Voorbeeld van een Last In First Out-wachtrij
- Voeg meer dan 1 item toe aan een wachtrij
- Wachtrij sorteren
- Wachtrij omkeren
Hoe werkt Python Queue?
De wachtrij kan gemakkelijk worden vergeleken met het echte voorbeeld: de rij mensen die in een rij bij de kassa staan te wachten, de persoon die als eerste staat, krijgt het kaartje als eerste, gevolgd door de volgende persoon, enzovoort. Dezelfde logica geldt ook voor de datastructuur van de wachtrij.
Hier is een schematische weergave van de wachtrij:
De achterkant vertegenwoordigt het punt waar de items in de wachtrij worden geplaatst. In dit voorbeeld is 7 daar de waarde voor.
De voorkant vertegenwoordigt het punt waar de items uit de wachtrij zullen worden verwijderd. Als u een item uit de wachtrij verwijdert, krijgt u als eerste element 1, zoals weergegeven in de afbeelding.
Item 1 was het eerste dat in de wachtrij werd geplaatst en tijdens het verwijderen is het het eerste dat naar buiten komt. Daarom heet de wachtrij FIRST IN FIRST OUT (FIFO)
In een wachtrij worden de items op volgorde verwijderd en kunnen ze niet tussendoor worden verwijderd. U kunt item 5 gewoon niet willekeurig uit de wachtrij verwijderen, daarvoor moet u alle items vóór 5 verwijderen. De items in de wachtrij worden verwijderd in de volgorde waarin ze zijn geplaatst.
Typen wachtrijen in Python
Er zijn hoofdzakelijk twee soorten wachtrijen in Python:
- First in First out Queue: hiervoor komt het element dat als eerste naar buiten komt als eerste naar buiten.
Om met FIFO te werken, moet u de Queue () -klasse aanroepen vanuit de wachtrijmodule.
- Laatste in Eerste uit wachtrij: hier komt het element dat het laatst is ingevoerd als eerste tevoorschijn.
Om met LIFO te werken, moet u de LifoQueue () -klasse aanroepen vanuit de wachtrijmodule.
Installatie van Python-wachtrij
Het is heel gemakkelijk om met wachtrij in python te werken. Hier zijn de stappen die u moet volgen om gebruik te maken van de wachtrij in uw code.
Stap 1) U hoeft alleen de wachtrijmodule te importeren, zoals hieronder weergegeven:
import queue
De module is standaard beschikbaar met python en je hebt geen extra installatie nodig om met de wachtrij te werken. Er zijn 2 soorten wachtrij FIFO (first in first out) en LIFO (last in first out).
Stap 2) Om met FIFO-wachtrij te werken, roept u de klasse Wachtrij op met behulp van de geïmporteerde wachtrijmodule zoals hieronder weergegeven:
import queueq1 = queue.Queue()
Stap 3) Om met de LIFO-wachtrij te werken, roept u de klasse LifoQueue () op zoals hieronder weergegeven:
import queueq1 = queue.LifoQueue()
Beschikbare methoden in de Queue- en LifoQueue-klasse
Hieronder volgen de belangrijke methoden die beschikbaar zijn in de Queue en LifoQueue-klasse:
- put (item): Dit plaatst het item in de wachtrij.
- get (): hiermee krijgt u een item uit de wachtrij terug.
- empty (): Het zal true retourneren als de wachtrij leeg is en false als er items aanwezig zijn.
- qsize (): geeft de grootte van de wachtrij terug.
- full (): geeft true terug als de wachtrij vol is, anders false.
Voorbeeld van een First In First Out-wachtrij
In het geval van first in first out, komt het element dat als eerste naar buiten komt als eerste naar buiten.
Voeg een item toe aan een wachtrij
Laten we aan een voorbeeld werken om een item in een wachtrij toe te voegen. Om met de wachtrij aan de slag te gaan, importeert u eerst de modulewachtrij, zoals weergegeven in het onderstaande voorbeeld.
Om een item toe te voegen, kunt u gebruik maken van de put () methode zoals getoond in het voorbeeld:
import queueq1 = queue.Queue()q1.put(10) #this will additem 10 to the queue.
Standaard is de wachtrij oneindig groot en kunt u er een willekeurig aantal items aan toevoegen. Als u de grootte van de wachtrij wilt definiëren, kunt u hetzelfde als volgt doen
import queueq1 = queue.Queue(5) #The max size is 5.q1.put(1)q1.put(2)q1.put(3)q1.put(4)q1.put(5)print(q1.full()) # will return true.
Uitgang:
True
De grootte van de wachtrij is nu 5 en er zijn niet meer dan 5 items nodig, en de methode q1.full () zal true retourneren. Als u nog meer items toevoegt, wordt de code niet verder uitgevoerd.
Verwijder een item uit de wachtrij
Om een item uit de wachtrij te verwijderen, kunt u de methode get () gebruiken. Met deze methode kunnen items uit de wachtrij worden opgeroepen.
Het volgende voorbeeld laat zien hoe u een item uit de wachtrij verwijdert.
import queueq1 = queue.Queue()q1.put(10)item1 = q1.get()print('The item removed from the queue is ', item1)
Uitgang:
The item removed from the queue is 10
Voorbeeld van een Last In First Out-wachtrij
In het geval van 'last in the first out queue', komt het element dat als laatste is ingevoerd als eerste naar buiten.
Om met LIFO te werken, dwz als laatste in de eerste out-wachtrij, moeten we de wachtrij-module importeren en gebruik maken van de LifoQueue () - methode.
Voeg een item toe aan een wachtrij
Hier zullen we begrijpen hoe u een item aan de LIFO-wachtrij kunt toevoegen.
import queueq1 = queue.LifoQueue()q1.put(10)
U moet de methode put () op LifoQueue gebruiken, zoals in het bovenstaande voorbeeld wordt getoond.
Verwijder een item uit de wachtrij
Om een item uit de LIFOqueue te verwijderen, kunt u de methode get () gebruiken.
import queueq1 = queue.LifoQueue()q1.put(10)item1 = q1.get()print('The item removed from the LIFO queue is ', item1)
Uitgang:
The item removed from the LIFO queue is 10
Voeg meer dan 1 item toe aan een wachtrij
In de bovenstaande voorbeelden hebben we gezien hoe u een enkel item toevoegt en het item verwijdert voor FIFO en LIFOqueue. Nu zullen we zien hoe u meer dan één item kunt toevoegen en ook kunt verwijderen.
Voeg een item toe aan een FIFOqueue
import queueq1 = queue.Queue()for i in range(20):q1.put(i) # this will additem from 0 to 20 to the queue
Verwijder een item uit de FIFOqueue
import queueq1 = queue.Queue()for i in range(20):q1.put(i) # this will additem from 0 to 20 to the queuewhile not q1.empty():print("The value is ", q1.get()) # get() will remove the item from the queue.
Uitgang:
The value is 0The value is 1The value is 2The value is 3The value is 4The value is 5The value is 6The value is 7The value is 8The value is 9The value is 10The value is 11The value is 12The value is 13The value is 14The value is 15The value is 16The value is 17The value is 18The value is 19
Voeg een item toe aan een LIFOqueue
import queueq1 = queue.LifoQueue()for i in range(20):q1.put(i) # this will additem from 0 to 20 to the queue
Verwijder een item uit de LIFOqueue
import queueq1 = queue.LifoQueue()for i in range(20):q1.put(i) # this will additem from 0 to 20 to the queuewhile not q1.empty():print("The value is ", q1.get()) # get() will remove the item from the queue.
Uitgang:
The value is 19The value is 18The value is 17The value is 16The value is 15The value is 14The value is 13The value is 12The value is 11The value is 10The value is 9The value is 8The value is 7The value is 6The value is 5The value is 4The value is 3The value is 2The value is 1The value is 0
Wachtrij sorteren
Het volgende voorbeeld toont het sorteren van de wachtrij. Het algoritme dat voor het sorteren wordt gebruikt, is bellen sorteren.
import queueq1 = queue.Queue()#Addingitems to the queueq1.put(11)q1.put(5)q1.put(4)q1.put(21)q1.put(3)q1.put(10)#using bubble sort on the queuen = q1.qsize()for i in range(n):x = q1.get() # the element is removedfor j in range(n-1):y = q1.get() # the element is removedif x> y :q1.put(y) #the smaller one is put at the start of the queueelse:q1.put(x) # the smaller one is put at the start of the queuex = y # the greater one is replaced with x and compared again with nextelementq1.put(x)while (q1.empty() == False):print(q1.queue[0], end = " ")q1.get()
Uitgang:
3 4 5 10 11 21
Wachtrij omkeren
Om de wachtrij om te draaien, kunt u gebruik maken van een andere wachtrij en recursie.
Het volgende voorbeeld laat zien hoe u de wachtrij omkeert.
Voorbeeld:
import queueq1 = queue.Queue()q1.put(11)q1.put(5)q1.put(4)q1.put(21)q1.put(3)q1.put(10)def reverseQueue (q1src, q2dest) :buffer = q1src.get()if (q1src.empty() == False) :reverseQueue(q1src, q2dest) #using recursionq2dest.put(buffer)return q2destq2dest = queue.Queue()qReversed = reverseQueue(q1,q2dest)while (qReversed.empty() == False):print(qReversed.queue[0], end = " ")qReversed.get()
Uitgang:
10 3 21 4 5 11
Overzicht:
- Een wachtrij is een container die gegevens bevat. Er zijn twee soorten wachtrij, FIFO en LIFO.
- Bij een FIFO (First in First out Queue) komt het element dat als eerste naar buiten komt als eerste naar buiten.
- Voor een LIFO (Last in First out Queue) komt het element dat het laatst is ingevoerd als eerste naar buiten.
- Een item in een wachtrij wordt toegevoegd met behulp van de put (item) methode.
- Om een item te verwijderen, wordt de methode get () gebruikt.