棧

棧簡介

• 棧作為一種數(shù)據(jù)結(jié)構(gòu)，是一種只能在一端進行插入和刪除操作的特殊線性表。

• 它按照先進后出的原則存儲數(shù)據(jù)，先進入的數(shù)據(jù)被壓入棧底，最后的數(shù)據(jù)在棧頂，需要讀數(shù)據(jù)的時候從棧頂開始彈出數(shù)據(jù)（最后一個數(shù)據(jù)被第一個讀出來）。

棧（stack）又名堆棧，它是一種運算受限的線性表。其限制是僅允許在表的一端進行插入和刪除運算。這一端被稱為棧頂，相對地，把另一端稱為棧底。向一個棧插入新元素又稱作進棧、入?；驂簵?，它是把新元素放到棧頂元素的上面，使之成為新的棧頂元素；從一個棧刪除元素又稱作出?；蛲藯＃前褩ｍ斣貏h除掉，使其相鄰的元素成為新的棧頂元素。

棧的實現(xiàn)步驟：

• 定義一個棧結(jié)構(gòu)Stack
• 定義組成棧結(jié)構(gòu)的棧點StackNode
• 實現(xiàn)棧的初始化函數(shù)new( )
• 實現(xiàn)進棧函數(shù)push( )
• 實現(xiàn)退棧函數(shù)pop( )

定義一個棧結(jié)構(gòu)Stack

#[derive(Debug)]
struct Stack<T> {
    top: Option<Box<StackNode<T>>>,
}

讓我們一步步來分析

• 第一行的#[derive(Debug)]是為了讓Stack結(jié)構(gòu)體可以打印調(diào)試。
• 第二行是定義了一個Stack結(jié)構(gòu)體，這個結(jié)構(gòu)體包含一個泛型參數(shù)T。
• 第三行比較復(fù)雜，在定義StackNode的時候介紹

定義組成棧結(jié)構(gòu)的棧點StackNode

#[derive(Clone,Debug)]
struct StackNode<T> {
    val: T,
    next: Option<Box<StackNode<T>>>,
}

在這段代碼的第三行， 我們定義了一個val保存StackNode的值。

現(xiàn)在我們重點來看看第四行： 我們從里到外拆分來看看，首先是Box<StackNode<T>，這里的Box是 Rust 用來顯式分配堆內(nèi)存的類型：

pub struct Box<T> where T: ?Sized(_);
詳細文檔請參考Rust的標(biāo)準(zhǔn)庫

在 Rust 里面用強大的類型系統(tǒng)做了統(tǒng)一的抽象。在這里相當(dāng)于在堆空間里申請了一塊內(nèi)存保存StackNode<T>。

為什么要這么做了？如果不用Box封裝會怎么樣呢？

如果不用 Box 封裝，rustc 編譯器會報錯，在 Rust 里面，rustc 默認(rèn)使用棧空間，但是這里的StackNode定義的時候使用了遞歸的數(shù)據(jù)結(jié)構(gòu)，next 屬性的類型是 StackNode<T>，而這個類型是無法確定大小的，所有這種無法確定大小的類型，都不能保存在棧空間。所以需要使用Box來封裝。這樣的話next的類型就是一個指向某一塊堆空間的指針，而指針是可以確定大小的，因此能夠保存在?？臻g。

那么為什么還需要使用Option來封裝呢？

Option是 Rust 里面的一個抽象類型，定義如下：

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

Option 里面包括元素，None 和 Some(T) ，這樣就很輕松的描述了 next 指向棧尾的元素的時候，都是在 Option 類型下，方便了功能實現(xiàn)，也方便了錯誤處理。Option 還有很多強大的功能，讀者可以參考下面幾個連接：

Option標(biāo)準(zhǔn)庫文檔

Error Handling in Rust

rustbyexample 的 Options with Results部分

實現(xiàn) new( ) push( ) pop( )

接下來是實現(xiàn) stack 的主要功能了。

impl<T> Stack<T> {
    fn new() -> Stack<T> {
        Stack{ top: None }
    }

    fn push(&mut self, val: T) {
        let mut node = StackNode::new(val);
        let next = self.top.take();
        node.next = next;
        self.top = Some(Box::new(node));
    }

    fn pop(&mut self) -> Option<T> {
        let val = self.top.take();
        match val {
            None => None,
            Some(mut x) => {
                self.top = x.next.take();
                Some(x.val)
            },
        }
    }
}

• new( )比較簡單，Stack 初始化的時候為空，棧頂元素 top 就沒有任何值，所以 top 為 None。

• push( )的主要功能是往棧里面推入元素，把新的 StackNode 指向 Stack 里面舊的值，同時更新 Stack 棧頂指向新進來的值。

  這里有個需要注意的地方是第8行代碼里面，let next = self.top.take();，使用了 Option 類型的 take 方法：
  fn take(&mut self) -> Option<T> 它會把 Option 類型的值取走，并把它的元素改為 None

• pop( )的功能是取出棧頂?shù)脑?，如果棧頂?None 則返回 None。

完整代碼（包含簡單的測試）

#[derive(Debug)]
struct Stack<T> {
    top: Option<Box<StackNode<T>>>,
}

#[derive(Clone,Debug)]
struct StackNode<T> {
    val: T,
    next: Option<Box<StackNode<T>>>,
}

impl <T> StackNode<T> {
    fn new(val: T) -> StackNode<T> {
        StackNode { val: val, next: None }
    }
}

impl<T> Stack<T> {
    fn new() -> Stack<T> {
        Stack{ top: None }
    }

    fn push(&mut self, val: T) {
        let mut node = StackNode::new(val);
        let next = self.top.take();
        node.next = next;
        self.top = Some(Box::new(node));
    }

    fn pop(&mut self) -> Option<T> {
        let val = self.top.take();
        match val {
            None => None,
            Some(mut x) => {
                self.top = x.next.take();
                Some(x.val)
            },
        }
    }
}

fn main() {
    #[derive(PartialEq,Eq,Debug)]
    struct TestStruct {
        a: i32,
    }

    let a = TestStruct{ a: 5 };
    let b = TestStruct{ a: 9 };

    let mut s = Stack::<&TestStruct>::new();
    assert_eq!(s.pop(), None);

    s.push(&a);
    s.push(&b);
    println!("{:?}", s);

    assert_eq!(s.pop(), Some(&b));
    assert_eq!(s.pop(), Some(&a));
    assert_eq!(s.pop(), None);
}