Python Wachtrij: FIFO, LIFO Voorbeeld
Logan Young
Wat is Python Wachtrij?
Een wachtrij is een container die gegevens bevat. De gegevens die als eerste worden ingevoerd, worden als eerste 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 via de achterkant ingevoerd en via de voorkant verwijderd.
Hoe werkt Python Wachtrij werk?
De wachtrij kan eenvoudig worden vergeleken met het echte voorbeeld: de rij mensen die in de rij staan te wachten bij de ticketbalie, de persoon die als eerste staat krijgt als eerste het ticket, gevolgd door de volgende persoon, enzovoort. Dezelfde logica geldt ook voor de wachtrijgegevensstructuur.
Hier is een schematische weergave van de wachtrij:
De Achterwiel vertegenwoordigt het punt waar de items in de wachtrij worden ingevoegd. In dit voorbeeld is 7 de waarde daarvoor.
De Voorzijde vertegenwoordigt het punt waar de items uit de wachtrij worden verwijderd. Als u een item uit de wachtrij verwijdert, is het eerste element dat u krijgt 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 eruit 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 eenvoudigweg niet willekeurig uit de wachtrij verwijderen. Om dat te doen moet u alle items vóór 5 verwijderen. De items in de wachtrij worden verwijderd in de volgorde waarin ze zijn ingevoegd.
Soorten wachtrij in Python
Er zijn hoofdzakelijk twee soorten wachtrijen Python:
- First in First out Wachtrij: Hiervoor zal het element dat als eerste gaat als eerste naar buiten komen. Om met FIFO te werken, moet je bellen Wachtrij() klasse uit wachtrijmodule.
- Last in First out Wachtrij: Hier komt het element dat als laatste is ingevoerd als eerste naar buiten. Om met LIFO te werken, moet u bellen LifoQueue() klasse uit de wachtrijmodule.
Python wachtrij Installatie
Het is heel gemakkelijk om met wachtrijen in Python te werken. Hier volgen de stappen die u moet volgen om gebruik te maken van de wachtrij in uw code.
Stap 1) U hoeft alleen maar 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 gaan werken. Er zijn 2 soorten wachtrijen: FIFO (first in first out) en LIFO (last in first out).
Stap 2) Om met FIFO wachtrij te werken, roept u de klasse Queue aan met behulp van de wachtrijmodule die is geïmporteerd zoals hieronder weergegeven:
import queue q1 = queue.Queue()
Stap 3) Om met de LIFO-wachtrij te werken, roept u de klasse LifoQueue() aan, zoals hieronder weergegeven:
import queue q1 = queue.LifoQueue()
Methoden beschikbaar binnen de wachtrij- en LifoQueue-klasse
Hieronder staan de belangrijke methoden die beschikbaar zijn in de klassen Queue en LifoQueue:
- plaats(item): Hierdoor wordt het item in de wachtrij geplaatst.
- krijgen(): Hiermee krijgt u een item uit de wachtrij terug.
- leeg(): Het retourneert true als de wachtrij leeg is en false als er items aanwezig zijn.
- qgrootte(): retourneert de grootte van de wachtrij.
- vol(): retourneert true als de wachtrij vol is, anders false.
Voorbeeld van First In First Out-wachtrij
In het geval van first-in-first-out zal het element dat als eerste gaat het eerst naar buiten komen.
Toevoegen en item in een wachtrij
Laten we aan een voorbeeld werken om een item aan een wachtrij toe te voegen. Om met de wachtrij te gaan werken, importeert u eerst de modulewachtrij, zoals weergegeven in het onderstaande voorbeeld.
Om een item toe te voegen, kunt u de put()-methode gebruiken, zoals weergegeven in het voorbeeld:
import queue q1 = queue.Queue() q1.put(10) #this will additem 10 to the queue.
Standaard is de grootte van de wachtrij oneindig en kunt u er een willekeurig aantal items aan toevoegen. Als u de grootte van de wachtrij wilt definiëren, kunt u dit als volgt doen
import queue q1 = 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.
Output:
True
Nu is de grootte van de wachtrij 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 zijn items uit de wachtrij toegestaan wanneer deze worden aangeroepen.
Het volgende voorbeeld laat zien hoe u een item uit de wachtrij verwijdert.
import queue
q1 = queue.Queue()
q1.put(10)
item1 = q1.get()
print('The item removed from the queue is ', item1)
Output:
The item removed from the queue is 10
Voorbeeld van wachtrij Last In First Out
In het geval van de laatste in de first out-wachtrij, zal het element dat als laatste wordt ingevoerd als eerste naar buiten komen.
Om met LIFO te werken, dat wil zeggen als laatste in de wachtrij die als eerste uitkomt, moeten we de wachtrijmodule importeren en gebruik maken van de LifoQueue()-methode.
Toevoegen en item in een wachtrij
Hier zullen we begrijpen hoe u een item aan de LIFO-wachtrij kunt toevoegen.
import queue q1 = queue.LifoQueue() q1.put(10)
U moet de methode put() op LifoQueue gebruiken, zoals weergegeven in het bovenstaande voorbeeld.
Verwijder een item uit de wachtrij
Om een item uit de LIFOqueue te verwijderen, kunt u gebruik maken van de get() methode.
import queue
q1 = queue.LifoQueue()
q1.put(10)
item1 = q1.get()
print('The item removed from the LIFO queue is ', item1)
Output:
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 kunt toevoegen en het item kunt verwijderen 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 FIFO-wachtrij
import queue
q1 = 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 FIFO-wachtrij
import queue
q1 = queue.Queue()
for i in range(20):
q1.put(i) # this will additem from 0 to 20 to the queue
while not q1.empty():
print("The value is ", q1.get()) # get() will remove the item from the queue.
Output:
The value is 0 The value is 1 The value is 2 The value is 3 The value is 4 The value is 5 The value is 6 The value is 7 The value is 8 The value is 9 The value is 10 The value is 11 The value is 12 The value is 13 The value is 14 The value is 15 The value is 16 The value is 17 The value is 18 The value is 19
Voeg een item toe aan een LIFOqueue
import queue
q1 = 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 LIFO-wachtrij
import queue
q1 = queue.LifoQueue()
for i in range(20):
q1.put(i) # this will additem from 0 to 20 to the queue
while not q1.empty():
print("The value is ", q1.get()) # get() will remove the item from the queue.
Output:
The value is 19 The value is 18 The value is 17 The value is 16 The value is 15 The value is 14 The value is 13 The value is 12 The value is 11 The value is 10 The value is 9 The value is 8 The value is 7 The value is 6 The value is 5 The value is 4 The value is 3 The value is 2 The value is 1 The value is 0
Sorteerwachtrij
Het volgende voorbeeld toont het sorteren van de wachtrij. Het algoritme dat voor het sorteren wordt gebruikt, is bubble sort.
import queue
q1 = queue.Queue()
#Addingitems to the queue
q1.put(11)
q1.put(5)
q1.put(4)
q1.put(21)
q1.put(3)
q1.put(10)
#using bubble sort on the queue
n = q1.qsize()
for i in range(n):
x = q1.get() # the element is removed
for j in range(n-1):
y = q1.get() # the element is removed
if x > y :
q1.put(y) #the smaller one is put at the start of the queue
else:
q1.put(x) # the smaller one is put at the start of the queue
x = y # the greater one is replaced with x and compared again with nextelement
q1.put(x)
while (q1.empty() == False):
print(q1.queue[0], end = " ")
q1.get()
Output:
3 4 5 10 11 21
Revwachtrij
Om de wachtrij om te keren, kunt u gebruik maken van een andere wachtrij en recursie.
Het volgende voorbeeld laat zien hoe u de wachtrij kunt omkeren.
Voorbeeld:
import queue
q1 = 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 recursion
q2dest.put(buffer)
return q2dest
q2dest = queue.Queue()
qReversed = reverseQueue(q1,q2dest)
while (qReversed.empty() == False):
print(qReversed.queue[0], end = " ")
qReversed.get()
Output:
10 3 21 4 5 11
Samenvatting
- Een wachtrij is een container die gegevens bevat. Er zijn twee soorten wachtrijen: FIFO en LIFO.
- Bij een FIFO (First in First out Queue) komt het element dat als eerste gaat als eerste naar buiten.
- Bij een LIFO (Last in First out Queue) komt het element dat als laatste wordt 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 get() methode gebruikt.
