网站运营思路,网络推广公司营销方案,昆明网站建设工作室有哪些,wordpress博客经典插件数据结构与算法-Rust 版读书笔记-2线性数据结构-队列
1、队列#xff1a;先进先出
队列是项的有序集合#xff0c;其中#xff0c;添加新项的一端称为队尾#xff0c;移除项的另一端称为队首。一个元素在从队尾进入队列后#xff0c;就会一直向队首移动#xff0c;直到…数据结构与算法-Rust 版读书笔记-2线性数据结构-队列
1、队列先进先出
队列是项的有序集合其中添加新项的一端称为队尾移除项的另一端称为队首。一个元素在从队尾进入队列后就会一直向队首移动直到它成为下一个需要移除的元素为止。
2、Rust 预备知识
1、Some
rust为了处理情况设置的两个枚举类型分别是enum Option 和enum Result。
Option的枚举情况有两种分别是代表有的Some()和代表无的None。 如果是有返回值则可以通过if letmatchunwrap等多种方法对应情况取出Some包裹的值如果没有则是None。
Result的枚举情况也是有两种表示正确的Ok()和表示错误的Err()。同样也是matchunwrap等等对应方法去提取。分别提取对应情况的内容。
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 QueueT { // pub 表示公开的cap: usize, // 容量data: VecT, // 数据容器
}implT QueueT { // 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) - OptionT {if self.len() 0 {self.data.pop()}else {None}}// 以下是为队列实现的迭代功能// into_iter队列改变成为迭代器// iter: 队列不变得到不可变迭代器// iter_mut: 队列不变得到可变迭代器pub fn into_iter(self) - IntoIterT {IntoIter(self)}pub fn iter(self) - IterT {let mut iterator Iter { stack: Vec::new() };for item in self.data.iter() {iterator.stack.push(item);}iterator}pub fn iter_mut(mut self) - IterMutT {let mut iterator IterMut { stack: Vec::new() };for item in self.data.iter_mut() {iterator.stack.push(item);}iterator}}// 实现三种迭代功能
pub struct IntoIterT(QueueT);
implT:Clone Iterator for IntoIterT {type Item T;fn next(mut self) - OptionSelf::Item {if !self.0.is_empty() {Some(self.0.data.remove(0))} else {None}}
}pub struct Itera,T:a { stack: Veca T, }
impla,T Iterator for Itera,T {type Item a T;fn next(mut self) - OptionSelf::Item {if 0 ! self.stack.len() {Some(self.stack.remove(0)) // 索引移除}else {None}}
}pub struct IterMuta,T:a { stack: Veca mut T }
impla,T Iterator for IterMuta,T {type Item a mut T;fn next(mut self) - OptionSelf::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: Vecstr, 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。但这不存在问题因为队列就像一个圈到了队尾就会重新回到队首直至达到计数值。
