▼Data:   Data Structures
On this page:
make-queue
enqueue!
enqueue-front!
dequeue!
queue-filter!
queue->list
queue-length
queue-empty?
queue?
non-empty-queue?
in-queue
queue/  c
nonempty-queue/  c
6.3
  top  ← prev  up  next → 

1 Imperative Queues

Carl Eastlund <cce@racket-lang.org>

 (require data/queue) package: base

This module provides a simple mutable queue representation, providing first-in/first-out semantics.

Operations on queues mutate it in a thread-unsafe way.

procedure

(make-queue) → queue?

Produces an empty queue.

procedure

(enqueue! q v) → void?

  q : queue?
  v : any/c
Adds an element to the back of a queue.

This takes constant time, independent of the number of elements in q.

procedure

(enqueue-front! q v) → void?

  q : queue?
  v : any/c
Adds an element to the front of a queue.

This takes constant time, independent of the number of elements in q.

procedure

(dequeue! q) → any/c

  q : non-empty-queue?
Removes an element from the front of a non-empty queue, and returns that element.

This takes constant time, independent of the number of elements in q.

Examples:

(define q (make-queue))
> (enqueue! q 1)
> (dequeue! q)

1

> (enqueue! q 2)
> (enqueue! q 3)
> (dequeue! q)

2

> (dequeue! q)

3

> (enqueue! q 2)
> (enqueue! q 1)
> (enqueue-front! q 3)
> (enqueue-front! q 4)
> (queue->list q)

'(4 3 2 1)

procedure

(queue-filter! q pred?) → void?

  q : queue?
  pred? : (-> any/c any/c)
Applies pred? to each element of the queue, removing any where pred? returns #f.

This takes time proportional to the number of elements in q (assuming that pred? takes constant time, independent of the number of elements in q). It does not allocate and it calls pred? exactly once for each element of q.

Examples:

(define q (make-queue))
> (enqueue! q 1)
> (enqueue! q 2)
> (enqueue! q 3)
> (enqueue! q 4)
> (queue-filter! q even?)
> (queue->list q)

'(2 4)

procedure

(queue->list queue) → (listof any/c)

  queue : queue?
Returns an immutable list containing the elements of the queue in the order the elements were added.

This takes time proportional to the number of elements in q.

Examples:

(define q (make-queue))
> (enqueue! q 8)
> (enqueue! q 9)
> (enqueue! q 0)
> (queue->list q)

'(8 9 0)

procedure

(queue-length queue) → exact-nonnegative-integer?

  queue : queue?
Returns the number of elements in the queue.

This takes constant time, independent of the number of elements in q.

Examples:

(define queue (make-queue))
> (queue-length q)

3

> (enqueue! q 5)
> (enqueue! q 12)
> (queue-length q)

5

> (dequeue! q)

8

> (queue-length q)

4

procedure

(queue-empty? q) → boolean?

  q : queue?
Recognizes whether a queue is empty or not.

This takes constant time, independent of the number of elements in q.

Examples:

(define q (make-queue))
> (queue-empty? q)

#t

> (enqueue! q 1)
> (queue-empty? q)

#f

> (dequeue! q)

1

> (queue-empty? q)

#t

procedure

(queue? v) → boolean?

  v : any/c
This predicate recognizes queues.

This takes constant time, independent of the size of the argument v.

Examples:

> (queue? (make-queue))

#t

> (queue? 'not-a-queue)

#f

procedure

(non-empty-queue? v) → boolean?

  v : any/c
This predicate recognizes non-empty queues.

This takes constant time, independent of the size of the argument v.

Examples:

> (non-empty-queue? (let ([q (make-queue)])
                      (enqueue! q 1)
                      q))

#t

> (non-empty-queue? (make-queue))

#f

> (non-empty-queue? 'not-a-queue)

#f

procedure

(in-queue queue) → sequence?

  queue : queue?
Returns a sequence whose elements are the elements of queue.

value

queue/c : flat-contract?

value

nonempty-queue/c : flat-contract?

These are provided for backwards compatibility. They are identical to queue? and non-empty-queue?, respectively.

  top  ← prev  up  next →