Algorithmen und Datenstrukturen in Rust: Ein praktischer Leitfaden

Einleitung: Warum Rust ideal für Algorithmen und Datenstrukturen ist

Rust vereint die Leistung von C/C++ mit Speichersicherheit, was es zu einer hervorragenden Wahl für die Implementierung von Algorithmen und Datenstrukturen macht. Dank des Ownership- und Borrowing-Systems können Sie effiziente und sichere Strukturen ohne Garbage Collector erstellen. In diesem Artikel analysieren wir die praktische Implementierung wichtiger Datenstrukturen und Algorithmen in Rust – vom Stack bis zum Binärbaum und Graphendurchlauf.

Wir verwenden ausschließlich die Standardbibliothek von Rust, damit Sie den Code sofort in Ihren Projekten anwenden können. Alle Beispiele sind kompilierbar und funktionieren mit Rust 2021 Edition.

1. Stack und Queue: Klassische Strukturen in Rust

Stack

Ein Stack arbeitet nach dem LIFO-Prinzip (Last In, First Out). In Rust lässt sich ein Stack am einfachsten auf Basis von Vec implementieren:

struct Stack<T> {\n    elements: Vec<T>,\n}\n\nimpl<T> Stack<T> {\n    fn new() -> Self {\n        Stack { elements: Vec::new() }\n    }\n\n    fn push(&mut self, value: T) {\n        self.elements.push(value);\n    }\n\n    fn pop(&mut self) -> Option<T> {\n        self.elements.pop()\n    }\n\n    fn peek(&self) -> Option<&T> {\n        self.elements.last()\n    }\n\n    fn is_empty(&self) -> bool {\n        self.elements.is_empty()\n    }\n}\n\nfn main() {\n    let mut stack = Stack::new();\n    stack.push(10);\n    stack.push(20);\n    stack.push(30);\n    \n    println!("Oberstes Element: {:?}", stack.peek()); // Some(30)\n    println!("Entfernen: {:?}", stack.pop()); // Some(30)\n    println!("Ist der Stack leer? {}", stack.is_empty()); // false\n}

Vorteil: Vec bietet bereits amortisiertes O(1) für push/pop, und Rust garantiert, dass der Speicher beim Verlassen des Gültigkeitsbereichs freigegeben wird.

Queue

Eine Queue arbeitet nach dem FIFO-Prinzip (First In, First Out). Für eine effiziente Implementierung verwenden wir VecDeque aus der Standardbibliothek:

use std::collections::VecDeque;\n\nstruct Queue<T> {\n    elements: VecDeque<T>,\n}\n\nimpl<T> Queue<T> {\n    fn new() -> Self {\n        Queue { elements: VecDeque::new() }\n    }\n\n    fn enqueue(&mut self, value: T) {\n        self.elements.push_back(value);\n    }\n\n    fn dequeue(&mut self) -> Option<T> {\n        self.elements.pop_front()\n    }\n\n    fn front(&self) -> Option<&T> {\n        self.elements.front()\n    }\n\n    fn len(&self) -> usize {\n        self.elements.len()\n    }\n}\n\nfn main() {\n    let mut queue = Queue::new();\n    queue.enqueue("erster");\n    queue.enqueue("zweiter");\n    queue.enqueue("dritter");\n\n    println!("Erster in der Queue: {:?}", queue.front()); // Some("erster")\n    println!("Bedienen: {:?}", queue.dequeue()); // Some("erster")\n    println!("Länge der Queue: {}", queue.len()); // 2\n}

Wichtig: VecDeque verwendet einen Ringpuffer, was O(1) für Einfügungen und Löschungen an beiden Enden ermöglicht. Dies ist deutlich schneller als die Verwendung von Vec für eine Queue.

2. Binärer Suchbaum (BST) in Rust

Der binäre Suchbaum ist eine der grundlegenden Datenstrukturen. Wir implementieren ihn mit Box für rekursive Typen:

use std::cmp::Ordering;\n\n#[derive(Debug)]\nstruct Node<T: Ord> {\n    value: T,\n    left: Option<Box<Node<T>>>,\n    right: Option<Box<Node<T>>>,\n}\n\n#[derive(Debug)]\nstruct BinarySearchTree<T: Ord> {\n    root: Option<Box<Node<T>>>,\n}\n\nimpl<T: Ord> BinarySearchTree<T> {\n    fn new() -> Self {\n        BinarySearchTree { root: None }\n    }\n\n    fn insert(&mut self, value: T) {\n        let mut current = &mut se