Deque - Double-Ended Queue

Deques are a generalization of stacks and queues typically with methods to add, remove and access elements at both sides of the underlying data sequence. As such, the deque can also be used to mimic both stacks and queues.

Usage

deque(...)

as.deque(x)

is.deque(x)

Arguments

...

initial elements put into the Deque.

x

R object of ANY type for as.deque() and is.deque() or of class Deque for the S3 methods.

Details

Methods that alter Deque objects usually come in two versions providing either copy or reference semantics where the latter start with 'ref_' to note the reference semantic, for example, add() and ref_add().

• deque(...) initializes and returns an object of class Deque

• as.deque(x) coerces x to a deque.

• is.deque(x) returns TRUE if x is of class Deque and FALSE otherwise.

• x + y combines x and y into a new deque by appending y to x.

• x - y element-wise removes all items of y from x, given the element was contained in x.

• addleft(.x, ...) adds (possibly named) elements to left side of .x.

• ref_addleft(.x, ...) same as addleft(.x, ...) but adds by reference.

• peek(x, default = NULL) peek at last element. If x is empty, return default.

• peekleft(x, default = NULL) peek at first element. If x is empty, return default.

• ref_pop(.x) pop last element. If .x is empty, an error is given.

• ref_popleft(.x) pop first element. If .x is empty, an error is given.

• rev(x) and ref_rev(x) reverses all elements being done on a copy or in place, respectively.

• rotate(x, n) rotate all elements n steps to the right, If n is negative, rotate to the left.

See also

See container() for all inherited methods. For the full class documentation see Deque() and it's superclass Container().

Examples

d = deque(1, 2, s = "a", v = 1:3)
is.deque(d)
#> [1] TRUE
print(d)
#> |1, 2, s = "a", v = (1L 2L 3L)|
length(d)
#> [1] 4
names(d)
#> [1] ""  ""  "s" "v"
as.list(d)
#> [[1]]
#> [1] 1
#> 
#> [[2]]
#> [1] 2
#> 
#> $s
#> [1] "a"
#> 
#> $v
#> [1] 1 2 3
#> 
rev(d)
#> |v = (1L 2L 3L), s = "a", 2, 1|

l = list(0, 1)
d2 = as.deque(l)
d + d2
#> |1, 2, s = "a", v = (1L 2L 3L), 0, 1|
c(d, d2) # same as d + d2
#> |1, 2, s = "a", v = (1L 2L 3L), 0, 1|
d2 + d
#> |0, 1, 1, 2, s = "a", v = (1L 2L 3L)|
d - d2
#> |2, s = "a", v = (1L 2L 3L)|
c(d2, d) # same as d2 + d
#> |0, 1, 1, 2, s = "a", v = (1L 2L 3L)|
d2 - d
#> |0|
# Math
d = deque(1, 2, -(3:5))
d
#> |1, 2, (-3L -4L -5L)|
abs(d)
#> |1, 2, 3, 4, 5|
cumsum(d)
#> |1, 3, 0, -4, -9|
round(d)
#> |1, 2, -3, -4, -5|
exp(d)
#> |2.718282, 7.389056, 0.04978707, 0.01831564, 0.006737947|

# Summary
range(d)
#> [1] -5  2
min(d)
#> [1] -5
max(d)
#> [1] 2

d1 = deque(1, 1:2)
d2 = deque(2, 1:2)
d1 + d2     # same as c(d1, d2)
#> |1, (1L 2L), 2, (1L 2L)|
d2 + d1     # same as c(d2, d1)
#> |2, (1L 2L), 1, (1L 2L)|

d1 - d2
#> |1|
d2 - d1
#> |2|
d1 - d1
#> ||


d = deque(0)
add(d, a = 1, b = 2)         # |0, a = 1, b = 2|
#> |0, a = 1, b = 2|
addleft(d, a = 1, b = 2)     # |b = 2, a = 1, 0|
#> |b = 2, a = 1, 0|

d = deque(1, 2, 3)
peek(d)
#> [1] 3
peekleft(d)
#> [1] 1
peek(deque())
#> NULL
peek(deque(), default = 0)
#> [1] 0
peekleft(deque(), default = 0)
#> [1] 0
d = deque(1, 2, 3)
ref_pop(d)
#> [1] 3
print(d)
#> |1, 2|
ref_popleft(d)
#> [1] 1
print(d)
#> |2|

try({
ref_pop(deque())  # pop at empty Deque
})
#> Error : pop at empty Deque

d = deque(a = 1, b = 2, 3)
rev(d)
#> |3, b = 2, a = 1|
print(d)
#> |a = 1, b = 2, 3|
ref_rev(d)
#> |3, b = 2, a = 1|
print(d)
#> |3, b = 2, a = 1|

d = deque(1, 2, 3, 4)
rotate(d)
#> |4, 1, 2, 3|
rotate(d, n = 2)
#> |3, 4, 1, 2|