栈简介

  • 栈作为一种数据结构,是一种只能在一端进行插入删除操作的特殊线性表。

  • 它按照先进后出的原则存储数据,先进入的数据被压入栈底,最后的数据在栈顶,需要读数据的时候从栈顶开始弹出数据(最后一个数据被第一个读出来)。

栈(stack)又名堆栈,它是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算。这一端被称为栈顶,相对地,把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈,它是把新元素放到栈顶元素的上面,使之成为新的栈顶元素;从一个栈删除元素又称作出栈或退栈,它是把栈顶元素删除掉,使其相邻的元素成为新的栈顶元素。

栈的实现步骤:

  • 定义一个栈结构Stack
  • 定义组成栈结构的栈点StackNode
  • 实现栈的初始化函数new( )
  • 实现进栈函数push( )
  • 实现退栈函数pop( )

定义一个栈结构Stack

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

让我们一步步来分析

  • 第一行的#[derive(Debug)]是为了让Stack结构体可以打印调试。
  • 第二行是定义了一个Stack结构体,这个结构体包含一个泛型参数T
  • 第三行比较复杂,在定义StackNode的时候介绍

定义组成栈结构的栈点StackNode

  1. #[derive(Clone,Debug)]
  2. struct StackNode<T> {
  3. val: T,
  4. next: Option<Box<StackNode<T>>>,
  5. }

在这段代码的第三行, 我们定义了一个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 里面的一个抽象类型,定义如下:

  1. pub enum Option<T> {
  2. None,
  3. Some(T),
  4. }

Option 里面包括元素,None 和 Some(T) ,这样就很轻松的描述了 next 指向栈尾的元素的时候,都是在 Option 类型下,方便了功能实现,也方便了错误处理。Option 还有很多强大的功能,读者可以参考下面几个连接:

Option标准库文档

Error Handling in Rust

rustbyexample 的 Options with Results部分

实现 new( ) push( ) pop( )

接下来是实现 stack 的主要功能了。

  1. impl<T> Stack<T> {
  2. fn new() -> Stack<T> {
  3. Stack{ top: None }
  4. }
  5. fn push(&mut self, val: T) {
  6. let mut node = StackNode::new(val);
  7. let next = self.top.take();
  8. node.next = next;
  9. self.top = Some(Box::new(node));
  10. }
  11. fn pop(&mut self) -> Option<T> {
  12. let val = self.top.take();
  13. match val {
  14. None => None,
  15. Some(mut x) => {
  16. self.top = x.next.take();
  17. Some(x.val)
  18. },
  19. }
  20. }
  21. }
  • new( )比较简单,Stack 初始化的时候为空,栈顶元素 top 就没有任何值,所以 topNone

  • push( )的主要功能是往栈里面推入元素,把新的 StackNode 指向 Stack 里面旧的值,同时更新 Stack 栈顶指向新进来的值。

    这里有个需要注意的地方是第8行代码里面,let next = self.top.take();,使用了 Option 类型的 take 方法:
    fn take(&mut self) -> Option<T>
    它会把 Option 类型的值取走,并把它的元素改为 None

  • pop( )的功能是取出栈顶的元素,如果栈顶为 None 则返回 None。

完整代码(包含简单的测试)

  1. #[derive(Debug)]
  2. struct Stack<T> {
  3. top: Option<Box<StackNode<T>>>,
  4. }
  5. #[derive(Clone,Debug)]
  6. struct StackNode<T> {
  7. val: T,
  8. next: Option<Box<StackNode<T>>>,
  9. }
  10. impl <T> StackNode<T> {
  11. fn new(val: T) -> StackNode<T> {
  12. StackNode { val: val, next: None }
  13. }
  14. }
  15. impl<T> Stack<T> {
  16. fn new() -> Stack<T> {
  17. Stack{ top: None }
  18. }
  19. fn push(&mut self, val: T) {
  20. let mut node = StackNode::new(val);
  21. let next = self.top.take();
  22. node.next = next;
  23. self.top = Some(Box::new(node));
  24. }
  25. fn pop(&mut self) -> Option<T> {
  26. let val = self.top.take();
  27. match val {
  28. None => None,
  29. Some(mut x) => {
  30. self.top = x.next.take();
  31. Some(x.val)
  32. },
  33. }
  34. }
  35. }
  36. fn main() {
  37. #[derive(PartialEq,Eq,Debug)]
  38. struct TestStruct {
  39. a: i32,
  40. }
  41. let a = TestStruct{ a: 5 };
  42. let b = TestStruct{ a: 9 };
  43. let mut s = Stack::<&TestStruct>::new();
  44. assert_eq!(s.pop(), None);
  45. s.push(&a);
  46. s.push(&b);
  47. println!("{:?}", s);
  48. assert_eq!(s.pop(), Some(&b));
  49. assert_eq!(s.pop(), Some(&a));
  50. assert_eq!(s.pop(), None);
  51. }