Functional Data Structures in R: Advanced Statistical Programming in R

© Thomas Mailund 2017

Thomas Mailund, Functional Data Structures in R, https://doi.org/10.1007/978-1-4842-3144-9_4

4. Bags, Stacks, and Queues

Thomas Mailund¹ 

(1)Aarhus N, Denmark

In this chapter, we start building data structures that are more complex than simple linked lists and unbalanced trees, but still relatively simple compared to those in future chapters. We will consider three abstract data structures: the bag, the list, and the queue. The bag is just a set, but one where we don’t value membership queries highly enough to make that operation efficient—we just want to be able to construct collections of elements that we can efficiently traverse later. The stack is a last-in-first-out collection of elements, where we can efficiently extract ...