Efficient retrieval of last and second to last element of ArrayStack in Scala?

3.5k views Asked by At

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?

2

There are 2 answers

2
Jean Logeart On BEST ANSWER
stack(4)    // returns 5th element
stack.last  // returns last element

Those operations are constant time.

0
yellow 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.