數據結構與算法-Rust 版讀書筆記-2線性數據結構-棧

一、線性數據結構概念

數組、棧、隊列、雙端隊列、鏈表這類數據結構都是保存數據的容器，數據項之間的順序由添加或刪除時的順序決定，數據項一旦被添加，其相對于前后元素就會一直保持位置不變，諸如此類的數據結構被稱為線性數據結構。

線性數據結構有兩端，稱為“左”和“右”，在某些情況下也稱為“前”和“后”，當然也可以稱為頂部和底部，名稱不重要，重要的是這種命名展現出的位置關系表明了數據的組織方式是線性的。這種線性特性和內存緊密相關，因為內存就是一種線性硬件，由此也可以看出軟件和硬件是如何關聯在一起的。

線性數據結構說的并非數據的保存方式，而是數據的訪問方式。

線性數據結構不一定代表數據項在內存中相鄰。以鏈表為例，雖然其中的數據項可能在內存的各個位置，但訪問是線性的。

區分不同線性數據結構的方法是查看它們添加和移除數據項的方式，特別是添加和移除數據項的位置。例如，一些數據結構只允許從一端添加數據項，另一些則允許從另一端移除數據項，還有的允許從兩端操作數據項。這些變種及其組合形式產生了許多在計算機科學領域非常有用的數據結構，它們出現在各種算法中，用于執行各種實際且重要的任務。

1、棧：后進先出

棧是數據項的有序集合，其中，新項的添加和移除總發生在同一端，這一端稱為頂部，與之相對的另一端稱為底部。棧的底部很重要，因為棧中靠近底部的項是存儲時間最長的，最近添加的項最先被移除。這種排序原則有時被稱為后進先出(Last In First Out，LIFO)或先進后出(First In Last Out，FILO)，所以較新的項靠近頂部，較舊的項靠近底部。

2、Rust 預備知識

1、trait

trait類似于Java中的接口，TS 的 interface，C++中的純虛類，但卻又不完全相同。

trait這個單詞，本意為特征，在代碼中的含義就是，讓某個結構體擁有某個特征。

trait Shape {fn area(&self) -> f32{return 0.0; } //該函數是實現可寫可不寫，如果不寫，那么實現該Trait的結構就必須寫，如果這里寫了，那么后面實現該trait的結構就可以不寫fn test(){println!("不寫self參數，則只能通過 :: 的方式進行調用");}
}struct triangle{ //為了簡單，假設其是直角三角形，存放兩個直角邊a: f32,b: f32,
}impl Shape for triangle {fn area(&self) -> f32 {return (self.a*self.b)/2.0;}
}struct square{a: f32
}impl Shape for square {fn area(&self) -> f32 {return self.a*self.a;}
}

通過 trait Shape，使得 triangle、square 都具有了 area 方法。

調用方式：

fn main() {let t=triangle{a: 1.0, b: 2.0};let s=square{a:4.0};//調用帶有self參數的函數t.area();s.area();//調用沒有self參數的函數triangle::test();square::test();
}

其中area函數的參數帶有self，也就是要與具體的結構體對應，調用的時候要用.的方式。

另一種調用方式：

fn main() {let t=triangle{a: 1.0, b: 2.0};let s=square{a:4.0};//調用帶有self參數的函數test_area(&t);test_area(&s);
}fn test_area(shape: &impl Shape){shape.area();
}

用 test_area 函數倆輸出，這個函數的參數為 &impl Shape，意思是：接受實現了這個 Shape trait 的結構體的引用。

這是不是就和println!宏非常像了！現在只要你的任意形狀結構體實現了這個Shape的trait，那么我就能用一個統一的方法（test_area）來輸出你的內容！

所以：

只要你自定義了一個結構體，你想要讓他可以被println!打印出來，你就得為其實現這個trait

如果要拷貝，那就請你實現Clone這個trait，并且顯式的調用clone這個函數，讓你自己清楚的認識到此刻你是在完成一個拷貝數據的工作

#[derive(Clone)]
struct Stu{name: String,age:u32
}fn main() {let s1=Stu{name:String::from("yushi-"),age:100};let s2=s1.clone(); //讓你能清醒的認識到自己在完成一個拷貝的工作println!("{}:{}", s1.name,s1.age); //可用，因為是將內容拷貝給了s2一份println!("{}:{}", s2.name,s2.age);
}

最常用的trait，除了Copy與Clone，還有三個：Debug、Default、PartialEq

其中，Debug是方便我們調試用的：

#[derive(Debug)]
struct Stu{name: String,age:u32
}
fn main() {let s1=Stu{/*省略代碼*/};println!("{:?}", s1);
}

只要你用了Debug這個trait，那么你就無需實現Display這個trait，也可以方便的打印出相關信息

唯一需要注意的點就是，打印Debug信息，你需要在{}中添加:?

如果你還想要打印格式化后的格式信息，讓結構更好看，還可以這樣寫：

println!("{:#?}", s1);

2、Vec

Vec 是一種動態數組，它可以在運行時自動調整大小。

Vec是Rust標準庫的一部分，提供了一種高效、安全的方式來處理大量數據。

基于堆內存申請的連續動態數據類型，其索引、壓入(push)、彈出(pop) 操作的時間復雜度為 O(1) 。

Vec 是 vector 的縮寫。

Vec的底層實現是基于數組的，因此它的性能非常高。Vec可以存儲任何類型的數據，包括整數、浮點數、字符串等。

Vec其實是一個智能指針，用于在堆上分配內存的動態數組。它提供了一些方法來操作數組，如添加、刪除和訪問元素。與C或Python中的數組不同，Vec會自動處理內存分配和釋放，從而避免了常見的內存泄漏和懸掛指針錯誤。

Vec的本質就是一個三元組，指針、長度、容量，在rust標準庫中的定義如下：

pub struct Vec<T, A: Allocator = Global> {buf: RawVec<T, A>,len: usize,
}
impl<T> Vec<T> {#[inline]pub const fn new() -> Self {Vec { buf: RawVec::NEW, len: 0 }}
//...略...
}

Vec的核心功能之一是動態增長和收縮。當向Vec中添加元素時，如果堆上的內存不足，Vec會自動分配更多的內存來容納元素。這個過程稱為“擴容”。同樣，當從Vec中刪除元素時，如果堆上的內存過多，Vec會自動收縮以釋放內存。這個過程稱為“縮容”。這種自動內存管理機制使得使用Vec變得非常方便，同時也避免了手動管理內存的錯誤。

除了基本的添加、刪除和訪問元素操作之外，Vec還提供了許多其他功能。例如，它們可以按索引訪問元素，可以使用迭代器遍歷元素，并且支持多種方法（如push()、pop()、insert()和remove()）來修改Vec的內容。Vec還提供了一些有用的靜態方法（如capacity()、len()和is_empty()），可以用來獲取Vec的屬性。

雖然Vec是一個非常強大的數據結構，但它們也有一些限制。例如，Vec在堆上分配內存，這意味著訪問元素的速度可能會比在棧上分配內存的數組慢。此外，由于Vec是智能指針，因此它們的大小不是固定的，這可能會導致一些編程錯誤。例如，如果嘗試將Vec賦值給一個固定大小的數組或另一個Vec，則會發生編譯時錯誤。

Vec::new()方法

只創建一個空列表時，必須注明類型（否則通不過編譯）。

fn main() {let vec: Vec<i32> = Vec::new();println!("{:?}", vec);
}

Vec::from()方法

 let vec = Vec::from([1,2,3]);

vec! 宏

用于判斷是否相等

fn main() {let vec1 = Vec::from([1,2,3]);println!("{:?}", vec1);let vec2 = vec![1,2,3];println!("{:?}", vec2);assert_eq!(vec1, vec2);assert_eq!(vec1, [1,2,3]);assert_eq!(vec2, [1,2,3]);println!("{}", vec1 == vec2); // 輸出 true
}

創建相同元素 n 的 vec

fn main() {let vec = vec![0; 5];assert_eq!(vec, [0, 0, 0, 0, 0]);println!("{:?}", vec);let vec = vec![1; 3];assert_eq!(vec, [1, 1, 1]);println!("{:?}", vec);let vec = vec![1; 0];
}

因為是數組，所以還有 pop、splice、sort 等等數組具有的方法。

3、impl

**impl是一個關鍵字，用于在類型上實現方法。它是將函數與特定類型（結構體或枚舉）關聯起來的一種方式。impl**主要有兩種用途：

1、實現方法：你可以為特定類型定義方法。然后可以在該類型的實例上調用這些方法。

struct Rectangle {width: u32,height: u32,
}impl Rectangle {fn area(&self) -> u32 {self.width * self.height}
}

在這個示例中，為**Rectangle結構體實現了一個名為area**的方法，用于計算矩形的面積。

2、實現特質（Traits）：Rust中的特質（Trait）類似于其他語言中的接口。它們定義了類型必須提供的功能。使用**impl**，你可以為特定類型實現一個特質，提供特質中定義的必要方法。

trait Describable {fn describe(&self) -> String;
}impl Describable for Rectangle {fn describe(&self) -> String {format!("Rectangle of width {} and height {}", self.width, self.height)}
}

在這里，為**Rectangle實現了Describable**特質，提供了描述矩形的具體方式。

impl 塊中定義的函數可以是獨立的，這意味著將其稱為 Foo::bar()。 如果函數以 self、&self 或 &mut self 作為它的第一個參數，那么也可以使用方法調用語法調用它，這是任何面向對象的程序員都熟悉的特性，比如 foo.bar ()。

4、Self

通常在 Rust 的 trait 和 associated function 中使用 Self 來指代實現該 trait 或調用該 associated function 的類型。

struct Point {x: f32,y: f32,
}impl Point {//關聯函數fn origin() -> Self {Point { x: 0.0, y: 0.0 }}
}fn main() {let p = Point::origin();
}

5、self

self 是一個代表**類型實例（或者是類型的引用或者是值）**的關鍵字，在 Rust 的方法中使用 self 可以引用當前類型的實例或者類型本身。

具體來說，當我們定義一個方法時，使用 self 關鍵字作為方法的第一個參數可以讓我們在調用該方法時直接訪問類型實例本身

struct Point {x: f32,y: f32,
}impl Point {fn distance(&self, other: &Point) -> f32 {let dx = self.x - other.x;let dy = self.y - other.y;(dx * dx + dy * dy).sqrt()}
}

6、 . 和 ::

在Rust中，.和::操作符都可以用來調用方法，但它們的用法有所不同。

.操作符用于調用實例方法。實例方法是定義在類型上的方法，它需要一個類型的實例作為第一個參數（通常稱為self）。**而實例方法（instance methods）與其他語言中的動態方法（dynamic methods）類似。都需要先聲明一個實例后，才可以用的方法。**例如，下面是一個簡單的結構體和一個實例方法的示例：

上面的代碼定義了一個名為Point的結構體，它有兩個字段x和y。然后，我們在impl Point塊中定義了一個名為distance_from_origin的實例方法。這個方法接受一個名為self的參數，它表示調用該方法的實例。在這個方法中，我們使用了self.x和self.y來訪問實例的字段。

在main函數中，我們創建了一個名為p的Point實例，并使用.操作符來調用它的實例方法。也就是說，我們使用了語句p.distance_from_origin()來調用該方法。

而::操作符則用于調用關聯函數。**關聯函數也是定義在類型上的函數，但它不需要一個類型的實例作為第一個參數。Rust中的關聯函數（associated functions）與其他語言中的靜態方法（static methods）類似。**例如，下面是一個簡單的結構體和一個關聯函數的示例：

上面的代碼定義了一個名為Point的結構體，它有兩個字段x和y。然后，我們在impl Point塊中定義了一個名為new的關聯函數。這個函數接受兩個參數：x和y，并返回一個新創建的Point實例。

在main函數中，我們使用::操作符來調用Point類型上的關聯函數。也就是說，我們使用了語句Point::new(3, 4)來調用該函數。

實例方法通常用于操作類型的實例。例如，您可以定義一個Point結構體，它有兩個字段x和y，然后定義一個實例方法來計算點到原點的距離。這個方法需要一個Point類型的實例作為第一個參數，然后使用這個實例的字段來進行計算。

關聯函數通常用于執行與類型相關但不依賴于類型實例的操作。例如，您可以定義一個關聯函數來創建一個新的Point實例。這個函數不需要一個Point類型的實例作為第一個參數，而是接受一些參數來初始化新創建的實例。

在選擇使用實例方法還是關聯函數時，您應該考慮您要執行的操作是否依賴于類型的實例。如果是，則應該使用實例方法；否則，應該使用關聯函數。

7、self 和 &self、mut 和 &mut

&self，表示向函數傳遞的是一個引用，不會發生對象所有權的轉移；

self，表示向函數傳遞的是一個對象，會發生所有權的轉移，對象的所有權會傳遞到函數中。

let b = a;
含義：a綁定的資源A轉移給b，b擁有這個資源A

let b = &a;　　
含義：a綁定的資源A借給b使用，b只有資源A的讀權限

let b = &mut a;　　
含義：a綁定的資源A借給b使用，b有資源A的讀寫權限

let mut b = &mut a;　　
含義：a綁定的資源A借給b使用，b有資源A的讀寫權限。同時，b可綁定到新的資源上面去（更新綁定的能力）

fn do(c: String) {}　　
含義：傳參的時候，實參d綁定的資源D的所有權轉移給c

fn do(c: &String) {}　　
含義：傳參的時候，實參d將綁定的資源D借給c使用，c對資源D只讀

fn do(c: &mut String) {}　　
含義：傳參的時候，實參d將綁定的資源D借給c使用，c對資源D可讀寫

fn do(mut c: &mut String) {}　　
含義：傳參的時候，實參d將綁定的資源D借給c使用，c對資源D可讀寫。同時，c可綁定到新的資源上面去（更新綁定的能力）

8、Option<T>

Option<T> 是 Rust 中的類型系統，來傳播和處理錯誤的類型。

pub enum Option<T> {None,Some(T),
}

Option<T>是一個枚舉類型，要么是Some<T>，要么是None。這能很好地表達有值和無值兩種情況，避免出現Java中的NullPointerException。

9、’ 生命周期標記

生命周期用單引號’加字母表示，置于&后，如&'a、&mut 't

10、unwrap

有的時候我們不想處理或者讓程序自己處理 Err， 有時候我們只要 OK 的具體值就可以了。

針對這兩種處女座訴求， Rust 語言的開發者們在標準庫中定義了兩個幫助函數 unwrap() 和 expect()。

方法	原型	說明
unwrap	unwrap(self):T	如果 self 是 Ok 或 Some 則返回包含的值。 否則會調用宏 panic!() 并立即退出程序
expect	expect(self,msg:&str):T	如果 self 是 Ok 或 Some 則返回包含的值。 否則調用panic!() 輸出自定義的錯誤并退出

expect() 函數用于簡化不希望事情失敗的錯誤情況。而 unwrap() 函數則在返回 OK 成功的情況下，提取返回的實際結果。

unwrap() 和 expect() 不僅能夠處理 Result <T,E> 枚舉，還可以用于處理 Option <T> 枚舉。

fn main(){let result = is_even(10).unwrap();println!("result is {}",result);println!("end of main");
}
fn is_even(no:i32)->Result<bool,String> {if no%2==0 {return Ok(true);} else {return Err("NOT_AN_EVEN".to_string());}
}

編譯運行以上 Rust 代碼，輸出結果如下

thread 'main' panicked at 'called `Result::unwrap()` on 
an `Err` value: "NOT_AN_EVEN"', libcore\result.rs:945:5
note: Run with `RUST_BACKTRACE=1` for a backtrace

11、'_ 匿名生命周期

Rust 2018 允許你明確標記生命周期被省略的地方，對于此省略可能不清楚的類型。 要做到這一點，你可以使用特殊的生命周期'_，就像你可以用語法 let x：_ = ..;明確標記一個類型一樣。

要我們說的話，無論出于什么原因，我們在 &'a str 周圍有一個簡單的封裝：

struct StrWrap<'a>(&'a str);

Rust 版本指南 中文版

3、棧的 Rust 代碼實現、運行結果

stack.rs

/** @Description: * @Author: tianyw* @Date: 2023-12-10 17:43:34* @LastEditTime: 2023-12-10 21:28:31* @LastEditors: tianyw*/
#[derive(Debug)] // Debug 是派生宏的名稱，此語句為 Stack 結構體實現了 Debug traitpub struct Stack<T> { // pub 表示公開的size: usize, // 棧大小data: Vec<T>, // 棧數據 泛型數組
}impl<T> Stack<T> { // impl 用于定義類型的實現，如實現 new 方法、is_empty 方法等// 初始化空棧pub fn new() -> Self { // 指代 Stack 類型Self {size: 0,data: Vec::new() // 初始化空數組}}pub fn is_empty(&self) -> bool {0 == self.size // 結尾沒有分號，表示返回當前值}pub fn len(&self) -> usize { // &self 只可讀self.size // 結尾沒有分號 表示返回當前值}// 清空棧pub fn clear(&mut self) { // &mut self 可讀、可寫self.size = 0;self.data.clear();}// 將數據保存在 Vec 的末尾pub fn push(&mut self, val:T) {self.data.push(val);self.size +=1;}// 在將棧頂減1后，彈出數據pub fn pop(&mut self) -> Option<T> {if 0 == self.size { return None; }self.size -= 1;self.data.pop()}// 返回棧頂數據引用和可變引用pub fn peek(&self) -> Option<&T> {if 0 == self.size {return None;}self.data.get(self.size - 1) // 不帶分號 獲取值并返回}pub 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: 棧不變，得到可變迭代器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>(Stack<T>);
impl<T:Clone> Iterator for IntoIter<T> {type Item = T;fn next(&mut self) -> Option<Self::Item> {if !self.0.is_empty() {self.0.size -= 1;self.0.data.pop()} 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> {self.stack.pop()}
}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> {self.stack.pop()}
}    

main.rs

mod stack;
fn main() {basic();peek();iter();fn basic() {let mut s= stack::Stack::new();s.push(1);s.push(2);s.push(3);println!("size:{},{:?}", s.len(), s);println!("pop {:?},size {}", s.pop().unwrap(), s.len());println!("empty: {}, {:?}", s.is_empty(), s);s.clear();println!("{:?}", s);}fn peek() {let mut s = stack::Stack::new();s.push(1);s.push(2);s.push(3);println!("{:?}", s);let peek_mut = s.peek_mut();if let Some(top) = peek_mut {*top = 4;}println!("top {:?}", s.peek().unwrap());println!("{:?}", s);}fn iter() {let mut s = stack::Stack::new();s.push(1);s.push(2);s.push(3);let sum1 = s.iter().sum::<i32>();let mut addend = 0;for item in s.iter_mut() {*item += 1;addend += 1;}let sum2 = s.iter().sum::<i32>();println!("{sum1} + {addend} = {sum2}");assert_eq!(9, s.into_iter().sum::<i32>());}
}

cargo run 運行結果

這里使用集合容器Vec作為棧的底層實現，因為Rust中的Vec提供了有序集合機制和一組操作方法，只需要選定Vec的哪一端是棧頂就可以實現其他操作了。以下棧實現假定Vec的尾部保存了棧的頂部元素，隨著棧不斷增長，新項將被添加到Vec的末尾。因為不知道所插入數據的類型，所以采用泛型數據類型T。此外，為了實現迭代功能，這里添加了IntoIter、Iter、IterMut三個結構體，以分別完成三種迭代功能。

應用：括號匹配、加減乘除優先級匹配

// par_checker3.rsfn par_checker3(par: &str) -> bool {let mut char_list = Vec::new();for c in par.chars() { char_list.push(c); }let mut index = 0;let mut balance = true;let mut stack = Stack::new();while index < char_list.len() && balance {let c = char_list[index];// 將開始符號入棧if '(' == c || '[' == c || '{' == c {stack.push(c);}// 如果是結束符號，則判斷是否平衡if ')' == c || ']' == c || '}' == c {if stack.is_empty() {balance = false;} else {let top = stack.pop().unwrap();if !par_match(top, c) { balance = false; }}}// 非括號字符直接跳過index += 1;}balance && stack.is_empty()
}fn main() {let sa = "(2+3){func}[abc]"; let sb = "(2+3)*(3-1";let res1 = par_checker3(sa); let res2 = par_checker3(sb);println!("sa balanced:{res1}, sb balanced:{res2}");// (2+3){func}[abc] balanced:true, (2+3)*(3-1 balanced:false
}