实现一个队列

前言

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

本篇文章的小节：

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

实现效果图

上述执行代码

fn main() {
    let mut queue = Queue::new(3);

    // 入队3个值
    queue.enqueue(1);
    queue.enqueue(2);
    queue.enqueue(3);

    // 打印 3
    println!("{}", queue.size());

    if let Err(err) = queue.enqueue(4) {
        // 打印 Queue capacity exceeded， 容量超出了 3
        println!("{}", err)
    }

    queue.dequeue();
    // 出队一个，打印 2
    println!("{}", queue.size());

    // 打印 Queue { capacity: 3, data: [3, 2] }
    println!("{:?}", queue);
}

实现代码

这里也是主要学习的是 Rust 的语法和算法的思想，所以实现队列使用原生的 Vec 结构来进行实现。

/// 以 Vec 的右侧为队头，左侧为队尾，这样入队的时候时间复杂度为 O(n)，出队的时间复杂度为 O(1)
#[derive(Debug)]
struct Queue<T> {
    // 最大容量
    capacity: usize,
    // 数据容器
    data: Vec<T>,
}

/// 实现队列
impl<T> Queue<T> {
    fn new(capacity: usize) -> Self {
        Self {
            capacity,
            data: Vec::with_capacity(capacity),
        }
    }

    /// 返回队列长度
    fn size(&self) -> usize {
        self.data.len()
    }

    /// 队列是否为空
    fn is_empty(&self) -> bool {
        self.capacity == 0
    }

    /// Vec右侧为队头，入队
    fn enqueue(&mut self, value: T) -> Result<(), String> {
        if self.size() >= self.capacity {
            return Err("capacity exceeded".to_string());
        }

        self.data.insert(0, value);

        Ok(())
    }

    // Vec 右侧为队头，出队
    fn dequeue(&mut self) -> Option<T> {
        if self.is_empty() {
            return None;
        }

        return self.data.pop();
    }
}

对应的 TS 代码

我们这里给出对应的 TS 代码是为了方便大家更好的去对比学习，看看 Rust 的语法和 TS 的语法有啥区别，还有它们的思想有啥区别

class Queue<T> {
  #capacity: number;
  #data: Array<T>;

  constructor(capacity: number) {
    this.#capacity = capacity;
    this.#data = [];
  }

  enqueue(value: T) {
    if (this.size() >= this.#capacity) {
      return "capacity exceeded";
    }

    // 往第一个元素插入值
    // this.#data.unshift(value);
    // 这里主要和上面的 Rust 版本对应上
    this.#data.splice(0, 0, value);
  }

  dequeue(): T | undefined {
    if (this.is_empty()) {
      return undefined;
    }

    this.#data.pop();
  }

  is_empty(): boolean {
    return this.#data.length === 0;
  }

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

总结

这一期了解到了队列的运作，也比较简单，可以了解到 Rust 的 Vec 容器的基础使用，比如在指定位置插入一个元素。

Rust 和 TypeScript 不一样的地方是 TS 可以在 class 中同时存放数据和方法的，但是 Rust 要先声明一个结构体，然后结构体中存放数据，再通过对结构体进行实现，才能把方法添加上。