Es gibt unterschiedliche Möglichkeiten, einen Stapel zu
implementieren. Man kann die Implementation auch verbergen und den
Stapel damit zu einem abstrakten Datentyp machen. Im folgenden
konstruieren wir einen Stapel als einfach verkettete Liste, weil das
zunächst am einfachsten ist. Ein Knoten enthält dazu ein Datenfeld
data und einen Zeiger auf den nächsten Knoten. Da der
Zeiger am Grund des Stapels keinen Nachfolger besitzt, müssen wir
den Zeiger zu einer Option machen.
Der Stapel ist dann ein Zeiger auf die Stapeloberseite. Die Liste verläuft von der Oberseite aus in Richtung Grund. Da der Stapel auch leer sein darf, muss der Zeiger eine Option sein.
Der Stapel besitzt zunächst zwei Methoden. Die Methode
push legt ein Element auf den Stapel. Die
Methode pop nimmt ein Element vom Stapel herunter und
gibt es als Wert zurück.
struct Node<T> {
data: T,
next: Option<Box<Node<T>>>
}
pub struct Stack<T> {
top: Option<Box<Node<T>>>
}
impl<T> Stack<T> {
pub fn new() -> Self {
Stack {top: None}
}
pub fn push(&mut self, x: T) {
let node = self.top.take();
self.top = Some(Box::new(Node {data: x, next: node}));
}
pub fn pop(&mut self) -> Option<T> {
if let Some(node) = self.top.take() {
self.top = node.next;
Some(node.data)
} else {
None
}
}
}
fn main() {
let mut a: Stack<i32> = Stack::new();
a.push(1);
a.push(2);
println!("{:?}", a.pop());
println!("{:?}", a.pop());
println!("{:?}", a.pop());
}
Für einfach verkettete Listen gibt es auch eine alternative Darstellung:
enum List<T> {
Nil, Node{data: T, next: Box<List<T>>}
}
Das führt zu einer leicht modifzierten, aber semantisch äquivalenten Implementation:
pub enum Stack<T> {
Nil, Node {data: T, next: Box<Stack<T>>}
}
impl<T> Stack<T> {
pub fn new() -> Self {
Stack::Nil
}
pub fn push(&mut self, x: T) {
let node = std::mem::replace(self, Stack::Nil);
*self = Stack::Node {data: x, next: Box::new(node)};
}
pub fn pop(&mut self) -> Option<T> {
match std::mem::replace(self, Stack::Nil) {
Stack::Node {data, next} => {
*self = *next;
Some(data)
},
Stack::Nil => None
};
}
}
fn main() {
let mut a: Stack<i32> = Stack::new();
a.push(1);
a.push(2);
println!("{:?}", a.pop());
println!("{:?}", a.pop());
println!("{:?}", a.pop());
}
Eine alternative Implementierung nutzt zur Ablage der Daten einen
Puffer. Kommt zum vollständig belegten Puffer ein weiteres Element
hinzu, wird dieser zuvor mittels einer Operation
reallocate durch einen neuen Puffer doppelter Größe
ersetzt, wobei die bereits gespeicherten Elemente logischerweise in den
neuen Puffer zu überführen sind.
Unbelegte Speicherzellen des Puffers kodieren wir als
None, um nicht mit uninitialisiertem Speicher respektive
ungültigen Werten arbeiten zu müssen.
pub struct Stack<T> {
buf: Box<[Option<T>]>,
len: usize
}
impl<T> Stack<T> {
pub fn new() -> Self {
Self {len: 0, buf: Box::new([None])}
}
fn reallocate(&mut self, size: usize) {
let mut buf = Box::from_iter((0..size).map(|_| None));
for i in 0..self.buf.len() {
buf[i] = self.buf[i].take();
}
self.buf = buf;
}
pub fn push(&mut self, x: T) {
if self.len == self.buf.len() {
self.reallocate(self.buf.len()*2);
}
self.buf[self.len] = Some(x);
self.len += 1;
}
pub fn pop(&mut self) -> Option<T> {
if self.len != 0 {
self.len -= 1;
self.buf[self.len].take()
} else {
None
}
}
}
Diese Konstruktion entspricht konzeptuell der von Vec
aus der Standardbibliothek. Allerdings entfallen bei Vec
die eigentlich redundanten Optionen im Puffer, womit bei
Vec das Ausborgen von
Teilen des belegten Puffers als Slice durchführbar ist. Dagegen ist
bei Stack eine abstraktere Schnittstelle zu nutzen,
zum Beispiel ein Iterator.
Die Liste soll aus Knoten bestehen. Jeder Knoten enthält ein
Datenfeld data und einen Zeiger next auf den
nächsten Knoten. Da der letzte Knoten keinen Nachfolger besitzt, müssen
wir den Zeiger next zu einer Option machen.
Die Liste ließe sich nun als Zeiger first auf den
ersten Knoten betrachten. Da die Liste aber leer sein darf, muss
first eine Option sein, denn sobald ein Knoten vorhanden
wäre, müsste auch das Datenfeld zu diesem Knoten vorhanden sein.
Die Liste soll außerdem eine Methode push besitzen,
die ein Element an das Ende der Liste hinzufügt. Um dieses zu erreichen,
müsste die Liste von vorne bis hinten iteriert werden, da es nur ein
Zeiger auf den Anfang gibt. Da dies ineffizient ist, speichern wir
zusätzlich auch einen Zeiger auf das Ende. Da es nun zwei Zeiger auf
denselben Knoten geben kann, müssen wir Rc benutzen, denn
Box erlaubt keinen gemeinsamen Besitz. Der Inhalt von
Rc ist jedoch unveränderlich. Daher benötigen wir eine
Zelle RefCell, die einen darin veränderlichen Inahlt
ermöglicht. Somit bekommt die Typdefinition schließlich die
folgende Gestalt:
type RcCell<T> = Rc<RefCell<T>>;
struct Node<T> {
data: T,
next: Option<RcCell<Node<T>>>
}
struct List<T> {
first: Option<RcCell<Node<T>>>,
last: Option<RcCell<Node<T>>>
}
Zusätzlich bräuchten wir einen Iterator, der durch die Liste iteriert, und darauf aufbauend eine Prozedur zur Ausgabe. Der Einfachheit halber führen wir den Iterator klonend aus. Die folgende Implementation enthält gleich alles in einem Rutsch.
use std::rc::Rc;
use std::cell::RefCell;
use std::fmt;
type RcCell<T> = Rc<RefCell<T>>;
struct Node<T> {
data: T,
next: Option<RcCell<Node<T>>>
}
struct List<T> {
first: Option<RcCell<Node<T>>>,
last: Option<RcCell<Node<T>>>
}
impl<T> List<T> {
fn new() -> Self {
List{first: None, last: None}
}
fn push(&mut self, x: T) {
let node = Rc::new(RefCell::new(Node {data: x, next: None}));
if let Some(last) = &self.last {
last.borrow_mut().next = Some(node.clone());
self.last = Some(node);
} else {
self.first = Some(node.clone());
self.last = Some(node);
}
}
}
impl<T> List<T> {
fn iter(&self) -> ListIterator<T> {
ListIterator{node: self.first.clone()}
}
}
struct ListIterator<T> {
node: Option<RcCell<Node<T>>>
}
impl<T: Clone> Iterator for ListIterator<T> {
type Item = T;
fn next(&mut self) -> Option<T> {
if let Some(node) = self.node.take() {
let data = node.borrow().data.clone();
self.node = node.borrow().next.clone();
Some(data)
} else {
None
}
}
}
impl<T: Clone + fmt::Display> fmt::Display for List<T> {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
write!(f, "[")?;
let mut first = true;
for x in self.iter() {
if first {first = false;} else {write!(f, ", ")?;}
write!(f, "{}", x)?;
}
write!(f, "]")
}
}
fn list<T, const N: usize>(a: [T; N]) -> List<T> {
let mut acc = List::new();
for x in a {acc.push(x);}
acc
}
fn main() {
let a: List<i32> = list([1, 2, 3, 4]);
println!("{}", a);
}
Eine Warteschlange ist, wie der Name bereits nahelegt, eine Datenstruktur, bei der Elemente effizient in derselben Reihenfolge entnommen werden können, in der sie in die Datenstruktur hineingebracht wurden. Die Programmierung einer solchen vermittels zweier Stapel tritt als verhältnismäßig leichte Übung hervor.
Der Ansatz beruht auf der folgenden Idee. Bei der Entnahme der Elemente von einem Stapel dreht sich, wie man weiß, die Reihenfolge um, in welcher die Elemente auf den Stapel gelegt wurden. Durchläuft eine Reihe von Elementen diese Prozedur also zweimal aufeinanderfolgend, liegt danach wieder die ursprüngliche Reihenfolge vor.
Den ersten Stapel benennen wir istack für
input stack, dt. Eingangsstapel und den zweiten
ostack für output stack, dt. Ausgangsstapel.
Die Operation enqueue soll ein Element zur Schlange
hinzufügen, die Operation dequeue eines entnehmen.
Bei enqueue wird das Element schlicht auf den
Eingangsstapel gepackt. Dagegen verhält sich dequeue ein
wenig komplizierter. Ist der Ausgangsstapel nichtleer, wird eines
abgehoben. Ist der Ausgangsstapel dagegen leer, wird solange ein
Element des Eingangsstapels entnommen und auf den Ausgangsstapel
gelegt, bis der Eingangsstapel geleert wurde. Erst danach wird ein
Element vom Ausgangsstapel abgehoben.
Zu beachten gilt, dass die Leerung des Eingangsstapels vollständig sein muss und nur dann erfolgen darf, wenn ein leerer Ausgangsstapel vorliegt. Andernfalls käme es zu einem logischen Fehler, das heißt, einer falschen Reihenfolge bei der Entnahme.
pub struct Queue<T> {
istack: Vec<T>,
ostack: Vec<T>
}
impl<T> Queue<T> {
pub fn new() -> Self {
Self {istack: Vec::new(), ostack: Vec::new()}
}
pub fn enqueue(&mut self, x: T) {
self.istack.push(x)
}
pub fn dequeue(&mut self) -> Option<T> {
if self.ostack.is_empty() {
while let Some(x) = self.istack.pop() {
self.ostack.push(x)
}
}
self.ostack.pop()
}
}
Obwohl es effizientere Ansätze als den dargelegten gibt, ist dieser zugestanden recht kompakt und nicht sonderlich ineffizient.
Baumstrukturen lassen sich wie einfach verkettete Listen als Enumeration formulieren. Algorithmen für Bäume können hochkompliziert ausfallen, besonders wenn diese einer Balancierung unterworfen werden müssen um die Rekursionstiefe möglichst niedrig zu halten.
Formulieren wir dann doch zunächst eine Funktion depth
zur Ermittlung der Tiefe eines Binärbaums. In puristischer Form
fällt der Algorithmus selbst rekursiv aus, das ist typisch bei
Algorithmen für Baumstrukturen.
enum Tree<T> {
Empty,
Leaf(T),
Node(Box<Tree<T>>, Box<Tree<T>>)
}
impl<T> Tree<T> {
fn node(x: Tree<T>, y: Tree<T>) -> Self {
Tree::Node(Box::new(x), Box::new(y))
}
}
fn depth<T>(t: &Tree<T>) -> u32 {
match t {
Tree::Empty => 0,
Tree::Leaf(_) => 1,
Tree::Node(x, y) => 1 + depth(x).max(depth(y))
}
}
fn main() {
let t: Tree<char> = Tree::node(
Tree::node(Tree::Leaf('A'), Tree::Empty),
Tree::Leaf('B')
);
println!("{}", depth(&t));
}