I wanted to implement a stack, but I am having a lot of trouble with pop. I'm trying to do it with a while let loop, but can't seem to beat the borrow checker.
pub struct Stack<T>{
top: Option<Box<Node<T>>>,
}
struct Node<T>{
val: T,
under: Option<Box<Node<T>>>,
}
Here's the Stack implementation and here is pop:
pub fn pop(&mut self) -> Option<T>{
if self.top.is_none(){
return None;
}
let mut last_node = &mut self.top;
while let Some(node) = last_node{
if node.under.is_none(){
break;
} else{
last_node = &mut node.under;
}
}
let return_node = std::mem::replace(last_node, None);
return Some(return_node.unwrap().val);
}
The trick here is to move top
completely out of self
, take what you need from it, then stick under
back into self.top
.
impl<T> Stack<T> {
pub fn pop(&mut self) -> Option<T> {
let top = self.top.take(); // take ownership of self.top
let Some(top) = top else {
return None
};
let Node { val, under } = *top; // we own top so we can move out
self.top = under; // put the next node down back in self
Some(val)
}
}
fn main() {
// 1 -> 2 -> 3 -> None
let mut stack = Stack {
top: Some(
Node {
val: 1,
under: Some(
Node {
val: 2,
under: Some(
Node {
val: 3,
under: None,
}
.into(),
),
}
.into(),
),
}
.into(),
),
};
println!("{:?}", stack.pop());
println!("{:?}", stack.pop());
println!("{:?}", stack.pop());
println!("{:?}", stack.pop());
println!("{:?}", stack.pop());
}
Result:
Some(1)
Some(2)
Some(3)
None
None