====================================================================
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``