DEQueue - Maple Help

DEQueue

An object-based double-ended queue

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.
 > $\mathrm{Q1}≔\mathrm{DEQueue}\left(a,b,c\right)$
 ${\mathrm{Q1}}{≔}{\mathrm{DEQueue}}{}\left({a}{,}{b}{,}{c}\right)$ (1)
 • Copy Q1.
 > $\mathrm{Q2}≔\mathrm{DEQueue}\left(\mathrm{Q1}\right)$
 ${\mathrm{Q2}}{≔}{\mathrm{DEQueue}}{}\left({a}{,}{b}{,}{c}\right)$ (2)
 • Create a DEQueue from a Maple list.
 > $\mathrm{Q3}≔\mathrm{DEQueue}\left(\left[b,c,d\right]\right)$
 ${\mathrm{Q3}}{≔}{\mathrm{DEQueue}}{}\left({b}{,}{c}{,}{d}\right)$ (3)

Modification

 • Remove c from the back of Q1 and insert z at the front.
 > $\mathrm{pop_back}\left(\mathrm{Q1}\right)$
 ${c}$ (4)
 > $\mathrm{push_front}\left(\mathrm{Q1},z\right)$
 ${\mathrm{DEQueue}}{}\left({z}{,}{a}{,}{b}\right)$ (5)
 • Add c to each element in Q2, doing so inplace.
 > $\mathrm{map}\left[\mathrm{inplace}\right]\left(\mathrm{+},\mathrm{Q2},c\right)$
 ${\mathrm{DEQueue}}{}\left({a}{+}{c}{,}{b}{+}{c}{,}{2}{}{c}\right)$ (6)
 • Replace all occurrences of c inside Q2 with d, doing so inplace.
 > $\mathrm{subs}\left[\mathrm{inplace}\right]\left(c=d,\mathrm{Q2}\right)$
 ${\mathrm{DEQueue}}{}\left({a}{+}{d}{,}{b}{+}{d}{,}{2}{}{d}\right)$ (7)

Inspection

 • Use member to determine whether a given element is a member of Q1.
 > $\mathrm{Q1}≔\mathrm{DEQueue}\left(a,b,c,4\right)$
 ${\mathrm{Q1}}{≔}{\mathrm{DEQueue}}{}\left({a}{,}{b}{,}{c}{,}{4}\right)$ (8)
 > $\mathrm{member}\left(b,\mathrm{Q1}\right)$
 ${\mathrm{true}}$ (9)
 • Use has to test for the occurrence of a subexpression in any of the members of the set.
 > $\mathrm{has}\left(\mathrm{Q1},c\right)$
 ${\mathrm{true}}$ (10)
 > $\mathrm{indets}\left(\mathrm{Q1},\mathrm{numeric}\right)$
 $\left\{{4}\right\}$ (11)

Conversion

 • Create a DEQueue object by converting a Vector.
 > $\mathrm{Q1}≔\mathrm{convert}\left(\mathrm{Vector}\left(10,\mathrm{symbol}=v\right),\mathrm{DEQueue}\right)$
 ${\mathrm{Q1}}{≔}{\mathrm{DEQueue}}{}\left({{v}}_{{1}}{,}{{v}}_{{2}}{,}{{v}}_{{3}}{,}{{v}}_{{4}}{,}{{v}}_{{5}}{,}{{v}}_{{6}}{,}{{v}}_{{7}}{,}{{v}}_{{8}}{,}{{v}}_{{9}}{,}{{v}}_{{10}}\right)$ (12)
 • Convert Q1 to a list.
 > $\mathrm{convert}\left(\mathrm{Q1},\mathrm{list}\right)$
 $\left[{{v}}_{{1}}{,}{{v}}_{{2}}{,}{{v}}_{{3}}{,}{{v}}_{{4}}{,}{{v}}_{{5}}{,}{{v}}_{{6}}{,}{{v}}_{{7}}{,}{{v}}_{{8}}{,}{{v}}_{{9}}{,}{{v}}_{{10}}\right]$ (13)

Indexing

 • Use indexing to extract each element of a DEQueue.
 > $\mathrm{Q1}≔\mathrm{DEQueue}\left(a,b,c,d\right)$
 ${\mathrm{Q1}}{≔}{\mathrm{DEQueue}}{}\left({a}{,}{b}{,}{c}{,}{d}\right)$ (14)
 > $\mathrm{seq}\left(i=\mathrm{Q1}\left[i\right],i=1..\mathrm{numelems}\left(\mathrm{Q1}\right)\right)$
 ${1}{=}{a}{,}{2}{=}{b}{,}{3}{=}{c}{,}{4}{=}{d}$ (15)
 • Reassign the value at the second index.
 > $\mathrm{Q1}\left[2\right]≔23:$
 > $\mathrm{seq}\left(i=\mathrm{Q1}\left[i\right],i=1..\mathrm{numelems}\left(\mathrm{Q1}\right)\right)$
 ${1}{=}{a}{,}{2}{=}{23}{,}{3}{=}{c}{,}{4}{=}{d}$ (16)

Iteration

 • Iterate through each element in Q1.
 > $\left[\mathrm{seq}\left(x,x\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{in}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathrm{Q1}\right)\right]$
 $\left[{a}{,}{23}{,}{c}{,}{d}\right]$ (17)
 • Add the elements of Q2.
 > $\mathrm{add}\left(x,x\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{in}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathrm{Q2}\right)$
 ${a}{+}{4}{}{d}{+}{b}$ (18)
 > $\mathbf{for}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathrm{ind},\mathrm{val}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{in}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathrm{Q2}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{do}\phantom{\rule[-0.0ex]{0.0em}{0.0ex}}\phantom{\rule[-0.0ex]{2.0em}{0.0ex}}\mathrm{print}\left(\mathrm{ind},\mathrm{val}\right)\phantom{\rule[-0.0ex]{0.0em}{0.0ex}}\mathbf{end}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{do}$
 ${1}{,}{a}{+}{d}$
 ${2}{,}{b}{+}{d}$
 ${3}{,}{2}{}{d}$ (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 $\mathrm{O}\left({n}^{2}\right)$ 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:
 > $\mathrm{CodeTools}:-\mathrm{Usage}\left(\mathrm{MapleLists}\left(20000\right)\right)$
 memory used=1.49GiB, alloc change=24.48MiB, cpu time=7.84s, real time=5.11s, gc time=6.27s
 ${20000}$ (20)
 > $\mathrm{CodeTools}:-\mathrm{Usage}\left(\mathrm{DEQueues}\left(20000\right)\right)$
 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.