有效檢索Scala中ArrayStack的倒數第二個元素？

Question

我在Scala中使用了一個可變的ArrayStack，但不知道如何高效地（恆定時間）訪問最後一個元素（以及倒數第二個元素），而無需從堆棧中彈出項目。可以訪問元素嗎？

Answer 1

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

這些操作是恆定時間。

Answer 2

stack(4)收益在固定時間

至於最後一個元素第五元素 - 答案取決於哪個版本您正在使用。斯卡拉2.11.7線性時間仍在運行stack.last，因爲它是用TraversableLike實現：

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

這是在版本2.12.0 fixed-M4使用IndexedSeqOptimized特質。 因此，據我的理解 - 如果您使用的是舊版本的Scala（這是發佈問題時的情況），您應該使用stack(stack.size - 1)，它會在常量時間內返回最後一個元素。