<h4>4.2 <span class="Heading">Deques implemented using plain lists</span></h4>
<p><strong class="pkg">datastructures</strong> implements deques using a circular buffer stored in a <strong class="pkg">GAP</strong> a plain list, wrapped in a positional object (<a href="/home/runner/gap/doc/ref/chap79.html#X834893D07FAA6FD2"><span class="RefLink">Reference: Positional Objects</span></a>).</p>
<p>The five positions in such a deque <code class="code">Q</code> have the following purpose</p>
<ul>
<li><p><code class="code">Q![1]</code> - head, the index in <code class="code">Q![5]</code> of the first element in the deque</p>
</li>
<li><p><code class="code">Q![2]</code> - tail, the index in <code class="code">Q![5]</code> of the last element in the deque</p>
</li>
<li><p><code class="code">Q![3]</code> - capacity, the allocated capacity in the deque</p>
</li>
<li><p><code class="code">Q![4]</code> - factor by which storage is increased if capacity is exceeded</p>
</li>
<li><p><code class="code">Q![5]</code> - GAP plain list with storage for capacity many entries</p>
</li>
</ul>
<p>Global constants <code class="keyw">QHEAD</code>, <code class="keyw">QTAIL</code>, <code class="keyw">QCAPACITY</code>, <code class="keyw">QFACTOR</code>, and <code class="keyw">QDATA</code> are bound to reflect the above.</p>
<p>When a push fills the deque, its capacity is resized by a factor of <code class="keyw">QFACTOR</code> using PlistDequeExpand. A new empty plist is allocated and all current entries of the deque are copied into the new plist with the head entry at index 1.</p>
<p>The deque is empty if and only if head = tail and the entry that head and tail point to in the storage list is unbound.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ PlistDeque</code>( [<var class="Arg">capacity</var>[, <var class="Arg">factor</var>]] )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: a deque</p>
<p>Constructor for plist based deques. The optional argument <var class="Arg">capacity</var> must be a positive integer and is the capacity of the created deque, and the optional argument <var class="Arg">factor</var> must be a rational number greater than one which is the factor by which the storage of the deque is increased if it runs out of capacity when an object is put on the queue.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ PlistDequePushFront</code>( <var class="Arg">deque</var>, <var class="Arg">object</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Push <var class="Arg">object</var> to the front of <var class="Arg">deque</var>.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ PlistDequePushBack</code>( <var class="Arg">deque</var>, <var class="Arg">object</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Push <var class="Arg">object</var> to the back of <var class="Arg">deque</var>.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ PlistDequePopFront</code>( <var class="Arg">deque</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: object or fail</p>
<p>Pop object from the front of <var class="Arg">deque</var> and return it. If <var class="Arg">deque</var> is empty, returns <code class="keyw">fail</code>.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ PlistDequePopBack</code>( <var class="Arg">deque</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: object or fail</p>
<p>Pop object from the back of <var class="Arg">deque</var> and return it. If <var class="Arg">deque</var> is empty, returns <code class="keyw">fail</code>.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ PlistDequePeekFront</code>( <var class="Arg">deque</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: object or fail</p>
<p>Returns the object at the front <var class="Arg">deque</var> without removing it. If <var class="Arg">deque</var> is empty, returns <code class="keyw">fail</code>.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ PlistDequePeekBack</code>( <var class="Arg">deque</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: object or fail</p>
<p>Returns the object at the back <var class="Arg">deque</var> without removing it. If <var class="Arg">deque</var> is empty, returns <code class="keyw">fail</code>.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ PlistDequeExpand</code>( <var class="Arg">deque</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Helper function to expand the capacity of <var class="Arg">deque</var> by the configured factor.</p>
<p><em>Queues</em> are linear data structure that allow adding elements at the end of the queue, and removing elements from the front. A <em>deque</em> is a <em>double-ended queue</em>; a linear data structure that allows access to objects at both ends.</p>
<p>The API that objects that lie in <code class="func">IsQueue</code> (<a href="chap4.html#X82229C878341CDDC"><span class="RefLink">4.1-1</span></a>) and <code class="func">IsDeque</code> (<a href="chap4.html#X7CD371EE7EB88DA8"><span class="RefLink">4.1-2</span></a>) must implement the API set out below.</p>
Die Informationen auf dieser Webseite wurden
nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit,
noch Qualität der bereit gestellten Informationen zugesichert.
Bemerkung:
Die farbliche Syntaxdarstellung ist noch experimentell.
