Tutorial zur Python-Warteschlangendatenstruktur

Master-FIFO-Warteschlangenoperationen in Python. Führen Sie unser interaktives Warteschlangenbeispiel aus, das die Enqueue- und Dequeue-Methoden zeigt.

Versuchen Sie es im Editor

Übersicht

Eine Warteschlange ist eine lineare Datenstruktur, die nach dem First-In-First-Out-Prinzip (FIFO) arbeitet. Elemente werden hinten hinzugefügt (in die Warteschlange gestellt) und vorne entfernt (aus der Warteschlange entfernt), ähnlich wie bei einer Kasse in einem Geschäft.

Warteschlangen sind in der Informatik von entscheidender Bedeutung für die Bearbeitung von Aufgaben in der genauen Reihenfolge, in der sie eintreffen. Sie fungieren als Puffer, die Produzenten- und Konsumentenprozesse entkoppeln.

Python bietet mehrere Möglichkeiten zum Erstellen von Warteschlangen: Basislisten, das Modul „collections.deque“ für threadsichere schnelle Vorgänge und das Modul „queue.Queue“, das speziell für Multithread-Anwendungen entwickelt wurde.

Code- und Ausführungsausgabe

Eine interaktive FIFO-Warteschlange, die mithilfe von „collections.deque“ für effiziente Front-Removal-Vorgänge erstellt wurde.

queue_demo.py

Versuchen Sie es im Editor

from collections import deque

class Queue:
    def __init__(self):
        self.buffer = deque()
        
    def enqueue(self, item):
        self.buffer.append(item)
        print(f"Enqueued: {item}")
        
    def dequeue(self):
        if self.is_empty():
            return "Underflow: Queue is empty"
        dequeued = self.buffer.popleft()
        print(f"Dequeued: {dequeued}")
        return dequeued
        
    def is_empty(self):
        return len(self.buffer) == 0
        
    def size(self):
        return len(self.buffer)

# Test the Queue
q = Queue()
q.enqueue("Customer 1")
q.enqueue("Customer 2")
q.enqueue("Customer 3")

print(f"Queue Size: {q.size()}")
q.dequeue()
q.dequeue()

print(f"Remaining in Queue: {list(q.buffer)}")

Terminal-Ausgabe

Enqueued: Customer 1
Enqueued: Customer 2
Enqueued: Customer 3
Queue Size: 3
Dequeued: Customer 1
Dequeued: Customer 2
Remaining in Queue: ['Customer 3']

Schrittweise Umsetzung

Bearbeitung asynchroner Anfragen in Server-Web-Frameworks
Job-Scheduling-Warteschlangen in Betriebssystemen
Nachrichtenbroker und Warteschlangenpuffer (wie RabbitMQ oder Redis)

Häufig gestellte Fragen

Warum nicht list.pop(0) zum Entfernen aus der Warteschlange in Python verwenden?

Die Verwendung von „list.pop(0)“ ist langsam, da alle nachfolgenden Elemente im Speicher um einen Index nach links verschoben werden müssen, was zu einer O(n)-Leistung führt. Im Gegensatz dazu läuft „deque.popleft()“ in der konstanten Zeit O(1).

Was ist eine Prioritätswarteschlange?

Eine Prioritätswarteschlange ist eine Variante, bei der Elemente basierend auf einer zugehörigen Priorität und nicht auf der Grundlage der Ankunftsreihenfolge bereitgestellt werden. Python implementiert dies über das Modul „heapq“.