用链表实现栈

rust
fn main() {
    let mut stack = Stack::new();
    stack.push(1);
    stack.push(2);
    stack.push(3);

    // 栈顶是 3
    // Stack { size: 3, top: Some(Node { data: 3, next: Some(Node { data: 2, next: Some(Node { data: 1, next: None }) }) }) }
    println!("{:?}", stack);

    stack.pop();

    // 栈顶是 2
    // Stack { size: 2, top: Some(Node { data: 2, next: Some(Node { data: 1, next: None }) }) }
    println!("{:?}", stack);

    // 查看栈顶的值，返回不可变引用，返回 Some(2)
    println!("{:?}", stack.peek());

    // 获取下标为 1 的节点， 打印 Some(1)
    println!("{:?}", stack.get(1));

    // 修改下标为 1 的节点，修改为 111
    stack.get_mut(1).map(|data| *data = 111);

    // 获取下标为 1 的节点，打印 Some(111)
    println!("{:?}", stack.get(1));
}

type Link<T> = Option<Box<Node<T>>>;

/// 链表的节点
#[derive(Debug, Clone)]
struct Node<T> {
    data: T,
    next: Link<T>,
}

impl<T> Node<T> {
    fn new(data: T) -> Self {
        Self { data, next: None }
    }
}

/// 链表栈
#[derive(Debug, Clone)]
struct Stack<T> {
    size: usize,
    // 使用栈顶来进行控制栈结构
    top: Link<T>,
}

impl<T: Clone> Stack<T> {
    fn new() -> Self {
        Self { size: 0, top: None }
    }

    fn size(&self) -> usize {
        self.size
    }

    // take 取出 top 中的节点 ，留下 None
    fn push(&mut self, data: T) {
        let mut node = Node::new(data);
        node.next = self.top.take();
        self.top = Some(Box::new(node));
        self.size += 1;
    }

    fn pop(&mut self) -> Option<T> {
        // 从栈顶取出一个节点，留下个 None
        self.top.take().map(|node| {
            // 解引用 Box 中的节点
            let node = *node;
            // 将栈顶节点指向下一个
            self.top = node.next;
            self.size -= 1;
            node.data
        })
    }

    fn peek(&self) -> Option<&T> {
        self.top.as_ref().map(|node| &node.data)
    }

    fn get(&self, index: usize) -> Option<&T> {
        let mut current = &self.top;
        let mut current_index = 0;

        while let Some(node) = current {
            if current_index == index {
                return Some(&node.data);
            }

            current = &node.next;
            current_index += 1;
        }

        None
    }

    fn get_mut(&mut self, index: usize) -> Option<&mut T> {
        let mut current = &mut self.top;
        let mut current_index = 0;

        while let Some(node) = current {
            if index == current_index {
                return Some(&mut node.data);
            }
            current = &mut node.next;
            current_index += 1;
        }

        None
    }
}
用链表实现栈 ​

用链表实现栈
