rstack: Create a new, empty rstack

In rstackdeque: Persistent Fast Amortized Stack and Queue Data Structures

Description

An rstack is a "Last In, First Out" (LIFO) structure imagined as being organized from top (last in) to bottom (first in), supporting efficient insertion into the top, removal from the top, and peeking/accessing the top element. All functions supported by rstacks are side-effect free.

Usage

rstack()

Details

Other handy functions supported by rstacks include as.list and as.data.frame (the latter of which requires that all elements can be appended to become rows of a data frame in a reasonable manner). Operations are amortized O(1).

The rstack class also supports rev - this operation is O(N), and results in a copy. This means previous versions will retain their O(1) amortized nature (if we assume the cost of the reverse is charged to the newly created stack), at the cost of memory usage. However, this also means that if stacks are used in a non-persistent way, e.g. s <- rev(s), then the garbage collector is free to clean up old versions of the data.

Value

an empty rstack.

References

Okasaki, Chris. Purely Functional Data Structures. Cambridge University Press, 1999.

See Also

insert_top for insertion, without_top for removal, and peek_top for peeking.

Examples

s <- rstack()
s <- insert_top(s, "a")
s <- insert_top(s, "b")
print(s)

sl <- without_top(s)
print(sl)
print(s)

b <- peek_top(s)
print(b)

rstackdeque documentation built on May 2, 2019, 4:15 a.m.