Generischer Stack

Teil des Abschnitts Object Oriented Programming der Rust-Journey von Coddy — Lektion 59 von 61.

Aufgabe

Einfach

Ein Stack (Stapel) ist eine grundlegende Datenstruktur, die dem Prinzip „Last In, First Out“ (LIFO) folgt – das zuletzt hinzugefügte Element wird als erstes wieder entfernt. Denken Sie an einen Stapel Teller: Sie legen Teller oben auf und nehmen sie auch von oben wieder weg.

Lassen Sie uns eine generische Stack-Datenstruktur bauen, die jeden Elementtyp aufnehmen kann! Ein Stack folgt dem „Last In, First Out“-Prinzip – wie ein Stapel Bücher, bei dem man nur oben etwas hinzufügen oder entfernen kann.

Sie werden Ihren Code auf zwei Dateien aufteilen:

stack.rs: Definieren Sie Ihr generisches Stack<T>-Struct, das intern ein Vec<T> verwendet, um Elemente zu speichern. Implementieren Sie drei Methoden: new, um einen leeren Stack zu erstellen, push, um ein Element oben hinzuzufügen, und pop, um das oberste Element zu entfernen und zurückzugeben (gibt Option<T> zurück, da der Stack leer sein könnte).
main.rs: Binden Sie Ihr Stack-Modul ein und demonstrieren Sie die Funktionsweise Ihres Stacks mit Ganzzahlen. Erstellen Sie einen Stack, pushen Sie die bereitgestellten Zahlen darauf, poppen Sie dann die Elemente nacheinander herunter und geben Sie jedes einzelne aus. Verwenden Sie unwrap_or, um die von pop zurückgegebene Option zu handhaben – wenn der Stack leer ist, verwenden Sie -1 als Standardwert.

Ein Stack benötigt zwei wesentliche Operationen:

push — fügt ein Element oben auf den Stack hinzu
pop — entfernt und gibt das oberste Element zurück

Die pop-Methode sollte ein Option<T> zurückgeben, da der Stack leer sein könnte. Der Typ Vec verfügt bereits über eine pop-Methode, die Option<T> zurückgibt, welche Sie in Ihrer Implementierung nutzen können.

Ihr Stack sollte so funktionieren: Wenn Sie die Werte 10, 20 und 30 (in dieser Reihenfolge) pushen, sollte dreimaliges Poppen Ihnen 30, 20 und 10 (umgekehrte Reihenfolge) liefern. Ein viertes Poppen auf einem leeren Stack sollte den Standardwert zurückgeben.

Geben Sie jeden gepoppten Wert in einer eigenen Zeile aus:

Zum Beispiel mit den Eingaben 5, 15 und 25:

Sie erhalten drei Eingaben: drei Ganzzahlen, die auf den Stack gepusht werden sollen (parsen Sie jede als i32). Nachdem Sie alle drei gepusht haben, poppen Sie viermal, um sowohl erfolgreiche Pops als auch den Fall eines leeren Stacks zu demonstrieren.

Probier es selbst

mod stack;

use stack::Stack;

fn main() {
    // Lies drei Ganzzahlen von der Eingabe
    let mut input1 = String::new();
    std::io::stdin().read_line(&mut input1).expect("Failed to read line");
    let num1: i32 = input1.trim().parse().expect("Invalid number");

    let mut input2 = String::new();
    std::io::stdin().read_line(&mut input2).expect("Failed to read line");
    let num2: i32 = input2.trim().parse().expect("Invalid number");

    let mut input3 = String::new();
    std::io::stdin().read_line(&mut input3).expect("Failed to read line");
    let num3: i32 = input3.trim().parse().expect("Invalid number");

    // TODO: Erstelle einen neuen Stack

    // TODO: Schiebe die drei Zahlen auf den Stack (num1, num2, num3 in dieser Reihenfolge)

    // TODO: Viermal poppen und jedes Ergebnis ausgeben
    // Verwende unwrap_or(-1), um den Fall eines leeren Stacks zu behandeln
}