Next: Hash tables, Previous: Cells, Up: System features
The queues
structure exports names for procedures that operate
on simple first-in, first-out queues.
Make-queue
constructs an empty queue.Queue?
is the disjoint type predicate for queues.
Queue-empty?
returns#t
if queue contains zero elements or#f
if it contains some.Empty-queue!
removes all elements from queue.
#f
Enqueue!
adds object to queue.Dequeue!
removes & returns the next object available from queue; if queue is empty,dequeue!
signals an error.Maybe-dequeue!
is likedequeue!
, but it returns#f
in the case of an absence of any element, rather than signalling an error.Queue-head
returns the next element available from queue without removing it, or it signals an error if queue is empty.
On-queue?
returns true if queue contains object or#f
if not.Delete-from-queue!
removes the first occurrence of object from queue that would be dequeued.
These convert queues to and from lists of their elements.
Queue->list
returns a list in the order in which its elements were added to the queue.List->queue
returns a queue that will produce elements starting at the head of the list.
Examples:
(define q (make-queue)) (enqueue! q 'foo) (enqueue! q 'bar) (queue->list q) => (foo bar) (on-queue? q 'bar) => #t (dequeue! q) => 'foo (queue-empty? q) => #f (delete-from-queue! queue 'bar) (queue-empty? q) => #t (enqueue! q 'frobozz) (empty-queue! q) (queue-empty? q) => #t (dequeue! q) error--> empty queue
Queues are integrated with Scheme48's optimistic concurrency facilities, in that every procedure exported
except for queue->list
ensures fusible atomicity in operation
— that is, every operation except for queue->list
ensures that
the transaction it performs is atomic, and that it may be fused within
larger atomic transactions, as transactions wrapped within
call-ensuring-atomicity
&c. may be.