Algorithmen und Datenstrukturen in Rust: Ein praktischer Leitfaden

Algorithmen und Datenstrukturen in Rust: Warum das wichtig ist

Rust ist eine moderne systemnahe Programmiersprache, die die Leistung von C++ mit der Speichersicherheit kombiniert, die durch das Ownership-System gewährleistet wird. Das Erlernen von Algorithmen und Datenstrukturen in Rust ermöglicht es nicht nur, klassische Konzepte der Computer Science zu meistern, sondern auch die einzigartigen Eigenschaften der Sprache tiefer zu verstehen: Borrowing, Lifetimes und Zero-Cost Abstractions.

In diesem Artikel werden wir drei fundamentale Datenstrukturen (Stack, Queue und binärer Suchbaum) und einen klassischen Algorithmus (Quicksort) behandeln, die in Rust implementiert sind. Jedes Beispiel wird von Code und Erklärungen begleitet, die Ihnen helfen, von der Theorie zur Praxis überzugehen.

1. Stack in Rust: Implementierung mit Vec

Ein Stack ist eine Datenstruktur, die nach dem LIFO-Prinzip (Last In, First Out) funktioniert. In Rust lässt sich ein Stack am einfachsten auf Basis des standardmäßigen Vec implementieren, das alle notwendigen Methoden bereitstellt: push zum Hinzufügen und pop zum Entfernen.

Um die Sicherheit von Rust zu demonstrieren, erstellen wir jedoch einen Wrapper mit expliziter Fehlerbehandlung:

pub struct Stack<T> {    elements: Vec<T>,}

impl<T> Stack<T> {    pub fn new() -> Self {        Stack { elements: Vec::new() }    }

    pub fn push(&mut self, item: T) {        self.elements.push(item);    }

    pub fn pop(&mut self) -> Option<T> {        self.elements.pop()    }

    pub fn peek(&self) -> Option<&T> {        self.elements.last()    }

    pub fn is_empty(&self) -> bool {        self.elements.is_empty()    }}

fn main() {    let mut stack = Stack::new();    stack.push(10);    stack.push(20);    stack.push(30);

    println!("Oberstes Element: {:?}", stack.peek()); // Some(30)    println!("Entferne: {:?}", stack.pop());         // Some(30)    println!("Entferne: {:?}", stack.pop());         // Some(20)    println!("Stack leer? {}", stack.is_empty());      // false}

Der entscheidende Vorteil von Rust ist hier das Typsystem. Wenn Sie versuchen, ein Element aus einem leeren Stack zu entfernen, zwingt Sie der Compiler, das Option zu behandeln, was Fehler durch Dereferenzierung von Nullzeigern ausschließt, die für C/C++ typisch sind.

2. Queue: Manuelle Implementierung mit einem Ringpuffer

Eine Queue (FIFO) ist komplexer als ein Stack, da sie ein effizientes Entfernen vom Anfang erfordert. Rust bietet keine fertige doppelendige Queue mit garantierter Leistung, daher implementieren wir einen Ringpuffer (circular buffer) fester Größe.

Dies ist ein hervorragendes Beispiel, um unsafe-Code und rohe Zeiger zu demonstrieren, aber wir bleiben im sicheren Bereich und verwenden Vec und Indizes:

pub struct Queue<T> {    buffer: Vec<Option<T>>,    head: usize,    tail: usize,    capacity: usize,}

impl<T> Queue<T> {    pub fn new(capacity: usize) -> Self {        let mut buffer = Vec::with_capacity(capacity);        buffer.resize_with(capacity, || None);        Queue {            buffer,            head: 0,            tail: 0,            capacity,        }    }

    pub fn enqueue(&mut self, item: T) -> Result<(), &str> {        if (self.tail + 1) % self.capacity == self.head {            return Err("Queue ist voll");        }        self.buffer[self.tail] = Some(item);        self.tail = (self.tail + 1) % self.capacity;        Ok(())    }

    pub fn dequeue(&mut self) -> Option<T> {        if self.head == self.tail {            return None;        }        let item = self.buffer[self.head].take();        self.head = (self.head + 1) % self.capacity;        item    }

    pub fn is_empty(&self) -> bool {        self.head == self.tail    }}

fn main()