Warteschlangenimplementierung in Python

1. Warteschlangenimplementierung in Python
2. Fügen Sie der Warteschlange ein Element hinzu: Die Enqueue-Operation
3. Entfernen Sie ein Element aus der Warteschlange: Die Dequeue-Operation
4. Andere Operationen für Warteschlangen in Python
5. Warteschlangenimplementierung mit Listen in Python
6. Warteschlangenimplementierung mit verknüpften Listen in Python
7. Warteschlangenimplementierung mit dem Collections-Modul in Python
8. Effizienteste Warteschlangenimplementierung in Python

Wir verwenden Warteschlangen in Python, um First-In-First-Out-Operationen (FIFO) durchzuführen. In diesem Artikel werden drei verschiedene Möglichkeiten für die Warteschlangenimplementierung in Python erörtert.

Warteschlangenimplementierung in Python

In einer Warteschlange können wir verschiedene Operationen ausführen. Lassen Sie uns zuerst das allgemeine Konzept hinter allen Operationen besprechen, und danach werden wir die Warteschlangenoperationen mit verschiedenen Konstrukten implementieren.

Das erste Element in der Warteschlange wird als vorderes Element bezeichnet. In ähnlicher Weise wird das letzte Element der Warteschlange als hinteres Element bezeichnet.

Betrachten Sie beispielsweise die folgende Zahlenfolge als Warteschlange. 1 ist das vordere Element, während 6 das hintere Element ist.

1,2,3,4,5,6

Fügen Sie der Warteschlange ein Element hinzu: Die Enqueue-Operation

Bei der Enqueue-Operation fügen wir das Element in die Warteschlange ein, so wie sich eine Person an einem Ticketschalter in eine Warteschlange einreiht. Das neu hinzugefügte Element wird immer zum hinteren Element.

Wenn wir zum Beispiel die Zahl 7 zur oben angegebenen Warteschlange hinzufügen, sieht die Warteschlange wie folgt aus.

1,2,3,4,5,6,7

Es ist wichtig zu beachten, dass wir Elemente nur am Ende einer Warteschlange hinzufügen können.

Entfernen Sie ein Element aus der Warteschlange: Die Dequeue-Operation

Beim Dequeue-Vorgang entfernen wir das vordere Element der Warteschlange, so wie eine Person die Warteschlange verlässt, nachdem sie ihr Ticket am Ticketschalter erhalten hat.

Nach einer Dequeue-Operation wird das Front-Element aus der Warteschlange entfernt und das Element hinter dem Front-Element wird zum neuen Front-Element. Nach dem Dequeue-Vorgang sieht die im vorherigen Beispiel verwendete Warteschlange beispielsweise so aus.

2,3,4,5,6,7

Sie können das vordere Element nur in einem Dequeue-Vorgang entfernen. Warteschlangen folgen immer der First-in-First-out-Reihenfolge. Daher wird das zuerst der Warteschlange hinzugefügte Element auch zuerst entfernt.

Andere Operationen für Warteschlangen in Python

Wenn eine Warteschlange kein Element hat, wird sie als leer bezeichnet. Wir können verschiedene Ansätze verwenden, um zu bestimmen, ob eine Warteschlange in verschiedenen Implementierungen leer ist.

Manchmal müssen wir möglicherweise auch die Länge der Warteschlange ermitteln. Wir werden auch die Implementierung dieser Operation besprechen.

Warteschlangenimplementierung mit Listen in Python

Wir können Queues in Python am einfachsten mit Listen implementieren. Um eine Warteschlange mit Listen zu erstellen,

1. Wir definieren eine Klasse Queue mit drei Attributen.
2. Wir definieren eine leere Liste Daten, die die Elemente der Liste speichern wird.
3. Wir initialisieren zwei Variablen, vorne und hinten.
4. Wir initialisieren die Variablen auf -1 um anzuzeigen, dass die Warteschlange leer ist.

Code:

class Queue:
    def __init__(self):
        self.data = list()
        self.front = -1
        self.rear = -1

Beim Erstellen eines Queue-Objekts wird eine leere Liste erstellt und dem Attribut data zugewiesen. Die Liste speichert dann die Elemente der Warteschlange.

Nachdem wir die leere Warteschlange erstellt haben, implementieren wir verschiedene Operationen in der Warteschlange.

Überprüfen Sie, ob die Warteschlange in Python leer ist

Um zu überprüfen, ob die Warteschlange leer ist, können wir überprüfen, ob die Attribute vorne und hinten auf -1 initialisiert sind. Dazu definieren wir eine Methode isEmpty().

Die Methode isEmpty() prüft, wenn sie in einer Warteschlange aufgerufen wird, ob die vorderen und hinteren Attribute den Wert -1 haben. Wenn ja, wird True zurückgegeben, was bedeutet, dass die Warteschlange leer ist; andernfalls wird False zurückgegeben.

Code:

def isEmpty(self):
    if self.rear == -1 and self.front == -1:
        return True
    else:
        return False

Enqueue-Vorgang mit Listen in Python

Um ein Element in die Warteschlange einzufügen, prüfen wir zuerst, ob die Warteschlange leer ist. Wir können die oben definierte Methode isEmpty() verwenden.

1. Wenn die Warteschlange leer ist, fügen wir mit der Methode append() ein Element an die im Attribut data enthaltene Liste an. Wenn sie für eine Liste aufgerufen wird, nimmt die Methode append() ein Element als Eingabeargument und fügt es der Liste hinzu.
2. Da nun nur noch ein Element in der Liste vorhanden ist, aktualisieren wir die Werte der Attribute vorne und hinten auf 0. Sowohl das vordere als auch das hintere Element sind bei Index 0 in der Liste Daten vorhanden.
3. Wenn die Liste nicht leer ist, fügen wir das Element zuerst mit der Methode append() zur Liste hinzu.
4. Danach erhöhen wir den Wert im Attribut rear, um anzuzeigen, dass ein zusätzliches Element zur Warteschlange hinzugefügt wurde.

Bei der Enqueue-Operation wird der Wert des Attributs front nicht geändert, da wir kein Element aus der Warteschlange entfernen.

Die gesamte Operation kann wie folgt in Python implementiert werden.

Code:

def enQueue(self, element):
    if self.isEmpty():
        self.data.append(element)
        self.front = 0
        self.rear = 0
    else:
        self.data.append(element)
        self.rear += 1

Vorgang aus der Warteschlange mithilfe von Listen in Python entfernen

Wir werden zuerst prüfen, ob die Warteschlange für die Dequeue-Operation leer ist. Wenn ja, können wir nicht operieren; Andernfalls führen wir Folgendes aus.

1. Wir werden prüfen, ob es nur ein Element in der Warteschlange gibt. Wir können überprüfen, ob die Attribute front und rear denselben Wert haben und keines von ihnen -1 ist.
2. Wenn die Warteschlange nur ein Element hat, entfernen wir das Element am Index front der Warteschlange mit der Methode pop() und geben es an den Benutzer zurück. Dann aktualisieren wir die Attribute vorne und hinten auf -1, was anzeigt, dass die Warteschlange leer geworden ist.
3. Wenn keine der obigen Bedingungen True ist, hat die Warteschlange zwei oder mehr Elemente. In einem solchen Fall speichern wir das Element am Index front in einer temporären Variablen.
4. Danach erhöhen wir den Wert im Attribut front, was anzeigt, dass das nächste Element in der Liste zum front-Element geworden ist.
5. Schließlich geben wir den in der temporären Variablen gespeicherten Wert zurück.

Code:

def deQueue(self):
    if self.isEmpty():
        print("Queue is Empty. Cannot remove element")
    elif self.front == self.rear and self.front != -1:
        element = self.data[self.front]
        self.front = -1
        self.rear = -1
        return element
    else:
        element = self.data[self.front]
        self.front = self.front + 1
        return element

Ermitteln Sie die Länge der Warteschlange in Python

Um die Länge einer Warteschlange in Python zu ermitteln, können wir die folgenden Schritte ausführen.

1. Wenn die Warteschlange leer ist, ist die Länge der Warteschlange 0. Daher prüfen wir zuerst, ob die Warteschlange leer ist, indem wir die Methode isEmpty() verwenden.
2. Wenn die Methode isEmpty() True zurückgibt, geben wir 0 als Queue-Länge zurück.
3. Andernfalls wird die Länge der Liste als hinten-vorne+1 berechnet.

Wie unten gezeigt, haben wir dies in der Methode length() implementiert.

Code:

def length(self):
    if self.isEmpty():
        return 0
    return self.rear - self.front + 1

Wir haben alle Methoden implementiert. Lassen Sie uns nun alle Operationen einmal ausführen.

Vollständiger Code:

class Queue:
    def __init__(self):
        self.data = list()
        self.front = -1
        self.rear = -1

    def isEmpty(self):
        if self.rear == -1 and self.front == -1:
            return True
        else:
            return False

    def enQueue(self, element):
        if self.isEmpty():
            self.data.append(element)
            self.front = 0
            self.rear = 0
        else:
            self.data.append(element)
            self.rear += 1

    def deQueue(self):
        if self.isEmpty():
            print("Queue is Empty. Cannot remove element")
        elif self.front == self.rear and self.front != -1:
            element = self.data[self.front]
            self.front = -1
            self.rear = -1
            return element
        else:
            element = self.data[self.front]
            self.front = self.front + 1
            return element

    def length(self):
        return self.rear - self.front + 1


myQueue = Queue()
print("Enqueuing element 10")
myQueue.enQueue(10)
print("Queue Length is:", myQueue.length())
print("Enqueuing element 20")
myQueue.enQueue(20)
x = myQueue.deQueue()
print("dequeued element:", x)
print("Queue Length is:", myQueue.length())
y = myQueue.deQueue()
print("dequeued element:", y)
z = myQueue.deQueue()

Ausgang:

Enqueuing element 10
Queue Length is: 1
Enqueuing element 20
dequeued element: 10
Queue Length is: 1
dequeued element: 20
Queue is Empty. Cannot remove element

Im Beispiel haben wir einige Methoden nach der Queue-Implementierung in Python mithilfe von Listen ausgeführt. Sie können den Code kopieren, in Ihre IDE einfügen und mit dem Code experimentieren, um die Funktionsweise des Codes besser zu verstehen.

Warteschlangenimplementierung mit verknüpften Listen in Python

Wir haben bereits verschiedene Operationen auf verlinkten Listen in Python besprochen. Wir können auch verknüpfte Listenoperationen für die Warteschlangenimplementierung in Python verwenden.

Wir definieren zunächst einen Knoten mit zwei Attributen, nämlich data und next.

Code:

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

Wo:

• Das Attribut data wird verwendet, um Elemente der Warteschlange zu speichern.
• Das Attribut next wird verwendet, um auf das Element vor dem aktuellen Element in der Warteschlange zu zeigen.

Nachdem wir den Node definiert haben, definieren wir die Queue-Klasse, in der wir die Attribute front und rear haben.

Das Attribut front zeigt auf den Knoten, der das Element front in der verknüpften Liste der Warteschlange enthält. In ähnlicher Weise zeigt das Attribut hinten auf den Knoten, der das Element hinten in der verknüpften Liste enthält, die die Warteschlange enthält.

Die Attribute front und rear werden auf None initialisiert, da die Warteschlange leer ist.

Code:

class Queue:
    def __init__(self):
        self.front = None
        self.rear = None

Wenn die Klasse Queue initialisiert wird, enthält sie nur die Attribute front und rear mit dem Wert None.

Überprüfen Sie, ob die Warteschlange in Python leer ist

Um zu überprüfen, ob die Warteschlange leer ist, können wir überprüfen, ob die Attribute front und rear None sind. Wenn ja, können wir sagen, dass die Warteschlange leer ist.

Für diese Operation definieren wir die Methode isEmpty(). Wenn sie in einer Warteschlange aufgerufen wird, gibt die Methode isEmpty() True zurück, wenn die Warteschlange leer ist; andernfalls wird False zurückgegeben.

Code:

def isEmpty(self):
    if self.front is None:
        return True
    return False

Enqueue-Vorgang mit verknüpften Listen in Python

Um die Enqueue-Operation durchzuführen, prüfen wir zunächst, ob die Warteschlange leer ist. Wenn ja, weisen wir den Knoten mit dem neuen Element sowohl den Attributen vorne als auch hinten zu.

Andernfalls fügen wir das neue Element dem nächsten Knoten des hinteren Knotens hinzu. Danach machen wir den neuen Knoten zum hinteren Knoten.

Auf diese Weise wird das neue Element der Warteschlange hinzugefügt.

Code:

def enQueue(self, data):
    newNode = Node(data)
    if self.isEmpty():
        self.front = newNode
        self.rear = newNode
    else:
        self.rear.next = newNode

Dequeue-Operation mit verknüpften Listen in Python

Wir werden zuerst prüfen, ob die Warteschlange für die Dequeue-Operation leer ist. Wenn ja, sagen wir, dass ein Unterlauf aufgetreten ist, und wir können kein Element entfernen.

Andernfalls speichern wir die Daten zunächst in einer temporären Variablen im Knoten front.

Danach machen wir den nächsten Knoten des vorderen Knotens zum neuen vorderen Knoten. Dann löschen wir den in der temporären Variablen gespeicherten Frontknoten mit der Anweisung del.

Auf diese Weise wird der vorherige Frontknoten aus der Warteschlange gelöscht. Schließlich geben wir den im temporären Knoten gespeicherten Wert zurück.

Code:

def deQueue(self):
    if self.isEmpty():
        print("Queue is empty. Cannot remove element.")
    else:
        element = self.front
        nextFront = self.front.next
        self.front = nextFront
        value = element.data
        del element
        return value

Ermitteln Sie die Länge der Warteschlange in Python

1. Um die Länge der Warteschlange zu ermitteln, initialisieren wir zunächst eine Variable count auf 0.
2. Danach beginnen wir mit dem Durchlaufen der Warteschlange vom Knoten front mithilfe einer while-Schleife. Wir werden den count um 1 erhöhen, wenn wir zum nächsten Knoten gehen.
3. Sobald wir das Ende der Warteschlange erreicht haben, d. h. None, verlassen wir die while-Schleife.
4. Schließlich geben wir den Wert von count zurück, der die Länge der Warteschlange anzeigt.

Code:

def length(self):
    count = 0
    if self.front is None:
        return count
    else:
        temp = self.front
        while temp is not None:
            count += 1
            temp = temp.next
        return count

Wir haben alle Queue-Methoden mit verknüpften Listen implementiert. Lassen Sie uns nun die Operationen ausführen, um die Funktionsweise besser zu verstehen.

Vollständiger Code:

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None


class Queue:
    def __init__(self):
        self.front = None
        self.rear = None

    def isEmpty(self):
        if self.front is None:
            return True
        return False

    def enQueue(self, data):
        newNode = Node(data)
        if self.isEmpty():
            self.front = newNode
            self.rear = newNode
        else:
            self.rear.next = newNode

    def deQueue(self):
        if self.isEmpty():
            print("Queue is empty. Cannot remove element.")
        else:
            element = self.front
            nextFront = self.front.next
            self.front = nextFront
            value = element.data
            del element
            return value

    def length(self):
        count = 0
        if self.front is None:
            return count
        else:
            temp = self.front
            while temp is not None:
                count += 1
                temp = temp.next
            return count


myQueue = Queue()
print("Enqueuing element 10")
myQueue.enQueue(10)
print("Queue Length is:", myQueue.length())
print("Enqueuing element 20")
myQueue.enQueue(20)
x = myQueue.deQueue()
print("dequeued element:", x)
print("Queue Length is:", myQueue.length())
y = myQueue.deQueue()
print("dequeued element:", y)
z = myQueue.deQueue()

Ausgang:

Enqueuing element 10
Queue Length is: 1
Enqueuing element 20
dequeued element: 10
Queue Length is: 1
dequeued element: 20
Queue is empty. Cannot remove element.

Warteschlangenimplementierung mit dem Collections-Modul in Python

Wir können das Sammlungsmodul auch für die Warteschlangenimplementierung in Python verwenden.

Das Collections-Modul stellt die Klasse deque (doppelt beendete Warteschlange) bereit, um Warteschlangen und Stacks in Python zu implementieren. Sie können die Klasse deque in Ihr Programm importieren, indem Sie die nachstehende import-Anweisung verwenden.

from collections import deque

Wir werden eine Klasse Queue erstellen, um die Warteschlange zu implementieren. Wie unten gezeigt, erstellen wir ein deque-Objekt innerhalb der Klasse.

Code:

class Queue:
    def __init__(self):
        self.data = deque()

Wenn die Klasse Queue instanziiert wird, wird ein leeres deque-Objekt erstellt, um die Elemente der Warteschlange zu speichern.

Überprüfen Sie die Länge der Warteschlange in Python

Um die Länge der Warteschlange zu überprüfen, definieren wir eine length()-Methode. Innerhalb der length()-Methode berechnen wir die Länge des deque-Objekts mit der len()-Funktion.

Die len()-Funktion nimmt das deque-Objekt als Eingabe und gibt die deque-Länge zurück. Wir geben den Wert der Funktion len() als Länge der Warteschlange zurück, wie unten gezeigt.

Code:

def length(self):
    return len(self.data)

Überprüfen Sie, ob die Warteschlange in Python leer ist

Wenn die Länge der Warteschlange 0 ist, sagen wir, dass die Warteschlange leer ist. Wir können die Methode isEmpty() wie unten gezeigt definieren.

Code:

def isEmpty(self):
    if self.length() == 0:
        return True
    return False

Stellen Sie ein Element in Python in die Warteschlange

Wir werden die Methode enQueue() definieren, um ein Element einzureihen. Die Methode enQueue() nimmt das neue Element als Eingabeargument.

Innerhalb der enQueue()-Methode verwenden wir die append()-Methode, um das Element zum deque-Objekt hinzuzufügen. Die append()-Methode nimmt, wenn sie für das deque-Objekt aufgerufen wird, das neue Element als Eingabeargument und fügt es dem deque-Objekt hinzu.

Code:

def enQueue(self, x):
    self.data.append(x)

Dequeue-Vorgang in Python

Wir werden die Methode deQueue() definieren, um ein Element aus der Warteschlange zu entfernen. Innerhalb der Methode deQueue() rufen wir die Methode popleft() für das Objekt deque der Warteschlange auf.

Die popleft()-Methode entfernt, wenn sie für ein deque-Objekt aufgerufen wird, das vordere Element der deque. Es gibt auch das Element zurück, das aus der Warteschlange entfernt wurde.

Wir werden auch den von der Methode popleft() zurückgegebenen Wert von der Methode deQueue() mit einer return-Anweisung zurückgeben.

Code:

def deQueue(self):
    if self.isEmpty():
        print("Queue is empty. Cannot remove element.")
    else:
        return self.data.popleft()

Jetzt haben wir alle Methoden für die Warteschlangenimplementierung in Python mithilfe des Sammlungsmoduls implementiert. Lassen Sie uns die gesamte Ausführung beobachten.

Vollständiger Code:

from collections import deque


class Queue:
    def __init__(self):
        self.data = deque()

    def length(self):
        return len(self.data)

    def isEmpty(self):
        if self.length() == 0:
            return True
        return False

    def enQueue(self, x):
        self.data.append(x)

    def deQueue(self):
        if self.isEmpty():
            print("Queue is empty. Cannot remove element.")
        else:
            return self.data.popleft()


myQueue = Queue()
print("Enqueuing element 10")
myQueue.enQueue(10)
print("Queue Length is:", myQueue.length())
print("Enqueuing element 20")
myQueue.enQueue(20)
x = myQueue.deQueue()
print("dequeued element:", x)
print("Queue Length is:", myQueue.length())
y = myQueue.deQueue()
print("dequeued element:", y)
z = myQueue.deQueue()

Ausgang:

Enqueuing element 10
Queue Length is: 1
Enqueuing element 20
dequeued element: 10
Queue Length is: 1
dequeued element: 20
Queue is empty. Cannot remove element.

Effizienteste Warteschlangenimplementierung in Python

In diesem Artikel wurden drei Ansätze für die Warteschlangenimplementierung in Python erörtert.

Unter allen hier diskutierten Ansätzen ist die Verwendung von Listen zum Speichern der Warteschlangenelemente der schlechteste. Bei diesem Ansatz werden die Elemente niemals aus der Liste gelöscht.

Daher empfehlen wir Ihnen, es niemals in Ihren Programmen zu verwenden. Verwenden Sie es nur, wenn Sie ein Anfänger in Python sind und nichts über verknüpfte Listen wissen.

Wenn Sie keine externen Module verwenden dürfen, können Sie die Python-Warteschlangenimplementierung verwenden, die verknüpfte Listen verwendet, da sie zeit- und speichereffizient ist. Es ist jedoch langsamer als der Ansatz mit deque.

Für die effizienteste Warteschlangenimplementierung von Python sollten Sie den Modulansatz deque verwenden. Es hat die beste Effizienz in Bezug auf Zeit und Speicher, da der Quellcode für das Modul in C geschrieben ist und die Implementierung doppelt endende verkettete Listen verwendet, um das Objekt deque zu implementieren.

Wir hoffen, dass dieser Artikel Ihnen geholfen hat, die Warteschlangenimplementierung in Python zu verstehen. Bleiben Sie dran für weitere informative Artikel.