Warteschlangen und verkettete Listen in C: Movie-Ticketing-Queue Tutorial

Einführung in Warteschlangen und verkettete Listen in C

Warteschlangen (Queues) sind eine fundamentale Datenstruktur in der Informatik, die nach dem FIFO-Prinzip (First In, First Out) funktioniert. Besonders in Simulationen, wie einer Movie-Ticketing-Queue, ist die effiziente Verwaltung von Kundendaten entscheidend. In diesem Tutorial lernst du, wie du eine Warteschlange mit einer einfach verketteten Liste in C implementierst. Dieses Wissen ist nicht nur für dein COP3502C Assignment relevant, sondern auch für viele reale Anwendungen – von der Auftragsabwicklung in Online-Shops bis hin zur Verwaltung von Prozessen in Betriebssystemen.

Stell dir vor, du entwickelst ein System für ein Kino, das Kunden in verschiedene Warteschlangen einteilt, ähnlich wie bei einem Ticketverkauf für einen Blockbuster-Film. Die Herausforderung: Kunden kommen zu unterschiedlichen Zeiten an, kaufen unterschiedlich viele Tickets, und die Bearbeitungszeit variiert. Genau diese Szenario bildet die Grundlage für dein Assignment. Mit einer Queue als verkettete Liste kannst du dynamisch Kunden hinzufügen und entfernen, ohne die Begrenzungen eines Arrays.

Grundlagen: Was ist eine Queue und wie funktioniert sie?

Eine Queue ist eine lineare Datenstruktur, bei der Elemente nur am Ende (enqueue) hinzugefügt und am Anfang (dequeue) entfernt werden. Stell dir eine Schlange an einer Kinokasse vor: Der erste Kunde, der ankommt, wird zuerst bedient. In der Informatik wird dieses Prinzip oft für Aufgaben wie Task Scheduling oder Datenpufferung verwendet.

Für dein Assignment benötigst du eine Queue für jede der 13 möglichen Warteschlangen (nummeriert 0 bis 12). Jede Queue speichert Kunden mit Name, Ticketanzahl und Ankunftszeit. Die Implementierung erfolgt über eine einfach verkettete Liste, bei der jeder Knoten (Node) einen Kunden repräsentiert und auf den nächsten Knoten zeigt.

Verkettete Liste in C: Struktur und Grundoperationen

Eine verkettete Liste besteht aus Knoten, die dynamisch allokiert werden. Jeder Knoten enthält die Daten und einen Zeiger auf den nächsten Knoten. Hier ist die typische Definition in C:

typedef struct Node {
    char name[51];
    int tickets;
    int arrivalTime;
    struct Node* next;
} Node;

Für die Queue benötigst du zusätzlich einen Zeiger auf den vordersten und hintersten Knoten:

typedef struct Queue {
    Node* front;
    Node* rear;
} Queue;

Die grundlegenden Operationen sind enqueue (Einfügen am Ende) und dequeue (Entfernen vom Anfang). Hier eine Beispielimplementierung:

void enqueue(Queue* q, char* name, int tickets, int arrivalTime) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    strcpy(newNode->name, name);
    newNode->tickets = tickets;
    newNode->arrivalTime = arrivalTime;
    newNode->next = NULL;
    if (q->rear == NULL) {
        q->front = q->rear = newNode;
    } else {
        q->rear->next = newNode;
        q->rear = newNode;
    }
}

Node* dequeue(Queue* q) {
    if (q->front == NULL) return NULL;
    Node* temp = q->front;
    q->front = q->front->next;
    if (q->front == NULL) q->rear = NULL;
    return temp;
}

Diese Funktionen bilden das Herzstück deiner Queue-Implementierung. Achte darauf, dass du nach der Nutzung der Knoten den Speicher freigibst, um Memory Leaks zu vermeiden.

Assignment-spezifische Anforderungen: Queue-Nummer und Booth-Zuordnung

In deinem Assignment wird jedem Kunden basierend auf dem Anfangsbuchstaben seines Namens eine Queue-Nummer zugewiesen. Die Regel lautet: p % 13, wobei p die Position des Buchstabens im Alphabet ist (A=0, B=1, ..., Z=25). Ist das Ergebnis 0, wird der Kunde der Queue mit den wenigsten Kunden zugewiesen (unter den nicht-leeren Queues).

Die nicht-leeren Queues werden dann gleichmäßig auf die Booths (Schalter) verteilt. Jeder Booth bedient eine bestimmte Anzahl von Queues. Die Verteilung erfolgt nach dem Prinzip: Jeder Booth bekommt mindestens floor(k / b) Queues zugewiesen, wobei k die Anzahl der nicht-leeren Queues und b die Anzahl der Booths ist. Die restlichen Queues werden auf die ersten Booths verteilt.

Ein Beispiel: Bei 8 nicht-leeren Queues und 3 Booths bekommt Booth 1 drei Queues, Booth 2 drei Queues und Booth 3 zwei Queues. Die Reihenfolge der Queues ist aufsteigend nach ihrer Nummer.

Simulation der Kundenverarbeitung

Sobald die Booths festgelegt sind, beginnt die Simulation. Jeder Booth hat eine eigene Warteschlange, die aus den Kunden seiner zugewiesenen Queues besteht. Die Kunden werden in der Reihenfolge ihrer Ankunftszeit verarbeitet – ähnlich wie bei einem Live-Ticketing-Event, bei dem die ersten Kunden zuerst bedient werden.

Die Bearbeitungszeit pro Kunde beträgt: 30 + (Anzahl Tickets * 5) Sekunden. Der Booth beginnt mit der Bearbeitung, sobald der erste Kunde ankommt. Die Checkout-Zeit ist die Ankunftszeit plus die Bearbeitungszeit, wobei die Ankunftszeit des nächsten Kunden möglicherweise später liegt, sodass der Booth warten muss.

Um dies zu simulieren, musst du für jeden Booth die Kunden aus seinen Queues in einer einzigen Liste zusammenführen, sortiert nach Ankunftszeit. Da die Kunden in jeder Queue bereits chronologisch sortiert sind, kannst du einen Merge-ähnlichen Ansatz verwenden: Vergleiche die vordersten Kunden aller Queues und wähle den mit der frühesten Ankunftszeit.

Implementierungstipps für dein C-Programm

Hier sind einige bewährte Vorgehensweisen, die dir helfen, das Assignment erfolgreich zu lösen:

Dynamische Speicherverwaltung: Verwende malloc und free konsequent. Vergiss nicht, nach der Simulation alle Knoten und Queues freizugeben.
Effiziente Queue-Verwaltung: Verwende ein Array von Queues (Größe 13). Initialisiere alle Queues mit front = rear = NULL.
Eingabe einlesen: Nutze scanf wie in der Aufgabenstellung beschrieben. Die Eingabe ist bereits nach Ankunftszeit sortiert.
Queue-Nummer bestimmen: Berechne p = name[0] - 'A' und dann q = p % 13. Falls q == 0, suche die nicht-leere Queue mit den wenigsten Elementen.
Booth-Zuordnung: Bestimme zunächst alle nicht-leeren Queues. Sortiere sie aufsteigend. Verteile sie dann auf die Booths, indem du die Queues in Blöcke aufteilst.
Simulation pro Booth: Für jeden Booth erstellst du eine temporäre Priority Queue (oder eine verkettete Liste, die du sortiert einfügst), um die Kunden aus den zugewiesenen Queues nach Ankunftszeit zu ordnen. Da die Queues bereits sortiert sind, kannst du einen Merge-Ansatz verwenden.

Häufige Fehler und wie du sie vermeidest

Viele Studenten machen Fehler bei der dynamischen Speicherverwaltung oder der Logik der Queue-Zuweisung. Hier sind die häufigsten Stolperfallen:

Vergessen, Speicher freizugeben: Führe nach der Simulation eine Funktion freeQueue aus, die alle Knoten einer Queue löscht.
Falsche Behandlung von p%13 == 0: Stelle sicher, dass du die Queue mit den wenigsten Kunden auswählst, nicht die Queue 0 selbst (da Queue 0 nicht existiert, da die Nummern 1-12 verwendet werden).
Sortierung der Kunden pro Booth: Die Kunden aus verschiedenen Queues müssen nach Ankunftszeit sortiert werden. Verwende einen Merge-Ansatz, da die Queues intern sortiert sind.
Ausgabeformat: Achte auf das genaue Format: CUSTOMER from line X checks out at time T. mit einem Punkt am Ende und einer Leerzeile nach jedem Booth.

Erweiterte Konzepte: Priority Queue und Simulation

Obwohl die Aufgabenstellung eine einfache Queue verwendet, kannst du das Prinzip auf eine Priority Queue erweitern, bei der Kunden nach Dringlichkeit sortiert werden. Dies ist nützlich für Simulationen von Notaufnahmen oder Flugbuchungssystemen. In deinem Fall reicht jedoch die FIFO-Queue aus.

Ein interessanter Trend ist die Verwendung von Warteschlangen in KI-gesteuerten Systemen, wie bei Chatbots, die Anfragen in der Reihenfolge ihres Eingangs bearbeiten. Auch in der Spieleentwicklung werden Queues verwendet, um Aktionen von Spielern zu serialisieren.

Zusammenfassung und nächste Schritte

Mit diesem Tutorial hast du die Grundlagen für die Implementierung einer Movie-Ticketing-Queue in C gelernt. Du weißt jetzt, wie du eine Queue mit einer verketteten Liste erstellst, Kunden basierend auf ihrem Namen in Queues einteilst und die Verarbeitung an mehreren Booths simulieren. Übe diese Konzepte, indem du das Assignment Schritt für Schritt umsetzt. Denke daran, deinen Code zu kommentieren und die Speicherverwaltung im Auge zu behalten.

Viel Erfolg bei deinem COP3502C Assignment! Wenn du weitere Fragen hast, schau in die Foren oder frage deinen Tutor.