Rust 栈与队列：基于 Vec 的有趣封装与特性扩展

在 Rust 中，基于Vec封装栈与队列并进行特性扩展是超级常见且实用的操作。下面我们就来详细介绍一下，顺便用一些生活中的例子来协助你理解，让编程变得像玩游戏一样有趣！

基于Vec封装栈

栈就像一个堆叠的盘子，最后放上去的盘子会最先被拿下来，这就是 “后进先出（LIFO）” 的原则。在 Rust 中，我们可以用Vec来轻松实现一个栈。

rust

struct Stack<T> {
    elements: Vec<T>,
}

impl<T> Stack<T> {
    fn new() -> Self {
        Stack {
            elements: Vec::new(),
        }
    }

    fn push(&mut self, item: T) {
        self.elements.push(item);
    }

    fn pop(&mut self) -> Option<T> {
        self.elements.pop()
    }

    fn is_empty(&self) -> bool {
        self.elements.is_empty()
    }
}

Rust 栈与队列：基于 Vec 的有趣封装与特性扩展

这里我们定义了一个Stack结构体，它包含一个Vec<T>类型的elements字段，用来存储栈中的元素。然后我们为Stack结构体实现了一些方法：

new方法：用于创建一个空的栈，就像准备一个空的盘子堆一样。
push方法：把元素压入栈中，就像把盘子一个一个地叠上去。
pop方法：从栈中弹出元素，最后放进去的元素会最先被弹出，就像从盘子堆顶上拿盘子一样。
is_empty方法：检查栈是否为空，看看盘子堆里还有没有盘子。

我们可以这样使用这个栈：

rust

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

    while let Some(item) = stack.pop() {
        println!("Popped: {}", item);
    }

    println!("Is stack empty? {}", stack.is_empty());
}

基于Vec封装队列

队列则像排队买电影票的人群，先来的人会先买到票，也就是 “先进先出（FIFO）” 的原则。我们可以用Vec来实现一个简单的队列，不过为了让队列的操作更高效，我们一般会实现一个循环队列。

rust

struct CircularQueue<T> {
    data: Vec<Option<T>>,
    head: usize,
    tail: usize,
    capacity: usize,
}

impl<T> CircularQueue<T> {
    fn new(capacity: usize) -> Self {
        let mut data = Vec::with_capacity(capacity);
        for _ in 0..capacity {
            data.push(None);
        }
        CircularQueue {
            data,
            head: 0,
            tail: 0,
            capacity,
        }
    }

    fn enqueue(&mut self, item: T) -> bool {
        if (self.tail + 1) % self.capacity == self.head {
            return false;
        }
        self.data[self.tail] = Some(item);
        self.tail = (self.tail + 1) % self.capacity;
        true
    }

    fn dequeue(&mut self) -> Option<T> {
        if self.head == self.tail {
            return None;
        }
        let item = self.data[self.head].take();
        self.head = (self.head + 1) % self.capacity;
        item
    }

    fn is_empty(&self) -> bool {
        self.head == self.tail
    }
}

这里的CircularQueue结构体包含一个Vec<Option<T>>类型的data字段，用来存储队列中的元素，head和tail分别表明队列的头部和尾部的索引，capacity表明队列的容量。

new方法：创建一个指定容量的循环队列，初始化data向量，并将head和tail都设置为 0。
enqueue方法：将元素入队，如果队列已满则返回false，否则将元素放入tail位置，并更新tail索引。
dequeue方法：将元素出队，如果队列为空则返回None，否则取出head位置的元素，并更新head索引。
is_empty方法：检查队列是否为空，通过比较head和tail索引是否相等来判断。

使用示例：

rust

fn main() {
    let mut queue = CircularQueue::new(3);
    queue.enqueue(1);
    queue.enqueue(2);
    queue.enqueue(3);

    if let Some(item) = queue.dequeue() {
        println!("Dequeued: {}", item);
    }

    queue.enqueue(4);

    while let Some(item) = queue.dequeue() {
        println!("Dequeued: {}", item);
    }

    println!("Is queue empty? {}", queue.is_empty());
}

特性扩展

我们还可以为栈和队列扩展一些其他的特性，列如实现Iterator trait，让它们可以像迭代器一样被遍历。

对于栈，我们可以这样扩展：

rust

impl<T> std::iter::IntoIterator for Stack<T> {
    type Item = T;
    type IntoIter = std::vec::IntoIter<T>;

    fn into_iter(self) -> Self::IntoIter {
        self.elements.into_iter()
    }
}

这样我们就可以像下面这样遍历栈中的元素了：

rust

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

    for item in stack {
        println!("Item in stack: {}", item);
    }
}

对于队列，我们也可以类似地实现Iterator trait，不过要根据队列的特点来实现next方法：

rust

impl<T> std::iter::Iterator for CircularQueue<T> {
    type Item = T;

    fn next(&mut self) -> Option<Self::Item> {
        self.dequeue()
    }
}

然后就可以遍历队列了：

rust

fn main() {
    let mut queue = CircularQueue::new(3);
    queue.enqueue(1);
    queue.enqueue(2);
    queue.enqueue(3);

    for item in &mut queue {
        println!("Item in queue: {}", item);
    }
}

编译说明

要编译这些代码，你只需要把代码保存到一个以.rs为后缀的文件中，列如stack_queue.rs。然后在命令行中进入到该文件所在的目录，运行rustc stack_queue.rs命令，就会生成一个可执行文件。如果你的代码没有错误，就可以运行这个可执行文件来查看结果啦，就像打开一个神秘的宝箱，看看里面是不是你想要的东西！