queue0.html

Arc implements a queue datatype, which is useful to add and remove elements in a first-in-first-out order.  The queue datatype provides two advantages over using a plain list.  The queue provides constant-time operations to add and remove elements and to determine the queue length.  The queue also provides atomic access to its contents.
<p>Internally the queue is implemented by a three-element list.  The first element is the queue's contents as a list.  The second element is a reference to the last element in the list.  The third element is the length of the queue.  By maintaining a reference to the end of the queue, an element can be added to the end of the queue in constant time, without traversing the whole list.  By storing the length explicitly, the length can also be returned in constant time.  For example, the following shows a queue with two elements:
<pre class="repl">
arc> (let q (queue) (enq 'a q) (enq 'b q) q)
((a b) (b) 2)
</pre>
<p>
Most Arc operations do not have any "knowledge" of a queue, and if applied to a queue will act on the list implementing the queue; the results are likely to be undesired.  The <code>qlist</code> operation should be used to access the contents of the queue.
<pre class="repl">
arc> (do (= q (queue)) (enq 1 q) (enq 2 q))
(1 2)
arc> (apply + q)
Error: "+: expects type <number> as 1st argument, given: (1 2); other arguments were: (2) 2"
arc> (apply + (qlist q))
3
</pre>