數據結構與算法-Rust 版讀書筆記-2線性數據結構-雙端隊列

1、雙端隊列

deque又稱為雙端隊列，雙端隊列是與隊列類似的項的有序集合。deque有兩個端部：首端和尾端。deque不同于隊列的地方就在于項的添加和刪除是不受限制的，既可以從首尾兩端添加項，也可以從首尾兩端移除項。在某種意義上，這種混合線性結構提供了棧和隊列的所有功能。

雖然deque擁有棧和隊列的許多特性，但其不需要像它們一樣強制地進行LIFO和FIFO排序，這取決于如何添加和刪除數據。deque既可以當作棧使用，也可以當作隊列使用，但最好不要如此，因為不同的數據結構都有自身的特性，它們均是為了不同的計算目的而設計的。

2、雙端隊列的 Rust 代碼實現、運行結果

queue.rs

/** @Description: * @Author: tianyw* @Date: 2023-12-10 17:43:34* @LastEditTime: 2023-12-11 22:19:06* @LastEditors: tianyw*/
// 定義隊列
#[derive(Debug)]pub struct Deque<T> { // pub 表示公開的cap: usize, // 容量data: Vec<T>, // 數據容器
}impl<T> Deque<T> { // impl 用于定義類型的實現，如實現 new 方法、is_empty 方法等// 初始化空棧pub fn new(cap: usize) -> Self { Self {cap: cap,data:Vec::with_capacity(cap)}}pub fn is_empty(&self) -> bool {0 == self.len()}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)}// Vec 的末尾為隊首pub fn add_front(&mut self, val: T) -> Result<(), String> {if self.len() == self.cap {return  Err("No space available".to_string());}self.data.push(val);Ok(())}// Vec 的首部為隊尾pub fn add_rear(&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 remove_front(&mut self) -> Option<T> {if self.len() > 0 {self.data.pop()}else {None}}// 從隊尾移除數據pub fn remove_rear(&mut self) -> Option<T> {if self.len() > 0 {Some(self.data.remove(0))}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>(Deque<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 22:21:01* @LastEditors: tianyw*/mod deque;
fn main() {basic();iter();fn basic() {let mut d = deque::Deque::new(4);let _r1 = d.add_front(1);let _r2 = d.add_front(2);let _r3 = d.add_rear(3);let _r4 = d.add_rear(4); // 入隊if let Err(error) = d.add_front(5) {println!("Enqueue error:{error}")}println!("{:?}",d);match d.remove_rear() {Some(data) => println!("remove rear data {data}"),None => println!("empty deque"),}match d.remove_front() {Some(data) => println!("remove front data {data}"),None => println!("empty deque"),}println!("empty: {},len: {}",d.is_empty(),d.len());println!("full: {},{:?}",d.is_full(),d);d.clear();println!("{:?}",d);}fn iter() {let mut d = deque::Deque::new(4);let _r1 = d.add_front(1);let _r2 = d.add_front(2);let _r3 = d.add_rear(3);let _r4 = d.add_rear(4);let sum1 = d.iter().sum::<i32>();let mut addend = 0;for item in d.iter_mut() {*item += 1;addend += 1;}let sum2 = d.iter().sum::<i32>(); // vec 的 sum 方法println!("{sum1} + {addend} = {sum2}");assert_eq!(14,d.into_iter().sum::<i32>());}
}

cargo run 運行結果

應用：回文檢測

// palindrome_checker.rsfn palindrome_checker(pal: &str) -> bool {// 數據入隊let mut d = Deque::new(pal.len());for c in pal.chars() {let _r = d.add_rear(c);}let mut is_pal = true;while d.size() > 1 && is_pal {// 出隊首尾字符let head = d.remove_front();let tail = d.remove_rear();// 比較首尾字符，若不同，則字符串非回文if head != tail {is_pal = false;}}is_pal
}fn main() {let pal = "rustsur";let is_pal = palindrome_checker(pal);println!("{pal} is palindrome string: {is_pal}");// 輸出“rustsur is palindrome string: true”let pal = "panda";let is_pal = palindrome_checker(pal);println!("{pal} is palindrome string: {is_pal}");// 輸出“panda is palindrome string: false”
}