不可变 仙人掌栈 实现。

仙人掌栈的其他术语包括 父指针树、意大利面栈 和 萨瓜罗栈。更多信息请参阅 维基百科。

// Quickstart
extern crate kaktus;
// the trait `Stack` needs to be importet for `Stack`/`VStack` to work
use kaktus::{Stack, Stack};

let root = Stack::root(0);
let one = root.push(1);
assert_eq!(*one.pop().unwrap(), 0);
assert_eq!(*one, 1);

概述

本库中描述的栈与传统栈在一点上有决定性的不同，它们是 不可变的。这意味着值本身表示栈

let root = Stack::root(0);
let one = root.push(1);
let two = root.push(2);
assert_eq!(*two, 2);

进一步，从栈中弹出值仅返回父节点--原始值（以及因此表示的栈）仍然有效

let one_ = two.pop().unwrap();
assert_eq!(*one_, 1);
// `two` is still valid
assert_eq!(*two, 2);

为了比较，以下是栈通常是如何实现的

// traditional stack
let mut stack = vec![0];
stack.push(1);
stack.push(2);
let two = stack.pop().unwrap();
let one = stack.pop().unwrap();

仙人掌栈

由于不可变属性，可以从同一个父节点生成多个值，使其实际上成为一棵树

// tree structure:
// 0 -- 1 -- 2
//  \
//   3 -- 4 -- 5

let root = Stack::root(0);
let two  = root.push(1).push(2);
let five = root.push(3).push(4).push(5);

assert_eq!(*two, 2);
assert_eq!(*five, 5);

库内容

此库提供两种栈实现：Stack 和 VStack。简而言之：Stack 使用递归（指针）架构，而 VStackc 使用向量来存储栈的数据。