前言
昨天我们把单链栈又优化了一遍，但是存在一点瑕疵，今天我们继续优化！
持久性单链栈（Persistent Singly-Linked Stack）
上一小节中，我们实现了&mut的链，但是我们最后是采用take夺取所有权的方式来实现next的，这样不好，意味着我们只能迭代一次！，我们接下来就是来解决这个问题。
相信有基础的看到这里就知道我们要用到啥了（这里就不说了，等会自然知晓）。
还是在src文件夹下新开一个third.rs文件，同样在lib.rs中引入。
layout
之前的结构是没办法做到我们要实现的效果的，所以我们得重头开始，重新设计一个结构。
先来看个例子：
这不是一个常见的例子，但是可以很好的描述我们的问题。
来看结构图更直观点：
这个逼是真受欢迎呢
但是在常规rust safe中不允许有这么牛逼的数据存在！
现在这仨都在争夺B的所有权，按理说是不行的，但是这种场景确实存在（比如：图,一个节点不一定只有一个相邻节点），那咋整呢？
对于有gc(garbage collection)的语言来说，这完全不用考虑，等待这货没人引用的时候自然就给它销毁了。
但是在没有gc的语言中就存在心智负担了，对于这种场景，Rust提供了引用计数的方案，可以想成是一个非常小的gc：Rc(reference counting)，这货简单地说就是Box<T>的升级版。（跨线程相关的的是Arc）
补充一下课外知识：相信前端的各位老哥都有过刷面试题的经历，其中比较常见的就是旧版IE使用引用计数的gc方案导致可能存在循环引用的问题导致内存泄露的问题（毕竟红宝书前面几张的内容），简单地说就是A中引用了B，而B中引用了A，那么这个数据的计数就永远不会变成0也就没办法回收。而rust中采用这种方案解决多所有权的问题其实也会遇到循环引用的问题，这也是rust目前没办法解决的问题，所以在基础书中有明确指明这个问题（不过把这当做特性就有点那个了。。。大方承认不就好了，毕竟这是个大难题）。
相关点的链接：Reference Cycles Can Leak Memory - The Rust Programming Language (rust-lang.org)
以及我的知乎链接：rust基础学习--day33：智能指针 - 知乎 (zhihu.com)
ok，扯远了。
回到我们这里，Rc是Box<T>的升级版，但是它允许同时存在多个引用指向这个内存数据。（注意不是可变引用，Rc不允许变！后面我们会介绍如何实现可变）
那么我们的基础结构就是将Box替换成Rc即可：
然后我们来实现几个基础方法
基础方法
new方法我们不用改动，直接照抄即可。
然后就是实现pop和push，不过我们这里替换下名字，pop和push有些不太符合链表的命名，我们缓存prepend和tail，相应的，逻辑也要做一下调整。
我们先来实现prepand，它接收一个list和一个元素，并且返回一个list。
根据前面的实现逻辑，我们要给这个元素生成相应的节点，然后让它的next指向list。
不过需要注意，我们要满足前面说到的结构，也就是新生成的list和旧的list同时存在，也就是说旧的list的head节点同时存在两个**拥有者**，不过这一点我们并不需要担心，因为我们前面已经将Box改成Rc了，所以是没问题的。
注意这里的clone()方法，它是Rc的clone，而不是指针的clone。
额外知识点： Clone这个trait类似Copy，但是并不是Copy，两者的关系相当于浅复制和深复制，浅复制意味着只是复制一个指针，深复制则是完全复制一个新的。rust几乎所有类型都实现了这个trait。我们自定义的类型也可以通过#[derive(Clone)]的方式快捷实现Clone trait（派生宏），Copy也可以通过derive注册，不过如果你的字段类型存在不能Copy的类型，比如String，那么你的类型也不能实现Copy。
扯远了，Rc的clone是创建一个新的指针，同时计数+1，也就是说这个节点的拥有者又多了一个。也可以Rc::new(self.head)这么写，效果一样。
接着我们来实现tail，和之前pop的逻辑一样，都是返回这个节点，不同的是我们返回的是第二个节点的clone，也就是一个新的list，原本的list本身不发生变化。
但是报错了
类型不对，map需要F返回一个U
但是我们的next是Option<U>
这个问题好解决，直接给他unwrap不就好了嘛
但是这里我们还有其它更优雅的方案：使用and_then
它的作用基本和map一样，是如果是None就返回None，否则执行我们的闭包，也就是F，但是有别于map，and_then的 F要求返回一个Option<U>
然后搞几个测试用例测试下：
注意这里的链式调用prepand.prepand...，由于使用的是计数，而前一个节点只有后一个节点这一个拥有者，所以和原来的基本没差别。
不过和之前相比，我们可以直接在任意prepand链中间断开，然后生成一个新的list，这也是完全没问题的，非常方便！
另外我们的Iter也不需要调整，因为是返回一个不可变引用，并不会改变list本身，所以完全没问题：
不过它的测试用例要微调下：
至于IterMut和IntoIter我们暂时还不能实现，因为它俩需要支持对list的改动，单独一个Rc是无法做到的。
Drop
和前面使用Box的不同，因为Rc支持多拥有者，回收的方式不同，得等到没有引用的时候才可以销毁，所以我们还需要判断下这个节点是否还存在计数。
这里采用的是try_unwrap，顾名思义，就是尝试unwrap这个Option，返回的是Result<T, E>。
当然，我们更常用的是strong_count，也就是获取这个rc当前是否还有引用，另外还有个weak_count，我们双向链表会用到，用来处理循环引用的问题。
Arc
这里为啥会莫名其妙介绍Arc......
简单地说就是这货是多线程用的Rc。
不过相对于Rc，Arc的引用计数变化是原子级别的（atomically）（rc前面的A就是atomic），这就意味着存在损耗，但是多线程为什么需要原子级别的改动呢？因为会导致引用计数不准，所以得在原子层面上去计数。
所以Arc能不用就不用（多线程必用）。
然后**补充点多线程相关的知识：**其实我们以前也学过rust基础学习--day34：并发 - 知乎 (zhihu.com)。我们依靠Send和Sync，它俩都是marker trait，也就是它们只是用来标记这个数据是啥属性的，thread-safe还是thread-unsafe，其中Send表示表示这个数据在线程之间传递是安全的，Sync则表示这个数据在线程之间分享是safe的，不会造成线程抢数据的问题。rust会帮你自动实现这俩trait，大多数类型也都是Send和Sync，除了一些内部可变（interior mutability）的类型，这里就不多说了，链接里都有。
代码整合
总结
ok，单链栈到这里就结束旅程了，接下来我们准备实现一个双向链表！