rustborrow-checkermutable-reference

Pop function for a stack


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);
    }

Solution

  • 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