Python Warteschlange: FIFO, LIFO Beispiel
Logan Jung
Was ist Python Warteschlange?
Eine Warteschlange ist ein Container, der Daten enthält. Die zuerst eingegebenen Daten werden zuerst entfernt, weshalb eine Warteschlange auch „First in First Out“ (FIFO) genannt wird. Die Warteschlange hat vorne und hinten zwei Enden. Die Artikel werden von hinten eingegeben und von vorne entnommen.
Wie funktioniert Python Warteschlangenarbeit?
Die Warteschlange lässt sich leicht mit dem realen Beispiel vergleichen: Die Schlange von Menschen, die in einer Warteschlange am Ticketschalter stehen. Die Person, die zuerst steht, erhält zuerst das Ticket, gefolgt von der nächsten Person und so weiter. Die gleiche Logik gilt auch für die Warteschlangendatenstruktur.
Hier ist eine schematische Darstellung der Warteschlange:
Der Hinterreifen stellt den Punkt dar, an dem die Elemente in die Warteschlange eingefügt werden. In diesem Beispiel ist 7 der Wert dafür.
Der Vorderreifen stellt den Punkt dar, an dem die Elemente aus der Warteschlange entfernt werden. Wenn Sie ein Element aus der Warteschlange entfernen, erhalten Sie als erstes Element 1, wie in der Abbildung dargestellt.
Element 1 war das erste, das in die Warteschlange eingefügt wurde, und beim Entfernen ist es das erste, das wieder herauskommt. Daher heißt die Warteschlange FIRST IN FIRST OUT (FIFO).
In einer Warteschlange werden die Elemente der Reihe nach entfernt und können nicht zwischendurch entfernt werden. Sie können Element 5 einfach nicht zufällig aus der Warteschlange entfernen. Dazu müssen Sie alle Elemente vor 5 entfernen. Die Elemente in der Warteschlange werden in der Reihenfolge entfernt, in der sie eingefügt werden.
Arten von Warteschlangen in Python
Es gibt hauptsächlich zwei Arten von Warteschlangen in Python:
- First-in-First-out-Warteschlange: Dabei kommt das Element, das zuerst kommt, auch als erstes heraus. Um mit FIFO zu arbeiten, müssen Sie aufrufen Warteschlange() Klasse aus dem Warteschlangenmodul.
- Last-in-First-out-Warteschlange: Hier wird das zuletzt eingegebene Element als erstes ausgegeben. Um mit LIFO zu arbeiten, müssen Sie aufrufen LifoQueue() Klasse aus dem Queue-Modul.
Python Warteschlangeninstallation
Es ist sehr einfach, mit der Warteschlange in Python zu arbeiten. Hier sind die Schritte, die Sie befolgen müssen, um die Warteschlange in Ihrem Code zu nutzen.
Schritt 1) Sie müssen lediglich das Warteschlangenmodul importieren, wie unten gezeigt:
import queue
Das Modul ist standardmäßig mit Python verfügbar und Sie benötigen keine zusätzliche Installation, um mit der Warteschlange zu arbeiten. Es gibt zwei Arten von Warteschlangen-FIFO (First In First Out) und LIFO (Last In First Out).
Schritt 2) Um mit der FIFO-Warteschlange zu arbeiten, rufen Sie die Queue-Klasse mit dem importierten Warteschlangenmodul auf, wie unten gezeigt:
import queue q1 = queue.Queue()
Schritt 3) Um mit der LIFO-Warteschlange zu arbeiten, rufen Sie die Klasse LifoQueue() wie unten gezeigt auf:
import queue q1 = queue.LifoQueue()
In der Queue- und LifoQueue-Klasse verfügbare Methoden
Im Folgenden sind die wichtigen Methoden aufgeführt, die in den Klassen Queue und LifoQueue verfügbar sind:
- put(item): Dadurch wird das Element in die Warteschlange gestellt.
- erhalten(): Dadurch erhalten Sie einen Artikel aus der Warteschlange zurück.
- leer(): Es wird „true“ zurückgegeben, wenn die Warteschlange leer ist, und „false“, wenn Elemente vorhanden sind.
- qsize(): gibt die Größe der Warteschlange zurück.
- voll(): Gibt „true“ zurück, wenn die Warteschlange voll ist, andernfalls „false“.
Beispiel für eine First-In-First-Out-Warteschlange
Beim First-In-First-Out-Prinzip ist das Element, das zuerst kommt, auch das erste, das herauskommt.
Fügen Sie ein Element zu einer Warteschlange hinzu
Lassen Sie uns an einem Beispiel arbeiten, um ein Element zu einer Warteschlange hinzuzufügen. Um mit der Warteschlange zu arbeiten, importieren Sie zunächst die Modulwarteschlange, wie im folgenden Beispiel gezeigt.
Um ein Element hinzuzufügen, können Sie die Methode put() verwenden, wie im Beispiel gezeigt:
import queue q1 = queue.Queue() q1.put(10) #this will additem 10 to the queue.
Standardmäßig ist die Größe der Warteschlange unendlich und Sie können ihr beliebig viele Elemente hinzufügen. Wenn Sie die Größe der Warteschlange definieren möchten, können Sie dies wie folgt tun
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.
Ausgang:
True
Jetzt beträgt die Größe der Warteschlange 5, es werden nicht mehr als 5 Elemente benötigt und die Methode q1.full() gibt true zurück. Durch das Hinzufügen weiterer Elemente wird der Code nicht weiter ausgeführt.
Entfernen Sie ein Element aus der Warteschlange
Um ein Element aus der Warteschlange zu entfernen, können Sie die Methode get() verwenden. Diese Methode lässt beim Aufruf Elemente aus der Warteschlange zu.
Das folgende Beispiel zeigt, wie ein Element aus der Warteschlange entfernt wird.
import queue
q1 = queue.Queue()
q1.put(10)
item1 = q1.get()
print('The item removed from the queue is ', item1)
Ausgang:
The item removed from the queue is 10
Beispiel einer „Last In First Out“-Warteschlange
Im Falle des letzten Eintrags in der First-Out-Warteschlange wird das zuletzt eingegebene Element als erstes ausgegeben.
Um mit LIFO zu arbeiten, also als Letzter in der ersten Ausgangswarteschlange, müssen wir das Warteschlangenmodul importieren und die Methode LifoQueue() verwenden.
Fügen Sie ein Element zu einer Warteschlange hinzu
Hier erfahren Sie, wie Sie ein Element zur LIFO-Warteschlange hinzufügen.
import queue q1 = queue.LifoQueue() q1.put(10)
Sie müssen die put()-Methode für LifoQueue verwenden, wie im obigen Beispiel gezeigt.
Entfernen Sie ein Element aus der Warteschlange
Um ein Element aus der LIFOqueue zu entfernen, können Sie die Methode get() verwenden.
import queue
q1 = queue.LifoQueue()
q1.put(10)
item1 = q1.get()
print('The item removed from the LIFO queue is ', item1)
Ausgang:
The item removed from the LIFO queue is 10
Fügen Sie einer Warteschlange mehr als ein Element hinzu
In den obigen Beispielen haben wir gesehen, wie man ein einzelnes Element für FIFO und LIFOqueue hinzufügt und entfernt. Jetzt werden wir sehen, wie man mehr als ein Element hinzufügt und auch entfernt.
Fügen Sie ein Element in eine FIFO-Warteschlange ein
import queue
q1 = queue.Queue()
for i in range(20):
q1.put(i) # this will additem from 0 to 20 to the queue
Entfernen Sie ein Element aus der FIFO-Warteschlange
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.
Ausgang:
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
Fügen Sie ein Element in eine LIFO-Warteschlange ein
import queue
q1 = queue.LifoQueue()
for i in range(20):
q1.put(i) # this will additem from 0 to 20 to the queue
Entfernen Sie ein Element aus der LIFOqueue
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.
Ausgang:
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
Sortierwarteschlange
Das folgende Beispiel zeigt die Warteschlangensortierung. Der zum Sortieren verwendete Algorithmus ist Bubblesort.
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()
Ausgang:
3 4 5 10 11 21
RevWarteschlange
Um die Warteschlange umzukehren, können Sie eine andere Warteschlange und eine Rekursion verwenden.
Das folgende Beispiel zeigt, wie die Warteschlange umgekehrt wird.
Ejemplo:
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()
Ausgang:
10 3 21 4 5 11
Zusammenfassung
- Eine Warteschlange ist ein Container, der Daten enthält. Es gibt zwei Arten von Warteschlangen: FIFO und LIFO.
- Bei einer FIFO-Warteschlange (First in First out Queue) kommt das Element, das zuerst geht, auch als erstes heraus.
- Bei einer LIFO-Warteschlange (Last in First out Queue) wird das zuletzt eingegebene Element als erstes ausgegeben.
- Ein Element in einer Warteschlange wird mithilfe der Methode put(item) hinzugefügt.
- Um ein Element zu entfernen, wird die Methode get() verwendet.
