Rust
Generic stack
Build a Vec-backed generic Stack<T> data structure.
Final task: generic stack
In the intermediate level's final tasks you'll combine generics, traits, iterators and error handling. The first: a stack that works with any type. Last in, first out (LIFO):
struct Yigin<T> {
ogeler: Vec<T>,
}
impl<T> Yigin<T> {
fn new() -> Self { .. }
fn push(&mut self, x: T) { .. }
fn pop(&mut self) -> Option<T> { .. } // None if empty
fn peek(&self) -> Option<&T> { .. } // look without removing
fn len(&self) -> usize { .. }
fn is_empty(&self) -> bool { .. }
}
peek returns a reference, so T doesn't need to be Clone.
Delegating to Vec
Stack behaviour matches Vec's methods one to one; the wrapper only narrows the API and gives meaningful names:
impl<T> Yigin<T> {
fn push(&mut self, x: T) { self.ogeler.push(x); }
fn pop(&mut self) -> Option<T> { self.ogeler.pop() }
fn peek(&self) -> Option<&T> { self.ogeler.last() }
}
The user can't insert into the middle of the vector; the stack's invariants are protected.
Exercise Stack
Write the Yigin<T> type above with all its methods. Push 1, 2, 3; print the results of pop(), peek(), len() and is_empty() for an empty Yigin<&str> on one line.
Show example solution
struct Yigin<T> {
ogeler: Vec<T>,
}
impl<T> Yigin<T> {
fn new() -> Self {
Self { ogeler: Vec::new() }
}
fn push(&mut self, x: T) {
self.ogeler.push(x);
}
fn pop(&mut self) -> Option<T> {
self.ogeler.pop()
}
fn peek(&self) -> Option<&T> {
self.ogeler.last()
}
fn len(&self) -> usize {
self.ogeler.len()
}
fn is_empty(&self) -> bool {
self.ogeler.is_empty()
}
}
fn main() {
let mut y = Yigin::new();
for n in [1, 2, 3] {
y.push(n);
}
let p = y.pop();
let t = y.peek().copied();
let bos: Yigin<&str> = Yigin::new();
println!("{:?} {:?} {} {}", p, t, y.len(), bos.is_empty());
}
Test yourself
-
Which <code>Vec</code> method is used for <code>peek</code>?
Show answer
last() — The top of the stack is the end of the vector; last() gives Option<&T> to the last element.
-
Look at the top
fn peek(&self) -> Option<&T> {
self.ogeler.____()
}
Show answer
fn peek(&self) -> Option<&T> {
self.ogeler.last()
}
-
Operation and result (1, 2, 3 pushed)
- pop()
- Some(3)
- then peek()
- Some(2)
- then len()
- 2
- Yigin::<&str>::new().is_empty()
- true
Next lesson: Shapes with traits
