Wie ein Stapel ist die Warteschlange eine lineare Datenstruktur, die Elemente in einem First-In-First-Out-Prinzip speichert ( FIFO ) Benehmen. Bei einer Warteschlange wird das zuletzt hinzugefügte Element zuerst entfernt. Ein gutes Beispiel für eine Warteschlange ist eine beliebige Warteschlange von Verbrauchern für eine Ressource, bei der der Verbraucher, der zuerst kam, zuerst bedient wird.

Mit der Warteschlange verbundene Vorgänge sind:

• In die Warteschlange stellen: Fügt der Warteschlange ein Element hinzu. Wenn die Warteschlange voll ist, spricht man von einer Überlaufbedingung – Zeitkomplexität: O(1)
• Entsprechend: Entfernt ein Element aus der Warteschlange. Die Elemente werden in der gleichen Reihenfolge abgelegt, in der sie abgelegt werden. Wenn die Warteschlange leer ist, spricht man von einer Unterlaufbedingung – Zeitkomplexität: O(1)
• Vorderseite: Holen Sie sich das vordere Element aus der Warteschlange – Zeitkomplexität: O(1)
• Hinteren: Holen Sie sich das letzte Element aus der Warteschlange – Zeitkomplexität: O(1)

Implementieren Sie eine Warteschlange in Python

Es gibt verschiedene Möglichkeiten, eine Warteschlange zu implementieren Python. Dieser Artikel behandelt die Implementierung einer Warteschlange mithilfe von Datenstrukturen und Modulen aus der Python-Bibliothek. Python Queue kann auf folgende Weise implementiert werden:

• Liste
• Sammlungen.deque
• Schwanz.Schwanz

Implementierung mit Liste

List ist eine in Python integrierte Datenstruktur, die als Warteschlange verwendet werden kann. Anstelle von enqueue() und entsprechend () , append() Und Pop() Funktion verwendet wird. Allerdings sind Listen für diesen Zweck recht langsam, da das Einfügen oder Löschen eines Elements am Anfang das Verschieben aller anderen Elemente um eins erfordert, was O(n) Zeit erfordert.
Der Code simuliert eine Warteschlange mithilfe einer Python-Liste. Es fügt Elemente hinzu 'A' , 'B' , Und 'C' in die Warteschlange und entfernt sie dann aus der Warteschlange, was am Ende zu einer leeren Warteschlange führt. Die Ausgabe zeigt die anfängliche Warteschlange, Elemente aus der Warteschlange entfernt ( 'A' , 'B' , 'C' ) und der leere Zustand der Warteschlange.

Python3

Ausgabe:

Initial queue ['a', 'b', 'c'] Elements dequeued from queue a b c Queue after removing elements [] 

Traceback (most recent call last):  File '/home/ef51acf025182ccd69d906e58f17b6de.py', line 25, in   print(queue.pop(0)) IndexError: pop from empty list 

Implementierung mitcollections.deque

Die Warteschlange in Python kann mithilfe der Deque-Klasse aus dem Collections-Modul implementiert werden. In den Fällen, in denen wir schnellere Anhänge- und Pop-Operationen von beiden Enden des Containers benötigen, wird Deque gegenüber List bevorzugt, da Deque eine O(1)-Zeitkomplexität für Append- und Pop-Operationen bietet, im Vergleich zu List, die eine O(n)-Zeitkomplexität bietet . Anstelle von Enqueue und Deque werden die Funktionen append() und popleft() verwendet.
Der Code verwendet a deque> von dem collections> Modul zur Darstellung einer Warteschlange. Es hängt an 'A' , 'B' , Und 'C' in die Warteschlange und entfernt sie mit q.popleft()> , was zu einer leeren Warteschlange führt. Kommentieren q.popleft()> Nachdem die Warteschlange leer ist, wird eine ausgelöst IndexError> . Der Code demonstriert Warteschlangenvorgänge und behandelt ein Szenario mit leerer Warteschlange.

Python3

Ausgabe:

Initial queue deque(['a', 'b', 'c']) Elements dequeued from the queue a b c Queue after removing elements deque([]) 

Traceback (most recent call last):  File '/home/b2fa8ce438c2a9f82d6c3e5da587490f.py', line 23, in   q.popleft() IndexError: pop from an empty deque 

Implementierung mit queue.Queue

Queue ist ein integriertes Modul von Python, das zur Implementierung einer Warteschlange verwendet wird. queue.Queue(maxsize) initialisiert eine Variable auf die maximale Größe maxsize. Eine maximale Größe von Null „0“ bedeutet eine unendliche Warteschlange. Diese Warteschlange folgt der FIFO-Regel.
In diesem Modul stehen Ihnen verschiedene Funktionen zur Verfügung:

• maximale Größe – Anzahl der in der Warteschlange zulässigen Elemente.
• leer() – Gibt „True“ zurück, wenn die Warteschlange leer ist, andernfalls „False“.
• voll() – Gibt „True“ zurück, wenn sich in der Warteschlange Elemente mit maximaler Größe befinden. Wenn die Warteschlange mit maxsize=0 (Standardeinstellung) initialisiert wurde, gibt full() niemals True zurück.
• erhalten() – Entfernen Sie ein Element aus der Warteschlange und geben Sie es zurück. Wenn die Warteschlange leer ist, warten Sie, bis ein Artikel verfügbar ist.
• get_nowait() – Geben Sie einen Artikel zurück, wenn einer sofort verfügbar ist, andernfalls wird QueueEmpty ausgelöst.
• setzen(Artikel) – Einen Artikel in die Warteschlange stellen. Wenn die Warteschlange voll ist, warten Sie, bis ein freier Platz verfügbar ist, bevor Sie den Artikel hinzufügen.
• put_nowait(item) – Stellen Sie einen Artikel in die Warteschlange, ohne ihn zu blockieren. Wenn kein freier Slot sofort verfügbar ist, erhöhen Sie QueueFull.
• qsize() – Gibt die Anzahl der Elemente in der Warteschlange zurück.

Beispiel: Dieser Code verwendet die Queue> Klasse aus der queue> Modul. Es beginnt mit einer leeren Warteschlange und füllt sie mit „ A', 'B' , Und 'C' . Nach dem Entfernen aus der Warteschlange wird die Warteschlange leer und „1“ wird hinzugefügt. Obwohl es zuvor leer war, bleibt es voll, da die maximale Größe auf 3 festgelegt ist. Der Code demonstriert Warteschlangenvorgänge, einschließlich der Überprüfung auf Vollständigkeit und Leere.

Python3

Ausgabe:

0 Full: True Elements dequeued from the queue a b c Empty: True Empty: False Full: False