DEQueue - Maple Help

Online Help

All Products    Maple    MapleSim


DEQueue

An object-based double-ended queue

 

Description

Examples

Compatibility

Description

• 

The DEQueue appliable object provides an efficient means to construct, manipulate, and query double-ended queues.

• 

Unlike a Maple list, adding or replacing an element in a DEQueue does not allocate a new container. As such, it can be efficiently used in loops to build up a sequence an element at a time, adding new elements at either end.

Construction

• 

The DEQueue function returns a new DEQueue object.

– 

If called with a single argument that is either a Maple list or a DEQueue object, the returned object contains the elements in the argument.

– 

Otherwise, the returned object contains each distinct argument as an element.

Modification

• 

The following functions modify the contents of a DEQueue object. The dq argument denotes a DEQueue object. The expr argument denotes any Maple expression or sequence thereof.

– 

clear(dq) : Clears dq.

– 

pop_front(dq) : Deletes and returns one element from the front of dq.

– 

pop_back(dq) : Deletes and returns one element from the back of dq.

– 

push_front(dq,expr) : Pushes expr onto the front of dq.

– 

push_back(dq,expr) : Pushes expr onto the back of dq.

– 

dq ,= expr : Equivalent to push_back(dq,expr).

• 

Because elements can be pushed onto and popped from either end of a DEQueue, it can be used as both a first-in-first-out (FIFO) queue (by using push_back and pop_front), or as a stack (by using push_front and pop_front).

Inspection

• 

The following functions inspect the content of a DEQueue object. The dq arguments denote DEQueue objects.

– 

dq = other or `=`(dq,other) : When evaluated in a boolean context, returns true if dq and other are both DEQueue objects with identical content, false otherwise.

– 

expr in dq or `in`(expr,dq) : Returns true if expr is an element of dq, false otherwise.

– 

empty(dq) : Returns true if dq is empty, false otherwise.

– 

entries(dq) : Returns an expression sequence of all the entries in dq, with each entry enclosed in a list by default.

– 

front(dq) or back(dq) : Returns the element at the front or back of dq, without removing it.

– 

has(dq,expr) : Returns true if any element of dq contains expr, false otherwise.

– 

hastype(dq,typ) : Returns true if any element of dq contains an expression of the specified type, false otherwise.

– 

indets(dq,typ) : Returns a Maple set of all indeterminates in dq. If the optional typ parameter is specified, then returns the expressions of type typ.

– 

indices(dq) : Returns an expression sequence of all the indices of dq, with each index enclosed in a list by default.

– 

lowerbound(dq) : Returns the lower index bound (always 1)

– 

max(dq) : Returns the maximum element of dq. Behaves like max on lists.

– 

member(expr,dq) : Returns true if  expr is an element of dq, false otherwise.  The three argument form of member is not supported.

– 

min(dq) : returns the minimum element of dq.  Behaves like min on lists.

– 

numboccur(dq,expr) : Count the number of occurrences of expr in dq, either as an element or within elements.

– 

numelems(dq) : Returns the number of elements in dq.

– 

upperbound(dq) : Returns the upper index (same as the output of numelems).

• 

Each of the above functions is already available in Maple for built-in Maple structures such as lists and Arrays. Please refer to the help page for each function for details on usage.

Mapping, Selection, Removal, and Substitution

• 

The map, select, remove, selectremove, and subs functions operate on a DEQueue object. Refer to their help pages for the calling sequences. By default they create a new DEQueue object, but if called with the inplace index option, they update the existing DEQueue object. The dq argument denotes a DEQueue object.

– 

map(fcn,dq) : Apply a procedure, fcn, to each element of dq.

– 

select(fcn,dq) : Select elements of dq for which fcn returns true.

– 

remove(fcn,dq) : Remove elements of dq for which fcn returns true.

– 

selectremove(fcn,dq) : Produce two DEQueues, one containing selected elements and the other removed elements.

– 

subs(eqns,dq) : Substitute subexpressions in the content of dq.

Conversion

• 

The convert functions can be used to convert a DEQueue object to and from other Maple structures.

– 

convert(dq,typ) : Convert a DEQueue to the specified type.

– 

convert(expr,DEQueue) : Convert expr to a DEQueue object. expr must be a list, set, or rtable.

Indexing

• 

Integer indices can be used to extract or reassign a single element of a DEQueue.

Iteration

• 

The DEQueue object exports a ModuleIterator function, allowing the DEQueue object to be used in loops and iterations (seq, add, etc.).

• 

Note: The queue and stack commands have been deprecated. Use the superceding command, DEQueue instead.

Examples

Construction

• 

Create a DEQueue with three elements.

Q1DEQueuea,b,c

Q1DEQueuea,b,c

(1)
• 

Copy Q1.

Q2DEQueueQ1

Q2DEQueuea,b,c

(2)
• 

Create a DEQueue from a Maple list.

Q3DEQueueb,c,d

Q3DEQueueb,c,d

(3)

Modification

• 

Remove c from the back of Q1 and insert z at the front.

pop_backQ1

c

(4)

push_frontQ1,z

DEQueuez,a,b

(5)
• 

Add c to each element in Q2, doing so inplace.

mapinplace`+`,Q2,c

DEQueuea+c,b+c,2c

(6)
• 

Replace all occurrences of c inside Q2 with d, doing so inplace.

subsinplacec=d,Q2

DEQueuea+d,b+d,2d

(7)

Inspection

• 

Use member to determine whether a given element is a member of Q1.

Q1DEQueuea,b,c,4

Q1DEQueuea,b,c,4

(8)

memberb,Q1

true

(9)
• 

Use has to test for the occurrence of a subexpression in any of the members of the set.

hasQ1,c

true

(10)

indetsQ1,numeric

4

(11)

Conversion

• 

Create a DEQueue object by converting a Vector.

Q1convertVector10,symbol=v,DEQueue

Q1DEQueuev1,v2,v3,v4,v5,v6,v7,v8,v9,v10

(12)
• 

Convert Q1 to a list.

convertQ1,list

v1,v2,v3,v4,v5,v6,v7,v8,v9,v10

(13)

Indexing

• 

Use indexing to extract each element of a DEQueue.

Q1DEQueuea,b,c,d

Q1DEQueuea,b,c,d

(14)

seqi=Q1i,i=1..numelemsQ1

1=a,2=b,3=c,4=d

(15)
• 

Reassign the value at the second index.

Q1223:

seqi=Q1i,i=1..numelemsQ1

1=a,2=23,3=c,4=d

(16)

Iteration

• 

Iterate through each element in Q1.

seqx,xinQ1

a,23,c,d

(17)
• 

Add the elements of Q2.

addx,xinQ2

a+4d+b

(18)

forind,valinQ2doprintind,valenddo

1,a+d

2,b+d

3,2d

(19)

Usage

• 

The DEQueue object provides an efficient way to construct a list an element at a time, in a loop.  Doing so with standard Maple lists is inefficient in that each addition creates a new list; as such the operation is On2 in time and memory, where n is the number of elements. The following compares the memory and time required to create a list of twenty thousand elements using lists and a DEQueue object.

MapleLists := proc(n :: posint)
 local i, s;
    s := [];
    for i to n do
        s := [op(s), i];
    end do:
    numelems(s);
end proc:
DEQueues := proc(n :: posint)
local i, s;
    s := DEQueue();
    for i to n do
        push_back(s,-i);
    end do;
    numelems(s);
end proc:

CodeTools:-UsageMapleLists20000

memory used=1.49GiB, alloc change=24.48MiB, cpu time=7.84s, real time=5.11s, gc time=6.27s

20000

(20)

CodeTools:-UsageDEQueues20000

memory used=13.77MiB, alloc change=8.00MiB, cpu time=199.00ms, real time=204.00ms, gc time=0ns

20000

(21)

Compatibility

• 

The DEQueue object was introduced in Maple 2021.

• 

For more information on Maple 2021 changes, see Updates in Maple 2021.

See Also

list

Object