数据结构与算法-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 traitpub 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.rsfn 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。但这不存在问题，因为队列就像一个圈，到了队尾就会重新回到队首，直至达到计数值。