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:
arc> (let q (queue) (enq 'a q) (enq 'b q) q) ((a b) (b) 2)
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
qlist operation should be used to access the contents of the queue.
arc> (do (= q (queue)) (enq 1 q) (enq 2 q)) (1 2) arc> (apply + q) Error: "+: expects type
as 1st argument, given: (1 2); other arguments were: (2) 2" arc> (apply + (qlist q)) 3
Creates a queue.
>(queue) (nil nil 0)
>(type (queue)) cons
enq obj q
Adds obj to the end of queue q. Returns the queue as a list. The operation is wrapped in
>(let q (queue) (enq 'a q) (enq '(1 2) q)) (a (1 2))
enq-limit obj q [limit]
Adds obj to the queue q. If the new length would exceed the limit, the first element is dequeued. The new contents of the queue is returned as a list. Note that the length of the queue will either grow by one or remain constant; the queue will not be shortened to the limit. The operation is wrapped in
>(let q (queue) (enq-limit 'a q 2) (enq-limit 'b q 2) (enq-limit 'c q 2)) (b c)
Removes the first element from the queue q and returns the removed element. The operation is wrapped in
>(let q (queue) (enq 'a q) (enq 4 q) (deq q)) a
Returns the length of queue q.
>(let q (queue) (enq 'a q) (enq 4 q) (deq q) (qlen q)) 1
Returns the contents of queue q as a list.
>(let q (queue) (enq 'a q) (enq '(1 2) q) (qlist q)) (a (1 2))
Copyright 2008 Ken Shirriff.