R6DS (version 1.1.0)

RDeque: The RDeque reference class

Description

The RDeque reference class implements the data structure double-ended queue (deque).

Usage

RDeque

Format

An object of class R6ClassGenerator of length 24.

Immutable Methods

The immutable methods do not change the nodes of the instance.

peekleft

This function is an active method which returns the value of the leftmost node of the deque. It returns NULL if the deque is empty.

peek

This function is an active method which returns the value of the rightmost node of the deque. It returns NULL if the deque is empty.

Mutable Methods

The mutable methods changes the nodes of the instance.

appendleft(..., collapse=NULL)

The appendleft method creates nodes containing the values in ... and collapse, and the push them into the deque from the left. Note that if you push elements in this manner:

instance$appendleft(elem1, elem2, elem3)

The order of them inside the deque will be

elem3, elem2, elem1, ...

from left to right, and elem3 will be the new head of the deque.

append(..., collapse=NULL)

The append method creates nodes containing the values in ... and collapse, and push them into the deque from the right, which is equivalent to the push in RStack and enqueue in RQueue.

popleft()

The popleft method returns and removes the leftmost element in the deque, which is equivalent to the dequeue in RQueue. It returns NULL if the deque is empty.

pop()

The pop method returns and removes the rightmost element in the deque, which is equivalent to the pop in RStack. It returns NULL if the deque is empty.

Details

A deque is an ordered list of items combining both the stack and the queue. Each node in the DLL has three fields: val storing the value of the node, prev pointing to the previous node and next pointing to the next node.

The deque is slightly more powerful than stack and queue, as it can append elements from left or the head. See RStack and RQueue for the introductions of the two classes. It has a generalized version: the doubly linked list (DLL), see RDLL.

Different from the RStack and RQueue classes, you can check the leftmost and rightmost elements by using peekleft and peek methods. Note that they are both active methods and do not change the deque but just return the elements.

The elements in the deque are not necessarily to be of the same type, and they can even be of function type.

References

For the details about the deque data structure, see Deque at Wikipedia.

See Also

RStack, RQueue, and R6DS for the introduction of the reference class and some common methods

Examples

# NOT RUN {
### create a new instance

# to create a new instance of the class
deque <- RDeque$new()

# the previous RDeque instance will be removed by running the following
# and the memory allocated for that one will be cleared,
# as now, the variable deque points to another instance of the class.
deque <- RDeque$new(0, 1, 2, collapse=list(3, 4))
# the following sentence is equivalent to the above
deque <- RDeque$new(0, 1, 2, 3, 4)
# where the numbers 0, 1, 2, 3, 4 are enqueued into the deque

### append and appendleft

# it can be one single element
deque$append(5)
# it can be several elements separated by commas
# note the whole list will be one element of the deque
# because it is not passed through the collapse argument
deque$append(list(a=10,b=20), "Hello world!")
# the collapse argument takes a list whose elements will be collapsed
# but the elements' names will not be saved
deque$append(collapse = list(x=100,y=200))
# they can be used together
deque$append("hurrah", collapse = list("RDeque",300))

# this string will be the new head
deque$appendleft("a string")
# we can update the head by
deque$appendleft("string3","string2","string1")
# "string1" will be the leftmost

### peekleft and peek
deque$peekleft
# "string1"
deque$peek
# 300

### popleft and pop

val <- deque$popleft()
# "string1"
val <- deque$pop()
# 300

# then we keep dequeuing!
while(!is.null(val)) val <- deque$pop()

# }

Run the code above in your browser using DataCamp Workspace