scala - 堆栈 - Scala 实现/性能问题

Question

我一直在看scala-lang关于各种数据结构及其性能特征的注释。
我注意到 immutable.Stack附加和前置都具有 C(常量)复杂度，而 mutable.Stack堆栈的前置复杂度为 C，追加的复杂度为 L(线性)。这让我有点吃惊。
我认为，“附加”意味着只是 push()到栈顶。而且由于前置和附加的复杂性不同，这是否意味着“前置”实际上是将某些东西放在堆栈的底部？为什么它的性能更好(C 表示可变)而不是附加(L 表示可变)？而且，我怎么能在堆栈前加上呢？我在 scaladoc 中看不到任何适合于此的方法.
编辑。
正如@Łukasz 在评论中指出的那样，您可以使用 +: 预先添加并附加到堆栈中。和 :+运营商。问题仍然存在 - 为什么前置比附加到堆栈更好(更快)？我应该添加到底部而不是推到顶部吗？

Answer 1

看起来这张表有错误，或者我没有得到什么。如果你看一下实现，push适用于可变和不可变 Stack需要恒定的时间，并且 :+对于可变和不可变都需要线性时间，因为 :+来自 SeqLike它在线性时间内完成，这对于堆栈作为数据结构非常合理

使用不可变的可变和不可变堆栈 List内部和使用 ::操作，这是恒定的。 List它的追加操作为 L ，所以没办法Stack可以做得更好

对于不可变堆栈，它是:

def push[B >: A](elem: B): Stack[B] = new Stack(elem :: elems)

对于可变的，它是:

def push(elem: A): this.type = { elems = elem :: elems; this }

另请注意不可变 Stack自 2.11 起已弃用

附言我什至检查了 2.12 的最新来源，但似乎代码自 2.11 以来没有改变

P.P.S.我找不到 Stack 的任何插入实现，看着 table 似乎很奇怪只有 Stack在不可变结构中可以插入数据，所以我猜 L该列应该在 append柱子