Next: , Previous: Cells, Up: System features


4.1.8 Queues

The queues structure exports names for procedures that operate on simple first-in, first-out queues.

— procedure: make-queue –> queue
— procedure: queue? object –> boolean

Make-queue constructs an empty queue. Queue? is the disjoint type predicate for queues.

— procedure: queue-empty? queue –> boolean
— procedure: empty-queue! queue –> unspecified

Queue-empty? returns #t if queue contains zero elements or #f if it contains some. Empty-queue! removes all elements from queue.

— procedure: enqueue! queue object –> unspecified
— procedure: dequeue! queue –> value
— procedure: maybe-dequeue! queue –> value or #f
— procedure: queue-head queue –> value

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 like dequeue!, 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.

— procedure: queue-length queue –> integer

Returns the number of objects in queue.

— procedure: on-queue? queue object –> boolean
— procedure: delete-from-queue! queue object –> unspecified

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.

— procedure: queue->list queue –> list
— procedure: list->queue list –> queue

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.