Datenstrukturen spielen in der Programmierwelt eine Schlüsselrolle. Sie helfen uns, unsere Daten so zu organisieren, dass sie effizient genutzt werden können. Die Warteschlange ist eine der einfachsten verfügbaren Datenstrukturen.
In diesem Artikel erfahren wir mehr über die Warteschlange und ihre Implementierung in Python.
Inhaltsverzeichnis
Was ist eine Warteschlange?
Eine Warteschlange ist eine lineare Datenstruktur, die dem First In/First Out (FIFO)-Prinzip folgt. Es ist das Gegenteil der Stack-Datenstruktur.
Wir können die Warteschlange mit einer realen Warteschlange an der Kinokasse vergleichen. Sehen wir uns die Abbildung einer Warteschlange wie folgt an.
Wenn Sie die Warteschlange am Schalter beobachten, kann die zweite Person erst zum Schalter gehen, nachdem die erste Person ihre Arbeit beendet hat. Hier kommt die erste Person an die Theke und dann die zweite Person. Hier folgt man also dem FIFO-Prinzip (First In/First Out). Wer zuerst kommt, wird die Arbeit zuerst erledigen. Wir können eine ähnliche Art von Warteschlangen in unserem täglichen Leben beobachten.
Die Datenstruktur der Warteschlange folgt ebenfalls demselben Prinzip. Jetzt wissen Sie, was Warteschlangen sind und wie sie funktionieren. Sehen wir uns die Operationen an, die an einer Warteschlangendatenstruktur ausgeführt werden können.
Operationen in der Warteschlange
Ähnlich wie beim Stapeln finden wir zwei Hauptoperationen in einer Warteschlangendatenstruktur.
einreihen (Daten)
Fügt der Warteschlange am Ende neue Daten hinzu. Die Seite wird als Rückseite bezeichnet.
aus der Warteschlange entfernen ()
Entfernt Daten vom Anfang der Warteschlange. Die Seite wird als Vorderseite bezeichnet.
Sehen wir uns zum besseren Verständnis die Abbildungen der Warteschlangenoperationen an. Ein Bild sagt mehr als tausend Worte.
Wir können einige Hilfsfunktionen schreiben, um mehr Informationen über die Warteschlange zu erhalten. Die Anzahl der Hilfsfunktionen, die Ihnen zur Verfügung stehen, ist unbegrenzt. Bleiben wir vorerst bei den wichtigsten einmal genannten.
Rückseite()
Gibt das erste Element vom Ende der Warteschlange zurück.
Vorderseite()
Gibt das erste Element vom Beginn der Warteschlange zurück.
ist leer()
Gibt zurück, ob die Warteschlange leer ist oder nicht.
Ist es Ihnen nicht langweilig? Ich meine die konzeptionellen Themen.
Für mich ja!
Aber wir können nichts tun, ohne die Konzepte zu kennen. Wir müssen es vor der Implementierung vollständig kennen. Keine Sorge, es ist an der Zeit, uns mit etwas Code die Hände schmutzig zu machen.
Ich nehme an, Sie haben Python auf Ihrem PC installiert, wenn nicht, können Sie auch den Online-Compiler ausprobieren.
Warteschlangenimplementierung
Die Implementierung einer Warteschlange dauert für einen Programmierer nicht länger als 15 Minuten. Sobald Sie es gelernt haben, werden Sie es sagen. Vielleicht können Sie es innerhalb von Minuten nach diesem Tutorial implementieren.
Es gibt mehrere Möglichkeiten, die Warteschlange in Python zu implementieren. Sehen wir uns Schritt für Schritt verschiedene Warteschlangenimplementierungen an.
#1. Aufführen
Die Liste ist ein eingebauter Datentyp in Python. Wir werden den Listendatentyp verwenden, um eine Warteschlange in einer Klasse zu implementieren. Wir führen Sie durch verschiedene Schritte, um die Warteschlangendatenstruktur von Grund auf ohne Module zu implementieren. Lassen Sie uns hineinspringen.
Schritt 1:
Schreiben Sie eine Klasse namens Queue.
class Queue: pass
Schritt 2:
Es muss eine Variable geben, um die Daten der Warteschlange in der Klasse zu speichern. Nennen wir es Elemente. Und es ist natürlich eine Liste.
class Queue: def __init__(self): self.elements = []
Schritt 3:
Um Daten in die Warteschlange einzufügen, benötigen wir eine Methode in der Klasse. Die Methode heißt enqueue, wie wir bereits im vorherigen Abschnitt des Tutorials besprochen haben.
Die Methode nimmt einige Daten und fügt sie der Warteschlange (Elemente) hinzu. Wir können die Append-Methode des Listendatentyps verwenden, um Daten am Ende der Warteschlange hinzuzufügen.
class Queue: # ... def enqueue(self, data): self.elements.append(data) return data
Schritt 4:
Die Warteschlange muss einen Ausgang haben. Und das nennt man Dequeue. Ich denke, Sie haben bereits erraten, dass wir die Pop-Methode des Listendatentyps verwenden werden. Ob Sie es erraten haben oder nicht, Prost!
Die Methode pop vom Datentyp list löscht ein Element aus der Liste des angegebenen Indexes. Wenn wir keinen Index angegeben haben, wird das letzte Element der Liste gelöscht.
Hier müssen wir das erste Element der Liste löschen. Also müssen wir den Index 0 an die Pop-Methode übergeben.
class Queue: # ... def dequeue(self): return self.elements.pop(0)
Das reicht für eine Warteschlange. Aber wir brauchen die Hilfsfunktionen, um zu testen, ob die Warteschlangenoperationen richtig funktionieren oder nicht. Lassen Sie uns auch die Hilfsfunktionen schreiben.
Schritt 5:
Die Methode rear() wird verwendet, um das letzte Element der Warteschlange zu erhalten. Die negative Indizierung im Listendatentyp hilft uns, das letzte Element der Warteschlange zu erhalten.
class Queue: # ... def rear(self): return self.elements[-1]
Schritt 6:
Die Methode front() wird verwendet, um das erste Element der Warteschlange zu erhalten. Wir können das erste Element der Warteschlange mithilfe des Listenindex abrufen.
class Queue: # ... def front(self): return self.elements[0]
Schritt 7:
Mit der Methode is_empty() wird überprüft, ob die Warteschlange leer ist oder nicht. Wir können die Länge der Liste überprüfen.
class Queue: # ... def is_empty(self): return len(self.elements) == 0
Puh! vervollständigte den Implementierungsteil der Warteschlangendatenstruktur. Wir müssen ein Objekt erstellen, das die Queue-Klasse verwenden kann.
Machen wir das.
class Queue: # ... if __name__ == '__main__': queue = Queue()
Jetzt haben wir ein Queue-Objekt. Testen wir es mit einer Reihe von Operationen.
- Prüfen Sie mit der is_empty-Methode, ob die Warteschlange leer ist oder nicht. Es sollte True zurückgeben.
- Fügen Sie die Nummern 1, 2, 3, 4, 5 mit der Methode enqueue in die Warteschlange ein.
- Die Methode is_empty sollte False zurückgeben. Prüfen Sie.
- Drucken Sie die vorderen und hinteren Elemente jeweils mit der vorderen und hinteren Methode.
- Entfernen Sie das Element mit der Dequeue-Methode aus der Warteschlange.
- Überprüfen Sie das vordere Element. Es sollte das Element 2 zurückgeben.
- Entfernen Sie nun alle Elemente aus der Warteschlange.
- Die is_empty-Methode sollte True zurückgeben. Prüfen Sie.
Ich denke, das reicht aus, um unsere Warteschlangenimplementierung zu testen. Schreiben Sie den Code für jeden oben erwähnten Schritt, um die Warteschlange zu testen.
Hast du den Code geschrieben?
Nein, keine Sorge.
Überprüfen Sie den folgenden Code.
class Queue: def __init__(self): self.elements = [] def enqueue(self, data): self.elements.append(data) return data def dequeue(self): return self.elements.pop(0) def rear(self): return self.elements[-1] def front(self): return self.elements[0] def is_empty(self): return len(self.elements) == 0 if __name__ == '__main__': queue = Queue() ## checking is_empty method -> True print(queue.is_empty()) ## adding the elements queue.enqueue(1) queue.enqueue(2) queue.enqueue(3) queue.enqueue(4) queue.enqueue(5) ## again checking is_empty method -> False print(queue.is_empty()) ## printing the front and rear elements using front and rear methods respectively -> 1, 5 print(queue.front(), end=' ') print(queue.rear()) ## removing the element -> 1 queue.dequeue() ## checking the front and rear elements using front and rear methods respectively -> 2 5 print(queue.front(), end=' ') print(queue.rear()) ## removing all the elements queue.dequeue() queue.dequeue() queue.dequeue() queue.dequeue() ## checking the is_empty method for the last time -> True print(queue.is_empty())
Ich denke, Sie führen das obige Programm aus. Sie können eine Ausgabe ähnlich dem folgenden Ergebnis erhalten.
True False 1 5 2 5 True
Wir können den Listendatentyp direkt als Warteschlangendatenstruktur verwenden. Die obige Implementierung der Warteschlange hilft Ihnen, die Warteschlangenimplementierung in anderen Programmiersprachen besser zu verstehen.
Sie können die obige Klassenimplementierung einer Warteschlange auch in einem anderen Programm eines Projekts verwenden, indem Sie einfach das Objekt wie zuvor erstellen.
Wir haben die Warteschlange von Grund auf mit dem Listendatentyp implementiert. Gibt es integrierte Module für die Warteschlange? Ja! Wir haben eingebaute Warteschlangenimplementierungen. Lass sie uns sehen.
#2. Deque aus Sammlungen
Sie ist als doppelseitige Warteschlange implementiert. Da es das Hinzufügen und Entfernen von Elementen von beiden Seiten unterstützt, können wir es als Stapel und Warteschlange verwenden. Sehen wir uns die Warteschlangenimplementierung mit Dequeue an.
Es wird unter Verwendung anderer Datenstrukturen implementiert, die als doppelt verknüpfte Liste bezeichnet werden. Die Leistung beim Einfügen und Löschen von Elementen ist also konsistent. Der Zugriff auf Elemente aus der mittleren verknüpften Liste dauerte O(n) Zeit. Wir können es als Warteschlange verwenden, da auf die mittleren Elemente aus der Warteschlange nicht zugegriffen werden muss.
Schauen wir uns die verschiedenen Methoden an, die uns die Dequeue bietet.
- append(data) – wird verwendet, um die Daten zur Warteschlange hinzuzufügen
- popleft() – wird verwendet, um das erste Element aus der Warteschlange zu entfernen
Es gibt keine alternativen Methoden für front, rear und is_empty. Wir können die gesamte Warteschlange anstelle der Vorder- und Rückseite drucken. Als nächstes können wir die Methode len verwenden, um zu prüfen, ob die Warteschlange leer ist oder nicht.
Wir haben eine Reihe von Schritten befolgt, um die Warteschlangenimplementierung im vorherigen zu testen. Lassen Sie uns auch hier die gleiche Reihe von Schritten befolgen.
from collections import deque ## creating deque object queue = deque() ## checking whether queue is empty or not -> True print(len(queue) == 0) ## pushing the elements queue.append(1) queue.append(2) queue.append(3) queue.append(4) queue.append(5) ## again checking whether queue is empty or not -> False print(len(queue) == 0) ## printing the queue print(queue) ## removing the element -> 1 queue.popleft() ## printing the queue print(queue) ## removing all the elements queue.popleft() queue.popleft() queue.popleft() queue.popleft() ## checking the whether queue is empty or not for the last time -> True print(len(queue) == 0)
Sie erhalten ein Ergebnis ähnlich der folgenden Ausgabe.
True False deque([1, 2, 3, 4, 5]) deque([2, 3, 4, 5]) True
#3. Warteschlange von Warteschlange
Python hat ein eingebautes Modul namens queue, das eine Klasse namens Queue für die Warteschlangenimplementierung bereitstellt. Es ist ähnlich wie das, was wir zuvor implementiert haben.
Lassen Sie uns zunächst verschiedene Methoden der Queue-Klasse auschecken.
- put(data) – fügt die Daten der Warteschlange hinzu oder schiebt sie in die Warteschlange
- get() – entfernt das erste Element aus der Warteschlange und gibt es zurück
- empty() – gibt zurück, ob der Stack leer ist oder nicht
- qsize() – gibt die Länge der Warteschlange zurück.
Lassen Sie uns die Warteschlange mit den obigen Methoden implementieren.
from queue import Queue
## creating Queue object
queue_object = Queue()
## checking whether queue is empty or not -> True
print(queue_object.empty())
## adding the elements
queue_object.put(1)
queue_object.put(2)
queue_object.put(3)
queue_object.put(4)
queue_object.put(5)
## again checking whether queue is empty or not -> False
print(queue_object.empty())
## removing all the elements
print(queue_object.get())
print(queue_object.get())
print(queue_object.get())
## checking the queue size
print("Size", queue_object.qsize())
print(queue_object.get())
print(queue_object.get())
## checking the whether queue_object is empty or not for the last time -> True
print(queue_object.empty())
Überprüfen Sie die Ausgabe des obigen Codes.
True False 1 2 3 Size 2 4 5 True
Es gibt einige andere Methoden in der Queue-Klasse. Sie können sie mit der eingebauten dir-Funktion erkunden.
Fazit
Ich hoffe, Sie haben etwas über die Warteschlangendatenstruktur und ihre Implementierung erfahren. Das war’s für die Warteschlange. Sie können die Warteschlange an verschiedenen Stellen verwenden, an denen in FIFO-Reihenfolge (First In/First Out) verarbeitet werden muss. Verwenden Sie die Warteschlange bei der Problemlösung, wann immer Sie den Fall erhalten, um sie zu verwenden.
Sind Sie daran interessiert, Python zu beherrschen? Sehen Sie sich diese Lernressourcen an.
Viel Spaß beim Programmieren 🙂 👨💻