DequeueΒΆ

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:

  • )show Stack
  • )show ArrayStack
  • )show Queue
  • )show Dequeue
  • )show Heap
  • )show BagAggregate

Table Of Contents

This Page