Rust 数据结构与算法：4栈：用栈实现进制转换

2、进展转换

将十进制数转换为二进制表示形式的最简单方法是“除二法”，可用栈来跟踪二进制结果。

下面实现一个将十进制数转换为二进制或十六进制的算法，代码如下：

#[derive(Debug)]
struct Stack<T> {size: usize,  // 栈大小data: Vec<T>, // 栈数据
}impl<T> Stack<T> {// 初始化空栈fn new() -> Self {Self {size: 0,data: Vec::new(), // 以 Vec 为低层}}fn is_empty(&self) -> bool {0 == self.size}fn len(&self) -> usize {self.size}// 清空栈fn clear(&mut self) {self.size = 0;self.data.clear();}// 将数据保存在 Vec 的末尾fn push(&mut self, val: T) {self.data.push(val);self.size += 1;}// 将栈顶减 1 后，弹出数据fn pop(&mut self) -> Option<T> {if 0 == self.size {return None;};self.size -= 1;self.data.pop()}// 返回栈顶数据引用和可变引用fn peek(&self) -> Option<&T> {if 0 == self.size {return None;}self.data.get(self.size - 1)}fn peek_mut(&mut self) -> Option<&mut T> {if 0 == self.size {return None;}self.data.get_mut(self.size - 1)}// 以下是为栈实现的迭代功能// into_iter: 栈改变，成为迭代器// iter: 栈不变，得到不可变迭代器// iter_mut：栈不变，得到可变迭代器fn into_iter(self) -> IntoIter<T> {// into_iter()方法获取了一个迭代器，然后进行迭代IntoIter(self)}fn iter(&self) -> Iter<T> {let mut iterator = Iter { stack: Vec::new() };for item in self.data.iter() {iterator.stack.push(item);}iterator}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}
}
// 实现三种迭代功能
struct IntoIter<T>(Stack<T>);
// Iterator 是 Rust 的迭代器 迭代器（iterator）负责遍历序列中的每一项和决定序列何时结束的逻辑。当使用迭代器时，我们无需重新实现这些逻辑。
impl<T: Clone> Iterator for IntoIter<T> {// into_iter()方法获取了一个迭代器，然后进行迭代。type Item = T;fn next(&mut self) -> Option<Self::Item> {// 迭代器之所以成为迭代器，是因为实现了Iterator trait。要实现该特征，最主要的就是实现其中的 next 方法，该方法控制如何从集合中取值，最终返回值的类型是关联类型 Item。if !self.0.is_empty() {self.0.size -= 1;self.0.data.pop()} else {None}}
}
// 'a 生命周期标识 用于帮助编译器检查引用的有效性，避免悬垂引用和使用已被释放的内存。
// 从所有权的角度来理解，就是它可以避免因为Copy或者clone的造成的不必要开销
struct Iter<'a, T: 'a> {stack: Vec<&'a T>, // 'a 被用在了传参类型 T 上
}
impl<'a, T> Iterator for Iter<'a, T> {type Item = &'a T; // 生命周期标识只作用于引用上，且放在&符号之后 如这里的 &'a Tfn next(&mut self) -> Option<Self::Item> {self.stack.pop()}
}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> {self.stack.pop()}
}
fn main() {let num1 = 10;let num2 = 43;let bin_str = base_converter(num1, 2);let hex_str = base_converter(num2, 16);println!("{num1}(十进制) = {bin_str}(二进制), {num2}(十进制) = {hex_str}(十六进制)");
}// 支持将 10进制数 转为 2 进制或 16 进制
fn base_converter(mut dec_num:u32,base:u32) -> String {// digits 对应各种余数的字符形式，尤其是 10-15let digits = ['0','1','2','3','4','5','6','7','8','9','A','B','C','D','E','F'];let mut rem_stack = Stack::new();// 余数入栈while dec_num > 0 {let rem = dec_num % base;rem_stack.push(rem);dec_num /= base;}// 余数出栈并取对应字符以拼接成字符串let mut base_str = "".to_string();while !rem_stack.is_empty() {let rem = rem_stack.pop().unwrap() as usize;base_str += &digits[rem].to_string();}base_str
}

运行结果：