數據結構與算法-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。但這不存在問題，因為隊列就像一個圈，到了隊尾就會重新回到隊首，直至達到計數值。