1 Imperative Queues
(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?
This takes constant time, independent of the number of elements in q.
procedure
(enqueue-front! q v) → void?
q : queue? v : any/c
This takes constant time, independent of the number of elements in q.
procedure
q : non-empty-queue?
This takes constant time, independent of the number of elements in q.
(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)
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.
(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 q) → (listof any/c)
q : queue?
This takes time proportional to the number of elements in q.
(define q (make-queue)) > (enqueue! q 8) > (enqueue! q 9) > (enqueue! q 0) > (queue->list q) '(8 9 0)
procedure
q : queue?
This takes constant time, independent of the number of elements in q.
(define q (make-queue)) > (queue-length q) 0
> (enqueue! q 5) > (enqueue! q 12) > (queue-length q) 2
> (dequeue! q) 5
> (queue-length q) 1
procedure
(queue-empty? q) → boolean?
q : queue?
This takes constant time, independent of the number of elements in q.
(define q (make-queue)) > (queue-empty? q) #t
> (enqueue! q 1) > (queue-empty? q) #f
> (dequeue! q) 1
> (queue-empty? q) #t
This takes constant time, independent of the size of the argument v.
> (queue? (make-queue)) #t
> (queue? 'not-a-queue) #f
procedure
(non-empty-queue? v) → boolean?
v : any/c
This takes constant time, independent of the size of the argument v.
> (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
value
value