A Dequeue is a double-ended queue so elements can be added to either end.
Here we create an dequeue of integers from a list. Notice that the order in the list is the order in the dequeue.
a:Dequeue INT:= dequeue [1,2,3,4,5]
[1,2,3,4,5]
We can remove the top of the dequeue using dequeue!:
dequeue! a
1
Notice that the use of dequeue! is destructive (destructive operations in FriCAS usually end with ! to indicate that the underylying data structure is changed).
a
[2,3,4,5]
The extract! operation is another name for the dequeue! operation and has the same effect. This operation treats the dequeue as a BagAggregate:
extract! a
2
and you can see that it also has destructively modified the dequeue:
a
[3,4,5]
Next we use enqueue! to add a new element to the end of the dequeue:
enqueue!(9,a)
9
Again, the enqueue! operation is destructive so the dequeue is changed:
a
[3,4,5,9]
Another name for enqueue! is insert!, which treats the dequeue as a BagAggregate:
insert!(8,a)
[3,4,5,9,8]
and it modifies the dequeue:
a
[3,4,5,9,8]
The front operation returns the item at the front of the dequeue:
front a
3
The back operation returns the item at the back of the dequeue:
back a
8
The bottom! operation returns the item at the back of the dequeue:
bottom! a
8
and it modifies the dequeue:
a
[3,4,5,9]
The depth function returns the number of elements in the dequeue:
depth a
4
The height function returns the number of elements in the dequeue:
height a
4
The insertBottom! function adds the element at the end:
insertBottom!(6,a)
6
and it modifies the dequeue:
a
[3,4,5,9,6]
The extractBottom! function removes the element at the end:
extractBottom! a
6
and it modifies the dequeue:
a
[3,4,5,9]
The insertTop! function adds the element at the top:
insertTop!(7,a)
7
and it modifies the dequeue:
a
[7,3,4,5,9]
The extractTop! function adds the element at the top:
extractTop! a
7
and it modifies the dequeue:
a
[3,4,5,9]
The top function returns the top element:
top a
3
and it does not modifies the dequeue:
a
[3,4,5,9]
The top! function returns the top element:
top! a
3
and it modifies the dequeue:
a
[4,5,9]
The reverse! operation destructively reverses the elements of the dequeue:
reverse! a
[9,5,4]
The rotate! operation moves the top element to the bottom:
rotate! a
[5,4,9]
The inspect function returns the top of the dequeue without modification, viewed as a BagAggregate:
inspect a
5
The empty? operation returns true only if there are no element on the dequeue, otherwise it returns false:
empty? a
false
The # (length) operation:
#a
3
The length operation does the same thing:
length a
3
The less? predicate will compare the dequeue length to an integer:
less?(a,9)
true
The more? predicate will compare the dequeue length to an integer:
more?(a,9)
false
The size? operation will compare the dequeue length to an integer:
size?(a,#a)
true
and since the last computation must alwasy be true we try:
size?(a,9)
false
The parts function will return the dequeue as a list of its elements:
parts a
[5,4,9]
If we have a BagAggregate of elements we can use it to construct a dequeue:
bag([1,2,3,4,5])$Dequeue(INT)
[1,2,3,4,5]
The empty function will construct an empty dequeue of a given type:
b:=empty()$(Dequeue INT)
[]
and the empty? predicate allows us to find out if a dequeue is empty:
empty? b
true
The sample function returns a sample, empty dequeue:
sample()$Dequeue(INT)
[]
We can copy a dequeue and it does not share storage so subsequent modifications of the original dequeue will not affect the copy:
c:=copy a
[5,4,9]
The eq? function is only true if the lists are the same reference, so even though c is a copy of a, they are not the same:
eq?(a,c)
false
However, a clearly shares a reference with itself:
eq?(a,a)
true
But we can compare a and c for equality:
(a=c)@Boolean
true
and clearly a is equal to itself:
(a=a)@Boolean
true
and since a and c are equal, they are clearly NOT not-equal:
a~=c
false
We can use the any? function to see if a predicate is true for any element:
any?(x+->(x=4),a)
true
or false for every element:
any?(x+->(x=11),a)
false
We can use the every? function to check every element satisfies a predicate:
every?(x+->(x=11),a)
false
We can count the elements that are equal to an argument of this type:
count(4,a)
1
or we can count against a boolean function:
count(x+->(x>2),a)
3
You can also map a function over every element, returning a new dequeue:
map(x+->x+10,a)
[15,14,19]
Notice that the orignal dequeue is unchanged:
a
[5,4,9]
You can use map! to map a function over every element and change the original dequeue since map! is destructive:
map!(x+->x+10,a)
[15,14,19]
Notice that the orignal dequeue has been changed:
a
[15,14,19]
The member function can also get the element of the dequeue as a list:
members a
[15,14,19]
and using member? we can test if the dequeue holds a given element:
member?(14,a)
true
See Also: