数据结构与算法-Rust 版读书笔记-2线性数据结构-队列

数据结构与算法-Rust 版读书笔记-2线性数据结构-队列

1、队列：先进先出

队列是项的有序集合，其中，添加新项的一端称为队尾，移除项的另一端称为队首。一个元素在从队尾进入队列后，就会一直向队首移动，直到它成为下一个需要移除的元素为止。

2、Rust 预备知识

1、Some

rust为了处理情况设置的两个枚举类型，分别是enum Option 和enum Result。

Option的枚举情况有两种，分别是代表有的Some()和代表无的None。 如果是有返回值，则可以通过if let，match，unwrap，？等多种方法对应情况取出Some包裹的值，如果没有则是None。

Result的枚举情况也是有两种，表示正确的Ok()和表示错误的Err()。同样也是match，unwrap等等对应方法去提取。分别提取对应情况的内容。

3、队列的 Rust 代码实现、运行结果

queue.rs

/*
 * @Description: 
 * @Author: tianyw
 * @Date: 2023-12-10 17:43:34
 * @LastEditTime: 2023-12-11 21:46:30
 * @LastEditors: tianyw
 */
// 定义队列
#[derive(Debug)] // Debug 是派生宏的名称，此语句为 Queue 结构体实现了 Debug trait

pub struct Queue<T> { // pub 表示公开的
    cap: usize, // 容量
    data: Vec<T>, // 数据容器
}

impl<T> Queue<T> { // impl 用于定义类型的实现，如实现 new 方法、is_empty 方法等
    // 初始化空栈
    pub fn new(size: usize) -> Self { // 指代 Queue 类型
        Self {
           cap: size,
           data:Vec::with_capacity(size)
        }
    }

    pub fn is_empty(&self) -> bool {
        0 == Self::len(&self)
    }

    pub fn is_full(&self) -> bool {
        self.len() == self.cap
    }

    pub fn len(&self) -> usize { // &self 只可读
        self.data.len()
    }

    // 清空
    pub fn clear(&mut self) { // &mut self 可读、可写
        self.data = Vec::with_capacity(self.cap)
    }

    // 判断是否有剩余空间，如果有的话，就将数据添加到队列中
   pub fn enquue(&mut self, val: T) -> Result<(), String> {
    if self.len() == self.cap {
        return  Err("No space available".to_string());
    }
    self.data.insert(0, val);
    Ok(())
   }

   // 数据出队
   pub fn dequeue(&mut self) -> Option<T> {
    if self.len() > 0 {
        self.data.pop()
    }else {
        None
    }
   }

    // 以下是为队列实现的迭代功能
    // into_iter：队列改变，成为迭代器
    // iter: 队列不变，得到不可变迭代器
    // iter_mut: 队列不变，得到可变迭代器
    pub fn into_iter(self) -> IntoIter<T> {
        IntoIter(self)
    }

    pub fn iter(&self) -> Iter<T> {
        let mut iterator = Iter { stack: Vec::new() };
        for item in self.data.iter() {
            iterator.stack.push(item);
        }
        iterator
    }

    pub fn iter_mut(&mut self) -> IterMut<T> {
        let mut iterator = IterMut { stack: Vec::new() };
        for item in self.data.iter_mut() {
            iterator.stack.push(item);
        }
        iterator
    }

    
}

// 实现三种迭代功能
pub struct IntoIter<T>(Queue<T>);
impl<T:Clone> Iterator for IntoIter<T> {
    type Item = T;
    fn next(&mut self) -> Option<Self::Item> {
        if !self.0.is_empty() {
            Some(self.0.data.remove(0))
        } else {
            None
        }
    }
}

pub struct Iter<'a,T:'a> { stack: Vec<&'a T>, }
impl<'a,T> Iterator for Iter<'a,T> {
    type Item = &'a T;
    fn next(&mut self) -> Option<Self::Item> {
        if 0 != self.stack.len() {
            Some(self.stack.remove(0)) // 索引移除
        }else {
            None
        }
    }
}

pub struct IterMut<'a,T:'a> { stack: Vec<&'a mut T> }
impl<'a,T> Iterator for IterMut<'a,T> {
    type Item = &'a mut T;
    fn next(&mut self) -> Option<Self::Item> {
       if 0 != self.stack.len() {
        Some(self.stack.remove(0))
       }else {
        None
       }
    }
}    

main.rs

/*
 * @Description: 
 * @Author: tianyw
 * @Date: 2023-12-11 21:29:04
 * @LastEditTime: 2023-12-11 21:54:22
 * @LastEditors: tianyw
 */

mod queue;
fn main() {
    basic();
    iter();

    fn basic() {
        let mut q = queue::Queue::new(4);
        let _r1 = q.enquue(1);
        let _r2 = q.enquue(2);
        let _r3 = q.enquue(3);
        let _r4 = q.enquue(4); // 入队

        if let Err(error) = q.enquue(5) {
            println!("Enqueue error:{error}")
        }

        if let Some(data) = q.dequeue() { // 出队
            println!("dequeue data: {data}");
        }else {
            println!("empty queue");
        }

        println!("empty: {}, len: {}", q.is_empty(),q.len());
        println!("full: {}",q.is_full());
        println!("q: {:?}",q);
        q.clear();
        println!("{:?}",q);
    }


    fn iter() {
        let mut q = queue::Queue::new(4);
        let _r1 = q.enquue(1);
        let _r2 = q.enquue(2);
        let _r3 = q.enquue(3);
        let _r4 = q.enquue(4);

        let sum1 = q.iter().sum::<i32>();
        let mut addend = 0;
        for item in q.iter_mut() {
            *item += 1;
            addend += 1;
        }
        let sum2 = q.iter().sum::<i32>(); // vec 的 sum 方法
        println!("{sum1} + {addend} = {sum2}");
        println!("sum = {}",q.into_iter().sum::<i32>())
    }
}

cargo run 运行结果

队列的典型应用是模拟以FIFO方式管理数据的真实场景。

应用：烫手山芋游戏

// hot_potato.rs
　
fn hot_potato(names: Vec<&str>, num: usize) -> &str {
    // 初始化队列，将人名入队
    let mut q = Queue::new(names.len());
    for name in names { let _nm = q.enqueue(name); }
　
    while q.size() > 1 {
        // 出入栈中的人名，相当于传递山芋
        for _i in 0..num {
            let name = q.dequeue().unwrap();
            let _rm = q.enqueue(name);
        }
　
        // 出入栈达到num次，删除一个人名
        let _rm = q.dequeue();
    }
　
    q.dequeue().unwrap()
}
　
fn main() {
    let name = vec!["Mon","Tom","Kew","Lisa","Marry","Bob"];
    let survivor = hot_potato(name, 8);
    println!("The survival person is {survivor}");
    // 输出“The survival person is Marry”
}

注意，在上面的实现中，计数值8大于队列中的人名数量6。但这不存在问题，因为队列就像一个圈，到了队尾就会重新回到队首，直至达到计数值。