Implementing Persistent O(1) Stacks and Queues in R

True to their functional roots, most R functions are side-effect-free, and users expect datatypes to be persistent. However, these semantics complicate the creation of efficient and dynamic data structures. Here, we describe the implementation of stack and queue data structures satisfying these conditions in R, available in the CRAN package rstackdeque. Guided by important work in purely functional languages, we look at both partiallyand fully-persistent versions of queues, comparing their performance characteristics. Finally, we illustrate the usefulness of such dynamic structures with examples of generating and solving mazes.

Shawn T. O’Neil

CRAN packages used

rstackdeque, dplyr, microbenchmark, ggplot2, hash, Rcpp

CRAN Task Views implied by cited packages

Graphics, HighPerformanceComputing, NumericalMathematics, Phylogenetics


Text and figures are licensed under Creative Commons Attribution CC BY 4.0. The figures that have been reused from other sources don't fall under this license and can be recognized by a note in their caption: "Figure from ...".


For attribution, please cite this work as

O’Neil, "The R Journal: Implementing Persistent O(1) Stacks and Queues in R", The R Journal, 2015

BibTeX citation

  author = {O’Neil, Shawn T.},
  title = {The R Journal: Implementing Persistent O(1) Stacks and Queues in R},
  journal = {The R Journal},
  year = {2015},
  note = {},
  doi = {10.32614/RJ-2015-009},
  volume = {7},
  issue = {1},
  issn = {2073-4859},
  pages = {118-126}