在 Scala 中高效检索 ArrayStack 的最后一个和倒数第二个元素？

Question

我在 Scala 中使用可变 ArrayStack 但不知道如何在不从堆栈中弹出项目的情况下有效地（恒定时间）访问最后一个元素（和倒数第二个元素）。是否可以访问元素？

Answer 1

stack(4)    // returns 5th element
stack.last  // returns last element

这些操作是常数时间。

Answer 2

stack(4) returns常数时间内的第5个元素

至于最后一个元素 - 答案取决于您使用的是哪个版本。 Scala 2.11.7 在线性时间上仍然是 运行 stack.last，因为它使用 TraversableLike 实现：

def last: A = {
    var lst = head
        for (x <- this)
            lst = x
        lst
}

这是 fixed 在版本 2.12.0-M4 中使用 IndexedSeqOptimized 特性。 因此，据我了解-如果您使用的是旧版本的 Scala（问题发布时就是这种情况），您应该使用 stack(stack.size - 1) 其中 returns 恒定时间的最后一个元素。