Queue- und Stack-Sammlungen in Rust

1. Rost-Sammlung
2. Rost-Warteschlange
3. Stapel in Rost

In diesem Artikel geht es um das Vorhandensein von Queue- und Stack-Sammlungen in Rust.

Rost-Sammlung

Die Standardsammlungsbibliothek von Rust enthält effiziente Implementierungen der am häufigsten verwendeten Datenstrukturen in der Allzweckprogrammierung. Als Ergebnis sollten zwei Bibliotheken in der Lage sein, ohne viel Datenkonvertierung zu kommunizieren, wenn sie die Standardimplementierungen verwenden.

Zu Beginn sollten wir wahrscheinlich Vec verwenden. Diese beiden Sammlungen decken die meisten Speicher- und Verarbeitungsszenarien für generische Daten ab.

Sie zeichnen sich durch das aus, was sie tun. Alle anderen Sammlungen in der Standardbibliothek haben spezifische Anwendungsfälle, für die sie die optimale Wahl sind, aber diese Anwendungsfälle sind eher Nischen.

Auch wenn Vec und HashMap technisch schlecht sind, sind sie wahrscheinlich ein ausreichender Ausgangspunkt.

Die in Rust verfügbaren Sammlungen können wie unten in vier Hauptkategorien eingeteilt werden.

1. Sequenzen: Vec, VecDeque, LinkedList
2. Karten: HashMap, BTreeMap
3. Sätze: HashSet, BTreeSet
4. Verschiedenes: BinaryHeap

Rost-Warteschlange

Die Queue-Datenstruktur in Rust wird verwendet, um die Elemente zu speichern. Die Warteschlange in Rust funktioniert nach dem FIO-Prinzip, was bedeutet, dass zuerst rein, zuerst raus.

Dies ist eine Standardwarteschlange, die in der Rust-Sammlungsbibliothek enthalten ist. Es ist eine lineare Datenstruktur.

Queue bietet uns mehrere Operationen, die verwendet werden können, um sie zu manipulieren. Es kann eine beliebige Anzahl von Elementen enthalten; Die gesamte Implementierung basiert auf der Vektordatenstruktur von Rust.

Syntax:

let mut variable_name : Queue<queue_size> = queue![];

Stapel in Rost

Ein Stapel ist eine Sammlung von Artikeln, die hinzugefügt und entfernt werden können, aber nur in der folgenden Reihenfolge: last in - first out (LIFO). Wenn Sie beispielsweise in einen überfüllten Zug einsteigen, müssen Sie als erster aussteigen, damit auch andere Fahrgäste aussteigen können.

Das Hinzufügen von Objekten wird typischerweise als push bezeichnet, während das Entfernen von Waren typischerweise als pop bezeichnet wird, da diese Funktionen in Rust mithilfe der Datenstruktur Vec (Vektor) implementiert sind.

Um einen neuen Stapel zu erstellen, können wir die folgende Syntax verwenden.

let s = Stack { stack: Vec::new() };

Rust’ bietet keine Bibliothek mit garantierter Latenz zum Hinzufügen von Elementen zur Standardbibliothek. Beim Hinzufügen zusätzlicher Elemente zu Rust-Sammlungen kann Speicher zugewiesen werden.

Im schlimmsten Fall kann die Speicherzuweisung unendlich lange dauern.

Es gibt jeweils zwei mögliche Kandidaten.

1. Ein Stack kann entweder auf einer Vec oder einer LinkedList implementiert werden, da beide pop back und push back unterstützen.
2. Eine Warteschlange kann entweder auf einer VecDeque oder einer LinkedList implementiert werden, da beide pop front und push back unterstützen.

Es gibt einen Unterschied zwischen Vec und LinkedList. Letzteres ist einfacher: Für jeden Aufruf zum push back wird Speicher zugewiesen.

Dies ist einerseits günstig, da die Kosten für push back unabhängig von der Anzahl der bereits in der Sammlung befindlichen Objekte sind. Andererseits kann die Speicherzuordnung jedoch sehr lange dauern.

Ersteres ist etwas komplizierter, weil:

1. es hat aufgrund seiner Cache-freundlichen Natur einen höheren Durchsatz
2. es verfügt über zusätzliche Kapazität, wodurch sichergestellt wird, dass kein push back vergeben wird, solange Überkapazität vorhanden ist; es hält immer noch amortisiertes O(1) push back aufrecht, selbst wenn überschüssige Kapazität nicht im Voraus reserviert wird

Besser wäre es, Vec für Stacks und VecDeque für Queues zu verwenden.