11.22 util.queue - Queue

Module: util.queue

Provides a queue (FIFO). This implementation is tuned for speed than safety; a queue is simply a pair that keeps head and tail of the queue, and minimal check is done in most of the operations.

SLIB (See section 11.15 slib - SLIB interface) provides the queue library that is safer. This API is upper compatible to the SLIB's. The idea is that this queue is used inside other procedure or structure that you know you don't need the strict checks. Use either one depending on your requirement.

Function: make-queue

Creates and returns an empty queue.

Function: queue? obj

Returns #t if obj is a queue. This operation checks obj is really in a shape of the queue.

Function: queue-empty? queue

Returns #t if obj is an empty queue.

Function: queue-length queue

Returns the number of the items in the queue.

Function: enqueue! queue obj &optional more-objs ...

Add obj to the end of queue. You may give more than one object, and each of them are enqueued in order. (Note: SLIB version doesn't take the optional arguments).

Function: queue-push! queue obj &optional more-objs ...

Add obj in front of queue. You may give more than one object, and each of them are pushed in order. (Note: SLIB version doesn't take the optional arguments).

Function: dequeue! queue

Function: queue-pop! queue

Take one object from the front of the queue queue and returns it. Both function works the same, but queue-pop! may be used to emphasize it works with queue-push!. An error is signalled if queue is empty.

Function: dequeue-all! queue

Returns the whole content of the queue by a list, with emptying queue. If queue is already empty, returns an empty list. See also queue->list below.

Function: queue-front queue

Function: queue-rear queue

Peek the head or the tail of the queue and returns the object, respectively. util.queue - Queue is not modified. An error is signalled if queue is empty.

Function: list->queue list

Returns a new queue whose content is the elements in list, in the given order.

Function: queue->list queue

Returns a list whose content is the items in the queue in order. Unlike dequeue-all!, the content of queue remains intact.

In Gauche, queue->list copies the content of the queue to a freshly allocated list, while dequeue-all! doesn't copy but directly returns the queue's internal list. There are some Scheme systems that has queue->list but doesn't guarantee the content is copied, so if you're planning to share the code among these implementations, it's better not to rely on the fact that queue->list copies the content.

Function: find-in-queue pred queue

Returns the first item in queue that satisfies a predicate pred. The order of arguments follows find in SRFI-1 (See section 10.2.7 List searching).

Function: remove-from-queue! pred queue

Removes all items in the queue that satisfies pred. Returns #t if any item is removed. Otherwise returns #f. The order of arguments follows remove in SRFI-1 (See section 10.2.6 List filtering & partitioning).

Note on portability: Scheme48 has delete-from-queue!, which takes object to remove rather than predicate, and also takes arguments in reversed order (i.e. queue comes first). Avoid conflicting with that I intentionally left out delete-from-queue!; it's easy to write one in either Scheme48 compatible way or consistent to SRFI-1 argument order.