A Queue object is represented as a list ordered by first-in, first-out. It operates like a line of people, where the “next” person is the one at the front of the line.
Here we create an queue of integers from a list. Notice that the order in the list is the order in the queue.
a:Queue INT:= queue [1,2,3,4,5]
[1,2,3,4,5]
We can remove the top of the queue 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 pop! operation and has the same effect. This operation treats the queue as a BagAggregate:
extract! a
2
and you can see that it also has destructively modified the queue:
a
[3,4,5]
Next we use enqueue! to add a new element to the end of the queue:
push!(9,a)
9
Again, the push! operation is destructive so the queue is changed:
a
[3,4,5,9]
Another name for enqueue! is insert!, which treats the queue as a BagAggregate:
insert!(8,a)
[3,4,5,9,8]
and it modifies the queue:
a
[3,4,5,9,8]
The inspect function returns the top of the queue without modification, viewed as a BagAggregate:
inspect a
8
The empty? operation returns true only if there are no element on the queue, otherwise it returns false:
empty? a
false
The front operation returns the front of the queue without modification:
front a
3
The back operation returns the back of the queue without modification:
back a
8
The rotate! operation moves the item at the front of the queue to the back of the queue:
rotate! a
[4,5,9,8,3]
The # (length) operation:
- #a
- 5
The length operation does the same thing:
length a
5
The less? predicate will compare the queue length to an integer:
less?(a,9)
true
The more? predicate will compare the queue length to an integer:
more?(a,9)
false
The size? operation will compare the queue 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 queue as a list of its elements:
parts a
[8,9,3,4,5]
If we have a BagAggregate of elements we can use it to construct a queue:
bag([1,2,3,4,5])$Queue(INT)
[1,2,3,4,5]
The empty function will construct an empty queue of a given type:
b:=empty()$(Queue INT)
[]
and the empty? predicate allows us to find out if a queue is empty:
empty? b
true
The sample function returns a sample, empty queue:
sample()$Queue(INT)
[]
We can copy a queue and it does not share storage so subsequent modifications of the original queue will not affect the copy:
c:=copy a
[4,5,9,8,3]
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)
5
You can also map a function over every element, returning a new queue:
map(x+->x+10,a)
[14,15,19,18,13]
Notice that the orignal queue is unchanged:
a
[4,5,9,8,3]
You can use map! to map a function over every element and change the original queue since map! is destructive:
map!(x+->x+10,a)
[14,15,19,18,13]
Notice that the orignal queue has been changed:
a
[14,15,19,18,13]
The member function can also get the element of the queue as a list:
members a
[18,19,13,14,15]
and using member? we can test if the queue holds a given element:
member?(14,a)
true
See Also: