Implementierung der Warteschlangen-Datenstruktur in C

Einführung

In diesem Projekt lernst du, wie du eine Warteschlange (Queue) als Datenstruktur in C implementierst. Warteschlangen werden in der Informatik weit verbreitet eingesetzt, beispielsweise in Nachrichtenwarteschlangen, die zum Übertragen von Daten in einem Computer verwendet werden.

👀 Vorschau

$ gcc queue.c -o queue
$./queue
11250

🎯 Aufgaben

In diesem Projekt wirst du lernen:

• Wie du die front()-Methode implementierst, um den Wert des vordersten Elements in der Warteschlange zurückzugeben
• Wie du die pop()-Methode implementierst, um das vorderste Element aus der Warteschlange zu entfernen und zurückzugeben
• Wie du die count()-Methode implementierst, um die Anzahl der derzeit in der Warteschlange befindlichen Elemente zurückzugeben
• Wie du die is_empty()-Methode implementierst, um zu überprüfen, ob die Warteschlange leer ist

🏆 Errungenschaften

Nach Abschluss dieses Projekts wirst du in der Lage sein:

• Die grundlegenden Operationen einer Warteschlangen-Datenstruktur zu verstehen
• Die Kernmethoden einer Warteschlange in C zu implementieren
• Dein Wissen über Warteschlangen anzuwenden, um reale Probleme zu lösen

Skills Graph

Implementiere die front()-Methode

In diesem Schritt lernst du, wie du die front()-Methode der Warteschlange implementierst.

Die front()-Methode sollte den Wert des vordersten Elements in der Warteschlange zurückgeben. Wenn die Warteschlange leer ist, sollte die Methode das Programm mit exit(-1) beenden.

Folgende Schritte, um diesen Schritt abzuschließen:

1. Öffne die Datei queue.c, die sich im Verzeichnis /home/labex/project/queue.c befindet.
2. Locate die front()-Methode im Code.
3. Implementiere die front()-Methode wie folgt:

static int front() {
    if(!phead) {
        exit(-1);
    }
    return phead->val;
}

Die front()-Methode überprüft zunächst, ob der Zeiger phead NULL ist, was auf eine leere Warteschlange hinweist. Wenn die Warteschlange leer ist, beendet die Methode das Programm mit exit(-1).

Wenn die Warteschlange nicht leer ist, gibt die Methode den in der phead-Knoten gespeicherten Wert zurück, der das vorderste Element der Warteschlange darstellt.

Implementiere die pop()-Methode

In diesem Schritt lernst du, wie du die pop()-Methode der Warteschlange implementierst.

Die pop()-Methode sollte das vorderste Element aus der Warteschlange entfernen und zurückgeben. Wenn die Warteschlange leer ist, sollte die Methode das Programm mit exit(-1) beenden.

Folgende Schritte, um diesen Schritt abzuschließen:

1. Öffne die Datei queue.c, die sich im Verzeichnis /home/labex/project/queue.c befindet.
2. Locate die pop()-Methode im Code.
3. Implementiere die pop()-Methode wie folgt:

static int pop() {
    if(!phead) {
        exit(-1);
    }
    int val = phead->val;
    phead = phead->next;
    return val;
}

Die pop()-Methode überprüft zunächst, ob der Zeiger phead NULL ist, was auf eine leere Warteschlange hinweist. Wenn die Warteschlange leer ist, beendet die Methode das Programm mit exit(-1).

Wenn die Warteschlange nicht leer ist, speichert die Methode den Wert des phead-Knotens, der das vorderste Element der Warteschlange darstellt. Anschließend aktualisiert sie den phead-Zeiger auf den nächsten Knoten, was effektiv das vorderste Element aus der Warteschlange entfernt. Schließlich gibt die Methode den gespeicherten Wert zurück.

Implementiere die count()-Methode

In diesem Schritt lernst du, wie du die count()-Methode der Warteschlange implementierst.

Die count()-Methode sollte die Anzahl der derzeit in der Warteschlange befindlichen Elemente zurückgeben.

Folgende Schritte, um diesen Schritt abzuschließen:

1. Öffne die Datei queue.c, die sich im Verzeichnis /home/labex/project/queue.c befindet.
2. Locate die count()-Methode im Code.
3. Implementiere die count()-Methode wie folgt:

static int count() {
    int cnt = 0;
    for(struct node* p = phead; p; p=p->next) {
        cnt++;
    }
    return cnt;
}

Die count()-Methode initialisiert eine Variable cnt mit 0. Anschließend läuft sie die Warteschlange entlang, indem sie die next-Zeiger des phead-Knotens und seiner Nachfolger folgt. Für jeden begegneten Knoten erhöht sie die Variable cnt. Schließlich gibt die Methode den cnt-Wert zurück, der die Anzahl der Elemente in der Warteschlange darstellt.

Implementiere die is_empty()-Methode

In diesem Schritt lernst du, wie du die is_empty()-Methode der Warteschlange implementierst.

Die is_empty()-Methode sollte 1 zurückgeben, wenn die Warteschlange leer ist, und 0 sonst.

Folgende Schritte, um diesen Schritt abzuschließen:

1. Öffne die Datei queue.c, die sich im Verzeichnis /home/labex/project/queue.c befindet.
2. Locate die is_empty()-Methode im Code.
3. Implementiere die is_empty()-Methode wie folgt:

static int is_empty() {
    return phead == NULL;
}

Die is_empty()-Methode überprüft einfach, ob der Zeiger phead NULL ist, was auf eine leere Warteschlange hinweist. Wenn phead NULL ist, gibt die Methode 1 zurück, was bedeutet, dass die Warteschlange leer ist. Andernfalls gibt sie 0 zurück, was bedeutet, dass die Warteschlange nicht leer ist.

Herzlichen Glückwunsch! Du hast jetzt alle erforderlichen Methoden für die Warteschlangen-Datenstruktur implementiert. Du kannst jetzt das Programm kompilieren und ausführen, um die Funktionalität der Warteschlange zu testen.

4. Kompilieren und ausführen:

$ gcc queue.c -o queue
$./queue
00000

Die erwartete Ausgabe lautet wie folgt:

$ gcc queue.c -o queue
$./queue
11250

Zusammenfassung

Herzlichen Glückwunsch! Du hast dieses Projekt abgeschlossen. Du kannst in LabEx weitere Übungen absolvieren, um deine Fähigkeiten zu verbessern.