Stack Class in R - Something More Concise

Question

Does R have a stack that you don't have to code yourself?

Literally, I just want something right out of CS 102.

I wrote the code below, and it works great. But I'd rather have something else more universal and proven.

Does the language have something? Or some package of all the usual algorithms, such as queues, trees, etc as well?

####################################################################################################
# Stack.R - Implments a generalized stack.  Uses Reference Classes since we need mutability.
####################################################################################################

Stack <- setRefClass("Stack",
     fields = list(
        vStack = "vector",
        nTop = "numeric"
     ),
    methods = list(
        initialize = function() {
            nTop <<- 1
        },
        push = function(nItem) {
            vStack <<- c(vStack, nItem)
            nTop <<- nTop + 1
            vStack[nTop-1]
        },
        pop = function() {
            if (nTop == 1) return(NULL)
            nItem <- vStack[nTop-1]
            nTop <<- nTop - 1
            vStack <<- vStack[1:nTop-1]
            nItem
        },
        top = function() {
            vStack[nTop-1]
        }
    )
)

# StackTest <- function() {
#     
#     say("Starting...")
#     s <- Stack()
#     say(s$push(1), " {push}")
#     say(s$push("Hello"), " {push}")
#     say(s$push(2), " {push}")
#     say(s$push("World"), " {push}")
#     say(s$push(3), " {push}")
#     say(s$top(),   " {top}")
#     say(s$top(),   " {top}")
#     say(s$pop(),   " {pop}")
#     say(s$pop(),   " {pop}")
#     say(s$pop(),   " {pop}")
#     say(s$pop(),   " {pop}")
#     say("Finished.")
#     
# }
# 
# StackTest()

Answer 1

Not really answering your question, but (a) reference classes seem to do a good job of changing the memory management so there is less copying, but are not necessarily performant compared to other reference-based implementations; and (b) the "copy-and-append" paradigm in vStack <<- c(vStack, nItem) scales very poorly. Here's a little ticker function

ticker = function(s) {
    i = 0
    t0 = Sys.time()
    while (i < 1000000) {
        s$push(i)
        i <- i + 1
        if (i %% 10000 == 0)
            print(i / as.numeric(Sys.time() - t0)) 
    }
}

with throughput starting at 3,800 operations / s falling to 2,700:

> ticker(Stack())
[1] 3784.634
[1] 3546.138
[1] 3429.046
[1] 3303.904
[1] 3192.252
[1] 3090.162
[1] 3000.161
[1] 2908.317
[1] 2826.459
[1] 2744.961
^C

Here's an incomplete implementation using a local environment

s = local({
    v = numeric()
    list(push=function(elt) v <<- c(v, elt),
         val=function() v)
})

with much higher initial throughput, and with the limitations of the "copy-and-append" strategy now much more apparent.

> ticker(s)
[1] 67933.63
[1] 41231.02
[1] 29095.23
[1] 22347.02
[1] 18274.56
[1] 14007.66
[1] 12436.16
[1] 11122.1
[1] 10034.59
[1] 9123.754
^C

Here's a "pre-allocate-and-fill" strategy adopting the same local environment approach implemented as a function call

stack <- function(type="numeric", length=1000L) {
    v <- vector(type, length)
    i <- 1L
    list(push=function(elt) {
        if (i == length(v))
            length(v) <<- 1.6 * length(v)
        v[[i]] <<- elt
        i <<- i + 1L
    }, val=function() v[seq_len(i - 1L)])
}

and it's improved performance

> ticker(stack())
[1] 155448.8
[1] 170315.3
[1] 174391.1
[1] 177424.6
[1] 179275.5
[1] 180605.6
[1] 179693.4
[1] 180258.7
[1] 180681
[1] 181290.1
^C

I guess all of this just emphasizes your original point, that you'd like a Stack implementation without re-inventing the wheel, and perhaps also @CarlWhitthoft 's implicit point that you can be better off thinking of algorithms that exploit R's vector operations.