Python-Warteschlange: FIFO, LIFO-Beispiel

Was ist eine 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 die Python-Warteschlange?

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:

Python-Warteschlangenarbeit

Der Hinterrad stellt den Punkt dar, an dem die Elemente in die Warteschlange eingefügt werden. In diesem Beispiel ist 7 der Wert dafür.

Der Vorderrad 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).

Python-Warteschlangenarbeit

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

In Python gibt es hauptsächlich zwei Arten von Warteschlangen:

  • 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.

Installation der Python-Warteschlange

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

Following sind die wichtigen Methoden, die in der Queue- und LifoQueue-Klasse 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, andernfallswise falsch

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.

Die folgendenwing Das 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

Following Das Beispiel zeigt die Warteschlangensortierung. Der für die Sortierung verwendete Algorithmus ist die Blasensortierung.

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

Umkehrwarteschlange

Um die Warteschlange umzukehren, können Sie eine andere Warteschlange und eine Rekursion verwenden.

Die folgendenwing Beispiel zeigt, wie man die Warteschlange umkehrt.

Beispiel:

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.