1.5 出栈

4 分钟阅读

原文链接: https://rust-unofficial.github.io/too-many-lists/first-pop.html

和 push 一样，pop 要修改链表。与 push 不同，我们实际上要返回点什么。但 pop 还要处理一个棘手的边界情况：链表为空怎么办？为此我们用可靠的 Option 类型：

1
2
3
pub fn pop(&mut self) -> Option<i32> {
    // TODO
}

Option<T> 是一个枚举，表示某个值可能存在。可以是 Some(T) 或 None。我们可以像对 Link 那样自己写枚举，但我们希望用户能看懂返回类型是什么，而 Option 太常见了，每个人都认识。事实上它如此基础，以至于每个文件里都会隐式导入，连同它的变体 Some 和 None（所以我们不必写 Option::None）。

Option<T> 上的尖括号表示 Option 在 T 上是泛型的。也就是说你可以为任何类型做 Option！

那么，我们有这个 Link，怎么判断是 Empty 还是有 More？用 match 做模式匹配！

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
pub fn pop(&mut self) -> Option<i32> {
    match self.head {
        Link::Empty => {
            // TODO
        }
        Link::More(node) => {
            // TODO
        }
    };
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
> cargo build

error[E0308]: mismatched types
  --> src/first.rs:27:30
   |
27 |     pub fn pop(&mut self) -> Option<i32> {
   |            ---               ^^^^^^^^^^^ expected enum `std::option::Option`, found ()
   |            |
   |            this function's body doesn't return
   |
   = note: expected type `std::option::Option<i32>`
              found type `()`

哎呀，pop 必须返回值，我们还没做。我们可以返回 None，但这里用 unimplemented!() 可能更好，表示函数还没实现完。unimplemented!() 是一个宏（! 表示宏），执行到它时会让程序 panic（以受控方式~崩溃）。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
pub fn pop(&mut self) -> Option<i32> {
    match self.head {
        Link::Empty => {
            // TODO
        }
        Link::More(node) => {
            // TODO
        }
    };
    unimplemented!()
}

无条件 panic 是发散函数的例子。发散函数永远不会返回给调用者，所以可以用在期望任意类型值的地方。这里 unimplemented!() 被用在 Option<T> 类型的值的位置上。

还要注意程序里不必写 return。函数里最后一条表达式（基本上就是最后一行）隐式成为返回值。这让很简单的事写得更简洁。你仍然可以像其他类 C 语言一样用 return 提前返回。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
> cargo build

error[E0507]: cannot move out of borrowed content
  --> src/first.rs:28:15
   |
28 |         match self.head {
   |               ^^^^^^^^^
   |               |
   |               cannot move out of borrowed content
   |               help: consider borrowing here: `&self.head`
...
32 |             Link::More(node) => {
   |                        ---- data moved here
   |
note: move occurs because `node` has type `std::boxed::Box<first::Node>`, which does not implement the `Copy` trait
  --> src/first.rs:32:24
   |
32 |             Link::More(node) => {
   |                        ^^^^

拜托 Rust，别烦我们！一如既往，Rust 对我们大发雷霆。幸好这次也把底细说全了！默认情况下，模式匹配会尝试把内容移入新分支，但我们做不到，因为这里不是按值拥有 self。

1
help: consider borrowing here: `&self.head`

Rust 说应该在 match 上加引用来修。🤷‍♀️ 试试：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
pub fn pop(&mut self) -> Option<i32> {
    match &self.head {
        Link::Empty => {
            // TODO
        }
        Link::More(node) => {
            // TODO
        }
    };
    unimplemented!()
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
> cargo build

warning: unused variable: `node`
  --> src/first.rs:32:24
   |
32 |             Link::More(node) => {
   |                        ^^^^ help: consider prefixing with an underscore: `_node`
   |
   = note: #[warn(unused_variables)] on by default

warning: field is never used: `elem`
  --> src/first.rs:13:5
   |
13 |     elem: i32,
   |     ^^^^^^^^^
   |
   = note: #[warn(dead_code)] on by default

warning: field is never used: `next`
  --> src/first.rs:14:5
   |
14 |     next: Link,
   |     ^^^^^^^^^^

好耶，又能编译了！现在理清逻辑。我们要做一个 Option，先建个变量。Empty 时返回 None。More 时返回 Some(i32)，并改链表 head。那就基本上这么做？

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
pub fn pop(&mut self) -> Option<i32> {
    let result;
    match &self.head {
        Link::Empty => {
            result = None;
        }
        Link::More(node) => {
            result = Some(node.elem);
            self.head = node.next;
        }
    };
    result
}

1
2
3
4
5
6
7
> cargo build
   Compiling lists v0.1.0 (/Users/ADesires/dev/temp/lists)
error[E0507]: cannot move out of borrowed content
  --> src/first.rs:35:29
   |
35 |                 self.head = node.next;
   |                             ^^^^^^^^^ cannot move out of borrowed content

扶额

拍桌

我们试图从 node 移出东西，而手里只有对它的共享引用。

应该退一步想我们要干什么。我们要：

检查链表是否为空。
若为空，直接返回 None
若不为空
- 移除链表 head
- 取出它的 elem
- 用它的 next 替换链表 head
- 返回 Some(elem)

关键是我们要移除东西，也就是要按值拿到链表 head。通过 &self.head 得到的共享引用肯定做不到。我们也「只」有 self 的可变引用，所以移动东西的唯一办法是替换它。看来又要跳 Empty 之舞了！

试试：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
pub fn pop(&mut self) -> Option<i32> {
    let result;
    match mem::replace(&mut self.head, Link::Empty) {
        Link::Empty => {
            result = None;
        }
        Link::More(node) => {
            result = Some(node.elem);
            self.head = node.next;
        }
    };
    result
}

1
2
3
cargo build

   Finished dev [unoptimized + debuginfo] target(s) in 0.22s

我的天

编译通过，没有任何警告！！！！

其实我要加一条个人 lint：我们建了 result 来返回，其实完全没必要！就像函数求值为最后一条表达式，每个块也求值为最后一条表达式。通常我们用分号压制这种行为，让块求值为空元组 ()。这就是像 push 这样不声明返回值的函数返回的东西。

所以可以写成：

1
2
3
4
5
6
7
8
9
pub fn pop(&mut self) -> Option<i32> {
    match mem::replace(&mut self.head, Link::Empty) {
        Link::Empty => None,
        Link::More(node) => {
            self.head = node.next;
            Some(node.elem)
        }
    }
}

更简洁、更地道。注意 Link::Empty 分支完全去掉了花括号，因为只有一条要求值的表达式。简单情况的 nice 简写。

1
2
3
cargo build

   Finished dev [unoptimized + debuginfo] target(s) in 0.22s

不错，还能用！

最后修改 August 23, 2026: 更新 (499855b16)