rdeque {rstackdeque}

Create a new empty rdeque

Description

Creates a new, empty, rdeque ready for use.

Usage

rdeque()

Details

An rdeque provided both "Last In, First Out" (LIFO) and "First In, First Out" (FIFO) access; envisaged as queue, elements may be added or removed from the front or the back with insert_front, insert_back, without_front, and without_back. The front and back elements may be retrieved with peek_front and peek_back.

Internally, rdeques are stored as a pair of rstacks; they provide O(1)-amortized insertion and removal, so long as they are not used persistently (that is, the variable storing the deque is always replaced by the modified version, e.g. s <- without_front(s)). When used persistently (e.g. s2 <- without_front(s), which results in two deques being accessible), this cannot be gauranteed. When an O(1) worst-cast, fully persistent FIFO queue is needed, the rpqueue from this package provides these semantics. However, there is a constant-time overhead for rpqueues, such that rdeques are often more efficient (and flexible) in practice, even in when used persistently.

Other useful functions 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).

Value

a new empty rdeque.

References

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

See Also

rstack for a fast LIFO-only structure.

Examples

d <- rdeque()
d <- insert_front(d, "a")
d <- insert_front(d, "b")
d <- insert_back(d, "c")
d <- insert_back(d, "d")
print(d)

d2 <- without_back(d)
print(d2)
print(d)

b <- peek_front(d)
print(b)