棧

棧簡介

• 棧作為一種數據結構，是一種只能在一端進行插入和刪除操作的特殊線性表。

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

棧（stack）又名堆棧，它是一種運算受限的線性表。其限制是僅允許在表的一端進行插入和刪除運算。這一端被稱為棧頂，相對地，把另一端稱為棧底。向一個棧插入新元素又稱作進棧、入棧或壓棧，它是把新元素放到棧頂元素的上面，使之成為新的棧頂元素；從一個棧刪除元素又稱作出棧或退棧，它是把棧頂元素刪除掉，使其相鄰的元素成為新的棧頂元素。

棧的實現步驟：

• 定義一個棧結構Stack
• 定義組成棧結構的棧點StackNode
• 實現棧的初始化函數new( )
• 實現進棧函數push( )
• 實現退棧函數pop( )

定義一個棧結構Stack

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

讓我們一步步來分析

• 第一行的#[derive(Debug)]是為了讓Stack結構體可以打印調試。
• 第二行是定義了一個Stack結構體，這個結構體包含一個泛型參數T。
• 第三行比較複雜，在定義StackNode的時候介紹

定義組成棧結構的棧點StackNode

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

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

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

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

在 Rust 裡面用強大的類型系統做了統一的抽象。在這裡相當於在堆空間裡申請了一塊內存保存StackNode<T>。

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

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

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

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

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

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

Option標準庫文檔

Error Handling in Rust

rustbyexample 的 Error handling

實現 new( ) push( ) pop( )

接下來是實現 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( )的功能是取出棧頂的元素，如果棧頂為 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);
}