I am using a mutable ArrayStack
in Scala but do not know how to access the last element (and second to last element) efficiently (constant time) without popping the items from the stack. Is it possible to access the elements?
Efficient retrieval of last and second to last element of ArrayStack in Scala?
3.5k views Asked by KaliMa At
2
There are 2 answers
0
On
stack(4)
returns 5th element in constant time
As for the last element - the answer depends on which version you're using. Scala 2.11.7 was still running stack.last
on linear time as it was using TraversableLike
implementation:
def last: A = {
var lst = head
for (x <- this)
lst = x
lst
}
This was fixed in version 2.12.0-M4 using the IndexedSeqOptimized
trait.
Therefor to my understanding - if you're using an older version of Scala (which was the case when the question was posted) you should use stack(stack.size - 1)
which returns last element in constant time.
Those operations are constant time.