使用 Rust 实现一个栈

前言

为了我们更好的去使用 Rust 去编写程序，掌握必要的数据结构和一些基本的算法是很有必要的。后续我会以图文的例子去写一些关于 Rust 数据结构的文章，可以同时学习到 Rust 的一些常用语法和数据结构。

本篇文章的小节：

• 实现效果图
• Rust 实现的代码
• 对应的 TypeScript 版本代码
• 总结

实现效果

后续的文章中我们都是先来一组图，然后再用程序描述出这组图的过程，最后再看具体的实现~废话不多说，直接开始

下面的程序就是上面的图的演示过程

fn main() {
    let mut stack = Stack::new();
    stack.push(1);
    stack.push(2);
    stack.push(3);
    // 打印 Some(3)
    println!("{:?}", stack.peek());
    stack.pop();
    // 打印 Some(2)
    println!("{:?}", stack.peek());

    // 修改第一个值为 111
    // map 可以将 Option 变体中的值提取出来，传入一个闭包
    stack.get_mut(0).map(|node| *node = 111);
    // 打印 Some(111)
    println!("{:?}", stack.get(0));
}

接下来我们再来看具体的实现，简单的来做，我们使用 Rust 自带的 Vec 容器作为基础的数据结构(类似于 Java 的 List 或者 JavaScript 中的数组)，它的数据会存放在堆上，在运行时会根据值的数量动态地调整容器的大小，比如当容量不够时会自动扩展两倍。

然后这里我们基于它封装一套栈的语法，这一期我们实现的比较简单，都是直接调用的 Vec 中的原生 API。

Rust 实现

// 实现 Debug Trait，可以让它在控制台上打印
#[derive(Debug)]
struct Stack<T> {
    size: usize,
    data: Vec<T>,
}

impl<T> Stack<T> {
    fn new() -> Stack<T> {
        Self {
            // 当前长度
            size: 0,
            // 数据容器
            data: vec![],
        }
    }

    // 往栈中推进一个值
    fn push(&mut self, value: T) {
        self.data.push(value);
        self.size += 1;
    }

    // 出栈
    fn pop(&mut self) -> Option<T> {
        if self.isEmpty() {
            return None;
        }

        self.size -= 1;
        self.data.pop()
    }

    // 查看栈顶元素
    fn peek(&self) -> Option<&T> {
        if self.isEmpty() {
            return None;
        }

        self.data.get(self.size - 1)
    }

    // 根据下标获取对应位置数据的不可变引用
    fn get(&self, index: usize) -> Option<&T> {
        if self.isEmpty() || index > self.size - 1 || index < 0 {
            return None;
        }

        self.data.get(index)
    }

    // 根据下标获取对应位置数据的可变引用
    fn get_mut(&mut self, index: usize) -> Option<&mut T> {
        if self.isEmpty() || index > self.size - 1 || index < 0 {
            return None;
        }

        self.data.get_mut(index)
    }


    // 判断栈是否为空
    fn is_empty(&self) -> bool {
        self.size == 0
    }

    // 获取栈的长度
    fn size(&self) -> usize {
        self.size
    }
}

对应的 TypeScript 版本代码

这里只写个框架，就不写具体实现了，由 TS 版本的代码可以看出， TS 是不分什么可变不可变引用的，对于内存的控制力没有 Rust 那么强

class Stack<T> {
  #_size: number;
  #_data: Array<T>;

  constructor() {
    this.#_size = 0;
    this.#_data = [];
  }

  push(value: T) {}

  pop(): T | null {}

  peek(): T | null {}

  get(index: number): T | null {}

  is_empty(): boolean {}

  size(): number {
    return this.#_size;
  }
}

总结

这一期比较简单，可以了解到 Vec 容器的使用和一个基础的栈结构的运作。这里我们主要是了解了 Rust 的语法，它和 TypeScript 不一样，TS 是可以在 class 中同时存放数据和方法的，但是 Rust 要先声明一个结构体，然后结构体中存放数据，再通过对结构体进行实现，才能把方法添加上。

从上面两个代码的对比可以看得出，Rust 对于内存的掌控力比 TypeScript 强，Rust 可以把数据分为可变和不可变，并且可以直接通过引用来操控对应的内存地址中的数据，虽然 Ts 中的数组的数据也是存放在堆上，但用 Rust 的概念来解释，拿 Ts 数组上的数据时，统统都是可变引用，比如这段代码：

const stack = [1, 2, 3];
stack[0] = 111;

Ts 中可以直接通过下标 0 来获取栈中的值并进行修改，但是 Rust 的话需要调用 get_mut() 方法，如果不想修改值只想查看的话就要调用 get 方法返回不可变引用。Rust 这样虽然麻烦，但是可以一定程度上保证程序的一个健壮性，毕竟 Rust 是以内存安全著称的。