Warteschlange

7.1 Definition der Warteschlange und ihre Eigenschaften

Warteschlange — ist eine abstrakte Datenstruktur, die eine geordnete Sammlung von Elementen darstellt, organisiert nach dem Prinzip "first in, first out" (FIFO). Eine Warteschlange kann man sich wie eine Schlange von Menschen im Geschäft vorstellen: Die erste Person in der Schlange wird zuerst bedient.

Eigenschaften der Warteschlange:

• FIFO (First In, First Out): Das erste hinzugefügte Element wird als erstes entfernt.
• Eingeschränkte Operationen: Die Warteschlange unterstützt einen eingeschränkten Satz von Operationen — Hinzufügen (enqueue), Entfernen (dequeue) und Betrachten (peek) des Elements an der Vorderseite.
• Einseitiger Zugang: Zugriff auf die Elemente ist nur von der Vorderseite (front) und der Rückseite (rear) möglich.
• Einfachheit der Implementierung: Eine Warteschlange kann einfach mit einem Array oder einer verketteten Liste implementiert werden.

Das FIFO-Prinzip:

• Hinzufügen eines Elements (enqueue): Ein neues Element wird am Ende der Warteschlange hinzugefügt.
• Entfernen eines Elements (dequeue): Das erste hinzugefügte Element wird vom Anfang der Warteschlange entfernt.
• Betrachten des vorderen Elements (peek): Ermöglicht das Betrachten des Elements an der Vorderseite der Warteschlange, ohne es zu entfernen.

Elemente der Warteschlange werden vom einen Ende (Rückseite) hinzugefügt und vom anderen Ende (Vorderseite) entfernt. So wird das erste hinzugefügte Element auch als erstes entfernt.

7.2 Grundlegende Operationen

Grundlegende Operationen: enqueue, dequeue, peek

Operation enqueue: Fügt ein neues Element am Ende der Warteschlange hinzu.

Zeitkomplexität: O(1).

from collections import deque

queue = deque()
queue.append(10)  # enqueue 10
queue.append(20)  # enqueue 20
print(queue)  # Ausgabe: deque([10, 20])

Operation dequeue: Entfernt und gibt das Element vom Beginn der Warteschlange zurück.

Zeitkomplexität: O(1).

from collections import deque

queue = deque()
queue.append(10)  # enqueue 10
queue.append(20)  # enqueue 20
print(queue)  # Ausgabe: deque([10, 20])

front_element = queue.popleft()  # dequeue
print(front_element)  # Ausgabe: 10
print(queue)  # Ausgabe: deque([20])

Operation peek: Gibt das Element an der Vorderseite der Warteschlange zurück, ohne es zu entfernen.

Zeitkomplexität: O(1).

from collections import deque

queue = deque()
queue.append(10)  # enqueue 10
queue.append(20)  # enqueue 20
print(queue)  # Ausgabe: deque([10, 20])

front_element = queue[0]  # peek
print(front_element)  # Ausgabe: 10

7.3 Anwendungsbeispiele von Warteschlangen

Schauen wir uns einige Anwendungsbeispiele für Warteschlangen an.

1 Verwaltung von Druckaufträgen

Eine Warteschlange wird zur Verwaltung von Druckaufträgen verwendet, bei der Dokumente in die Warteschlange hinzugefügt und in der Reihenfolge ihres Eingangs gedruckt werden.

class PrinterQueue:
    def __init__(self):
        self.queue = deque()

    def add_job(self, job):
        self.queue.append(job)

    def print_job(self):
        if self.queue:
            job = self.queue.popleft()
            print(f"Printing: {job}")

# Beispielverwendung:
printer_queue = PrinterQueue()
printer_queue.add_job("Document1.pdf")
printer_queue.add_job("Document2.pdf")
printer_queue.print_job()  # Ausgabe: Printing: Document1.pdf
printer_queue.print_job()  # Ausgabe: Printing: Document2.pdf

2 Verarbeitung von Anfragen auf einem Web-Server

Eine Warteschlange wird zur Verwaltung von Client-Anfragen verwendet, die an einen Web-Server gesendet werden. Anfragen werden in der Reihenfolge ihres Eingangs bearbeitet.

class RequestQueue:
    def __init__(self):
        self.queue = deque()

    def add_request(self, request):
        self.queue.append(request)

    def process_request(self):
        if self.queue:
            request = self.queue.popleft()
            print(f"Processing request: {request}")

# Beispielverwendung:
request_queue = RequestQueue()
request_queue.add_request("GET /index.html")
request_queue.add_request("POST /submit-form")
request_queue.process_request()  # Ausgabe: Processing request: GET /index.html
request_queue.process_request()  # Ausgabe: Processing request: POST /submit-form

3 Nachrichtenwarteschlange in Nachrichtenaustauschsystemen

Eine Warteschlange wird zur Verwaltung von Nachrichten in Informationsaustauschsystemen (z. B. in Message Brokers) verwendet. Nachrichten werden in der Reihenfolge ihres Eingangs bearbeitet.

class MessageQueue:
    def __init__(self):
        self.queue = deque()

    def send_message(self, message):
        self.queue.append(message)

    def receive_message(self):
        if self.queue:
            message = self.queue.popleft()
            print(f"Received message: {message}")

# Beispielverwendung:
message_queue = MessageQueue()
message_queue.send_message("Hello")
message_queue.send_message("World")
message_queue.receive_message()  # Ausgabe: Received message: Hello
message_queue.receive_message()  # Ausgabe: Received message: World