1 Queues

8.16.0.1

1 Queues🔗ℹ

Following queue structures implement and provide the functions empty?, enqueue, head, tail, queue and queue->list. All the queue structures are polymorphic.

1.1 Banker’s Queue

1.2 Physicist’s Queue

1.3 Implicit Queue

1.4 Bootstraped Queue

1.5 Real-Time Queue

1.6 Hood-Melville Queue

1.1 Banker’s Queue🔗ℹ

(require pfds/queue/bankers)

package: pfds

A Queue is nothing but a FIFO data structure. A Banker’s Queue is a amortized queue obtained using Bankers method. It provides a amortized running time of O(1) for head, tail and enqueue operations. To obtain this amortized running time, the data structure uses the techniques, lazy evaluation and memoization. Banker’s Queue internally uses Streams for lazy evaluation. For Streams, see Streams

syntax
(Queue A)

A banker’s queue of type A.

procedure
(queue a ...) → (Queue A)
a : A

Function queue creates a Banker’s Queue with the given inputs.

Example:

> (queue 1 2 3 4 5 6)
- : #(struct:Queue
      ((Rec
        g285461
        (U (Pairof Positive-Byte g285461) (Promiseof g285461) Null))
       Integer
       (Listof Positive-Byte)
       Integer))
#<Queue>

In the above example, the queue obtained will have 1 as its head element.

procedure
(empty t) → (Queue Nothing)
t : A

An empty queue instantiated to type t.

Examples:

> (empty Nothing)
- : (Queue Nothing)
#<Queue>
> (empty Integer)
- : (Queue Integer)
#<Queue>

procedure
(empty? que) → Boolean
que : (Queue A)

Function empty? checks if the given queue is empty or not.

Examples:

> (empty? (queue 1 2 3 4 5 6))
- : Boolean
#f
> (empty? (empty Integer))
- : Boolean
#t

procedure
(enqueue a que) → (Queue A)
a : A
que : (Queue A)

Function enqueue takes an element and a queue and adds the given element into the queue.

Example:

> (enqueue 10 (queue 4 5 6))
- : #(struct:Queue
      ((Rec
        g285539
        (U (Pairof Positive-Byte g285539) (Promiseof g285539) Null))
       Integer
       (Listof Positive-Byte)
       Integer))
#<Queue>

In the above example, (enqueue 10 (queue 4 5 6)) enqueues 10 to the end of the queue and returns (queue 4 5 6 10).

procedure
(head que) → A
que : (Queue A)

Function head takes a queue and returns the first element in the queue if its a non empty queue else throws an error.

Examples:

> (head (queue 10 4 3 12))
- : Integer [more precisely: Positive-Byte]
10
> (head (empty Integer))
head: given queue is empty

procedure
(tail que) → (Queue A)
que : (Queue A)

Function tail takes a queue and returns the same queue without the first element. If the queue is empty it throws an error.

Examples:

> (tail (queue 4 5 6))
- : #(struct:Queue
      ((Rec
        g285599
        (U (Pairof Positive-Byte g285599) (Promiseof g285599) Null))
       Integer
       (Listof Positive-Byte)
       Integer))
#<Queue>
> (tail (empty Integer))
tail: given queue is empty

In the above example, (tail (queue 4 5 6)), returns (queue 5 6).

procedure
(queue->list que) → (Queue A)
que : (Queue A)

Function queue->list takes a queue and returns a list of elements. The list will have head of the given queue as its first element.

Examples:

> (queue->list (queue 10 2 34 4 15 6))
- : (Listof Positive-Byte)
'(10 2 34 4 15 6)
> (queue->list (empty Integer))
- : (Listof Integer)
'()

procedure
(map func que1 que2 ...) → (Queue A)
  func : (A B ... B -> C)
  que1 : (Queue A)
  que2 : (Queue B)

Function map is similar to map for lists.

Examples:

> (queue->list (map add1 (queue 1 2 3 4 5 6)))
- : (Listof Positive-Index)
'(2 3 4 5 6 7)
> (queue->list (map * (queue 1 2 3 4 5 6) (queue 1 2 3 4 5 6)))
- : (Listof Positive-Index)
'(1 4 9 16 25 36)

procedure
(fold func init que1 que2 ...) → C
  func : (C A B ... B -> C)
  init : C
  que1 : (Queue A)
  que2 : (Queue B)

Function fold is similar to foldl or foldr

fold currently does not produce correct results when the given function is non-commutative.

Examples:

> (fold + 0 (queue 1 2 3 4 5 6))
- : Integer [more precisely: Nonnegative-Integer]
21
> (fold * 1 (queue 1 2 3 4 5 6) (queue 1 2 3 4 5 6))
- : Integer [more precisely: Positive-Integer]
518400

procedure
(filter func que) → (Queue A)
func : (A -> Boolean)
que : (Queue A)

Function filter is similar to filter.

Examples:

> (define que (queue 1 2 3 4 5 6))
> (queue->list (filter (λ: ([x : Integer]) (> x 5)) que))
- : (Listof Positive-Byte)
'(6)
> (queue->list (filter (λ: ([x : Integer]) (< x 5)) que))
- : (Listof Positive-Byte)
'(1 2 3 4)
> (queue->list (filter (λ: ([x : Integer]) (<= x 5)) que))
- : (Listof Positive-Byte)
'(1 2 3 4 5)

procedure
(remove func que) → (Queue A)
func : (A -> Boolean)
que : (Queue A)

Function remove is similar to filter but remove removes the elements which match the predicate.

Examples:

> (queue->list (remove (λ: ([x : Integer]) (> x 5))
                       (queue 1 2 3 4 5 6)))
- : (Listof Positive-Byte)
'(1 2 3 4 5)
> (queue->list (remove (λ: ([x : Integer]) (< x 5))
                       (queue 1 2 3 4 5 6)))
- : (Listof Positive-Byte)
'(5 6)
> (queue->list (remove (λ: ([x : Integer]) (<= x 5))
                       (queue 1 2 3 4 5 6)))
- : (Listof Positive-Byte)
'(6)

procedure
(andmap func que1 que2 ...) → Boolean
  func : (A B ... B -> Boolean)
  que1 : (Queue A)
  que2 : (Queue B)

Function andmap is similar to andmap.

Examples:

> (andmap even? (queue 1 2 3 4 5 6))
- : Boolean
#f
> (andmap odd? (queue 1 2 3 4 5 6))
- : Boolean
#f
> (andmap positive? (queue 1 2 3 4 5 6))
- : Boolean
#t
> (andmap negative? (queue -1 -2))
- : Boolean
#t

procedure
(ormap func que1 que2 ...) → Boolean
  func : (A B ... B -> Boolean)
  que1 : (Queue A)
  que2 : (Queue B)

Function ormap is similar to ormap.

Examples:

> (ormap even? (queue 1 2 3 4 5 6))
- : Boolean
#t
> (ormap odd? (queue 1 2 3 4 5 6))
- : Boolean
#t
> (ormap positive? (queue -1 -2 3 4 -5 6))
- : Boolean
#t
> (ormap negative? (queue 1 -2))
- : Boolean
#t

procedure
(build-queue size func) → (Queue A)
size : Natural
func : (Natural -> A)

Function build-queue is similar to build-list.

Examples:

> (queue->list (build-queue 5 (λ:([x : Integer]) (add1 x))))
- : (Listof Integer)
'(1 2 3 4 5)
> (queue->list (build-queue 5 (λ:([x : Integer]) (* x x))))
- : (Listof Integer)
'(0 1 4 9 16)

procedure
(head+tail que) → (Pair A (Queue A))
que : (Queue A)

Function head+tail returns a pair containing the head and the tail of the given queue.

Examples:

> (head+tail (queue 1 2 3 4 5))
- : (Pairof
     Positive-Byte
     #(struct:Queue
       ((Rec
         g286262
         (U (Pairof Positive-Byte g286262) (Promiseof g286262) Null))
        Integer
        (Listof Positive-Byte)
        Integer)))
'(1 . #<Queue>)
> (head+tail (build-queue 5 (λ:([x : Integer]) (* x x))))
- : (Pairof
     Integer
     #(struct:Queue
       ((Rec g286285 (U (Pairof Integer g286285) (Promiseof g286285) Null))
        Integer
        (Listof Integer)
        Integer)))
'(0 . #<Queue>)
> (head+tail (empty Integer))
head+tail: given queue is empty

1.2 Physicist’s Queue🔗ℹ

(require pfds/queue/physicists)

package: pfds

A Queue is nothing but a FIFO data structure. A Physicist’s queue ia a Amortized queues obtained by Physicist’s method. Provides a amortized running time of O(1) for head, tail and enqueue operations. Physicists’s Queue uses lazy evaluation and memoization to get this amortized running time.

syntax
(Queue A)

A physicist’s queue of type A.

procedure
(queue a ...) → (Queue A)
a : A

Function queue creates a Physicist’s Queue with the given inputs.

Example:

> (queue 1 2 3 4 5 6)
- : #(struct:Queue
      ((Listof Integer)
       (Boxof (U (-> (Listof Integer)) (Listof Integer)))
       Integer
       (Listof Integer)
       Integer))
#<Queue>

In the above example, the queue obtained will have 1 as its head element

procedure
(empty t) → (Queue A)
t : A

An empty queue.

procedure
(empty? que) → Boolean
que : (Queue A)

Function empty? checks if the given queue is empty or not.

Examples:

> (empty? (queue 1 2 3 4 5 6))
- : Boolean
#f
> (empty? (empty Integer))
- : Boolean
#t

procedure
(enqueue a que) → (Queue A)
a : A
que : (Queue A)

Function enqueue takes an element and a queue and enqueues the given element into the queue.

Example:

> (enqueue 10 (queue 1 2 3 4 5 6))
- : #(struct:Queue
      ((Listof Integer)
       (Boxof (U (-> (Listof Integer)) (Listof Integer)))
       Integer
       (Listof Integer)
       Integer))
#<Queue>

In the above example, enqueue adds the element 10 to (queue 1 2 3 4 5 6) and returns (queue 1 2 3 4 5 6 10).

procedure
(head que) → A
que : (Queue A)

Function head takes a queue and gives the first element in the queue if its a non empty queue else throws an error.

Examples:

> (head (queue 1 2 3 4 5 6))
- : Integer
1
> (head (empty Integer))
head: given queue is empty

procedure
(tail que) → (Queue A)
que : (Queue A)

Function tail takes a queue and returns a queue with rest elements if its a non empty queue else throws an error.

Examples:

> (tail (queue 1 2 3 4 5 6))
- : #(struct:Queue
      ((Listof Integer)
       (Boxof (U (-> (Listof Integer)) (Listof Integer)))
       Integer
       (Listof Integer)
       Integer))
#<Queue>
> (tail (empty Integer))
tail: given queue is empty

In the above example, (tail (queue 1 2 3 4 5 6)), returns (queue 2 3 4 5 6).

procedure
(queue->list que) → (Queue A)
que : (Queue A)

Function queue->list takes a queue and returns a list of elements. The list will have head of the given queue as its first element. If the given queue is empty, then it returns an empty list.

Examples:

> (queue->list (queue 10 2 34 4 15 6))
- : (Listof Integer)
'(10 2 34 4 15 6)
> (queue->list (empty Integer))
- : (Listof Integer)
'()

procedure
(map func que1 que2 ...) → (Queue A)
  func : (A B ... B -> C)
  que1 : (Queue A)
  que2 : (Queue B)

Function map is similar to map for lists.

Examples:

> (queue->list (map add1 (queue 1 2 3 4 5 6)))
- : (Listof Integer)
'(2 3 4 5 6 7)
> (queue->list (map * (queue 1 2 3 4 5 6) (queue 1 2 3 4 5 6)))
- : (Listof Integer)
'(1 4 9 16 25 36)

procedure
(fold func init que1 que2 ...) → C
  func : (C A B ... B -> C)
  init : C
  que1 : (Queue A)
  que2 : (Queue B)

Function fold is similar to foldl or foldr

fold currently does not produce correct results when the given function is non-commutative.

Examples:

> (fold + 0 (queue 1 2 3 4 5 6))
- : Integer
21
> (fold * 1 (queue 1 2 3 4 5 6) (queue 1 2 3 4 5 6))
- : Integer
518400

procedure
(filter func que) → (Queue A)
func : (A -> Boolean)
que : (Queue A)

Function filter is similar to filter.

Examples:

> (define que (queue 1 2 3 4 5 6))
> (queue->list (filter (λ: ([x : Integer]) (> x 5)) que))
- : (Listof Integer)
'(6)
> (queue->list (filter (λ: ([x : Integer]) (< x 5)) que))
- : (Listof Integer)
'(1 2 3 4)
> (queue->list (filter (λ: ([x : Integer]) (<= x 5)) que))
- : (Listof Integer)
'(1 2 3 4 5)

procedure
(remove func que) → (Queue A)
func : (A -> Boolean)
que : (Queue A)

Function remove is similar to filter but remove removes the elements which match the predicate.

Examples:

> (queue->list (remove (λ: ([x : Integer]) (> x 5))
                       (queue 1 2 3 4 5 6)))
- : (Listof Integer)
'(1 2 3 4 5)
> (queue->list (remove (λ: ([x : Integer]) (< x 5))
                       (queue 1 2 3 4 5 6)))
- : (Listof Integer)
'(5 6)
> (queue->list (remove (λ: ([x : Integer]) (<= x 5))
                       (queue 1 2 3 4 5 6)))
- : (Listof Integer)
'(6)

procedure
(andmap func que1 que2 ...) → Boolean
  func : (A B ... B -> Boolean)
  que1 : (Queue A)
  que2 : (Queue B)

Function andmap is similar to andmap.

Examples:

> (andmap even? (queue 1 2 3 4 5 6))
- : Boolean
#f
> (andmap odd? (queue 1 2 3 4 5 6))
- : Boolean
#f
> (andmap positive? (queue 1 2 3 4 5 6))
- : Boolean
#t
> (andmap negative? (queue -1 -2))
- : Boolean
#t

procedure
(ormap func que1 que2 ...) → Boolean
  func : (A B ... B -> Boolean)
  que1 : (Queue A)
  que2 : (Queue B)

Function ormap is similar to ormap.

Examples:

> (ormap even? (queue 1 2 3 4 5 6))
- : Boolean
#t
> (ormap odd? (queue 1 2 3 4 5 6))
- : Boolean
#t
> (ormap positive? (queue -1 -2 3 4 -5 6))
- : Boolean
#t
> (ormap negative? (queue 1 -2))
- : Boolean
#t

procedure
(build-queue size func) → (Queue A)
size : Natural
func : (Natural -> A)

Function build-queue is similar to build-list.

Examples:

> (queue->list (build-queue 5 (λ:([x : Integer]) (add1 x))))
- : (Listof Integer)
'(1 2 3 4 5)
> (queue->list (build-queue 5 (λ:([x : Integer]) (* x x))))
- : (Listof Integer)
'(0 1 4 9 16)

procedure
(head+tail que) → (Pair A (Queue A))
que : (Queue A)

Function head+tail returns a pair containing the head and the tail of the given queue.

Examples:

> (head+tail (queue 1 2 3 4 5))
- : (Pairof
     Integer
     #(struct:Queue
       ((Listof Integer)
        (Boxof (U (-> (Listof Integer)) (Listof Integer)))
        Integer
        (Listof Integer)
        Integer)))
'(1 . #<Queue>)
> (head+tail (build-queue 5 (λ:([x : Integer]) (* x x))))
- : (Pairof
     Integer
     #(struct:Queue
       ((Listof Integer)
        (Boxof (U (-> (Listof Integer)) (Listof Integer)))
        Integer
        (Listof Integer)
        Integer)))
'(0 . #<Queue>)
> (head+tail (empty Integer))
head+tail: given queue is empty

1.3 Implicit Queue🔗ℹ

(require pfds/queue/implicit)

package: pfds

Queues obtained by applying the technique called Implicit Recursive Slowdown. Provides a amortized running time of O(1) for the operations head, tail and enqueue. Implicit Recursive Slowdown combines laziness and technique called Recursive Slow-Down developed by Kaplan and Tarjan in their paper Persistant Lists with Catenation via Recursive Slow-Down.

syntax
(Queue A)

A implicit queue of type A.

procedure
(queue a ...) → (Queue A)
a : A

Function queue creates a Implicit Queue with the given inputs.

Example:

> (queue 1 2 3 4 5 6)
- : (U (Deep Positive-Byte) (Shallow Positive-Byte))
#<Deep>

In the above example, the queue obtained will have 1 as its head element.

value
empty : (Queue Nothing)

An empty queue.

procedure
(empty? que) → Boolean
que : (Queue A)

Function empty? checks if the given queue is empty or not.

Examples:

> (empty? (queue 1 2 3 4 5 6))
- : Boolean
#f
> (empty? empty)
- : Boolean
#t

procedure
(enqueue a que) → (Queue A)
a : A
que : (Queue A)

Functionenqueue takes an element and a queue and enqueues the given element into the queue.

Example:

> (enqueue 10 (queue 1 2 3 4 5 6))
- : (U (Deep Positive-Byte) (Shallow Positive-Byte))
#<Deep>

In the above example, enqueue adds the element 10 to of (queue 1 2 3 4 5 6) and returns (queue 1 2 3 4 5 6 10).

procedure
(head que) → A
que : (Queue A)

Function head takes a queue and gives the first element in the queue if queue is not empty else throws an error.

Examples:

> (head (queue 1 2 3 4 5 6))
- : Integer [more precisely: Positive-Byte]
1
> (head empty)
head: given queue is empty

procedure
(tail que) → (Queue A)
que : (Queue A)

Function tail takes a queue and returns a queue with rest elements if its a non empty queue else throws an error.

Examples:

> (tail (queue 1 2 3 4 5 6))
- : (U (Deep Positive-Byte) (Shallow Positive-Byte))
#<Deep>
> (tail empty)
tail: given queue is empty

In the above example, (tail (queue 1 2 3 4 5 6)), removes the head of the given queue returns (queue 2 3 4 5 6).

procedure
(queue->list que) → (Queue A)
que : (Queue A)

Function queue->list takes a queue and returns a list of elements. The list will have head of the given queue as its first element. If the given queue is empty, then it returns an empty list.

Examples:

> (queue->list (queue 10 2 34 4 15 6))
- : (Listof Positive-Byte)
'(10 2 34 4 15 6)
> (queue->list empty)
- : (Listof Nothing)
'()

procedure
(map func que1 que2 ...) → (Queue A)
  func : (A B ... B -> C)
  que1 : (Queue A)
  que2 : (Queue B)

Function map is similar to map for lists.

Examples:

> (queue->list (map add1 (queue 1 2 3 4 5 6)))
- : (Listof Positive-Index)
'(2 3 4 5 6 7)
> (queue->list (map * (queue 1 2 3 4 5 6) (queue 1 2 3 4 5 6)))
- : (Listof Positive-Index)
'(1 4 9 16 25 36)

procedure
(fold func init que1 que2 ...) → C
  func : (C A B ... B -> C)
  init : C
  que1 : (Queue A)
  que2 : (Queue B)

Function fold is similar to foldl or foldr

fold currently does not produce correct results when the given function is non-commutative.

Examples:

> (fold + 0 (queue 1 2 3 4 5 6))
- : Integer [more precisely: Nonnegative-Integer]
21
> (fold * 1 (queue 1 2 3 4 5 6) (queue 1 2 3 4 5 6))
- : Integer [more precisely: Positive-Integer]
518400

procedure
(filter func que) → (Queue A)
func : (A -> Boolean)
que : (Queue A)

Function filter is similar to filter.

Examples:

> (define que (queue 1 2 3 4 5 6))
> (queue->list (filter (λ: ([x : Integer]) (> x 5)) que))
- : (Listof Positive-Byte)
'(6)
> (queue->list (filter (λ: ([x : Integer]) (< x 5)) que))
- : (Listof Positive-Byte)
'(1 2 3 4)
> (queue->list (filter (λ: ([x : Integer]) (<= x 5)) que))
- : (Listof Positive-Byte)
'(1 2 3 4 5)

procedure
(remove func que) → (Queue A)
func : (A -> Boolean)
que : (Queue A)

Function remove is similar to filter but remove removes the elements which match the predicate.

Examples:

> (queue->list (remove (λ: ([x : Integer]) (> x 5))
                       (queue 1 2 3 4 5 6)))
- : (Listof Positive-Byte)
'(1 2 3 4 5)
> (queue->list (remove (λ: ([x : Integer]) (< x 5))
                       (queue 1 2 3 4 5 6)))
- : (Listof Positive-Byte)
'(5 6)
> (queue->list (remove (λ: ([x : Integer]) (<= x 5))
                       (queue 1 2 3 4 5 6)))
- : (Listof Positive-Byte)
'(6)

procedure
(andmap func que1 que2 ...) → Boolean
  func : (A B ... B -> Boolean)
  que1 : (Queue A)
  que2 : (Queue B)

Function andmap is similar to andmap.

Examples:

> (andmap even? (queue 1 2 3 4 5 6))
- : Boolean
#f
> (andmap odd? (queue 1 2 3 4 5 6))
- : Boolean
#f
> (andmap positive? (queue 1 2 3 4 5 6))
- : Boolean
#t
> (andmap negative? (queue -1 -2))
- : Boolean
#t

procedure
(ormap func que1 que2 ...) → Boolean
  func : (A B ... B -> Boolean)
  que1 : (Queue A)
  que2 : (Queue B)

Function ormap is similar to ormap.

Examples:

> (ormap even? (queue 1 2 3 4 5 6))
- : Boolean
#t
> (ormap odd? (queue 1 2 3 4 5 6))
- : Boolean
#t
> (ormap positive? (queue -1 -2 3 4 -5 6))
- : Boolean
#t
> (ormap negative? (queue 1 -2))
- : Boolean
#t

procedure
(build-queue size func) → (Queue A)
size : Natural
func : (Natural -> A)

Function build-queue is similar to build-list.

Examples:

> (queue->list (build-queue 5 (λ:([x : Integer]) (add1 x))))
- : (Listof Integer)
'(1 2 3 4 5)
> (queue->list (build-queue 5 (λ:([x : Integer]) (* x x))))
- : (Listof Integer)
'(0 1 4 9 16)

procedure
(head+tail que) → (Pair A (Queue A))
que : (Queue A)

Function head+tail returns a pair containing the head and the tail of the given queue.

Examples:

> (head+tail (queue 1 2 3 4 5))
- : (Pairof Positive-Byte (U (Deep Positive-Byte) (Shallow Positive-Byte)))
'(1 . #<Deep>)
> (head+tail (build-queue 5 (λ:([x : Integer]) (* x x))))
- : (Pairof Integer (U (Deep Integer) (Shallow Integer)))
'(0 . #<Deep>)
> (head+tail empty)
head: given queue is empty

1.4 Bootstraped Queue🔗ℹ

(require pfds/queue/bootstrapped)

package: pfds

Bootstrapped Queue use a structural bootstrapping technique called Structural Decomposition. The data structure gives a worst case running time of O(1) for the operation head and O(log*(n)) for tail and enqueue. Internally uses Physicist’s Queue.

syntax
(Queue A)

A bootstrapped queue of type A.

procedure
(queue a ...) → (Queue A)
a : A

Function queue creates a Bootstraped Queue with the given inputs.

Example:

> (queue 1 2 3 4 5 6)
- : (U (IntQue Integer) Null)
#<IntQue>

In the above example, the queue obtained will have 1 as its first element.

value
empty : (Queue Nothing)

An empty queue.

procedure
(empty? que) → Boolean
que : (Queue A)

Function empty? checks if the given queue is empty or not.

Examples:

> (empty? (queue 1 2 3 4 5 6))
- : Boolean
#f
> (empty? empty)
- : Boolean
#t

procedure
(enqueue a que) → (Queue A)
a : A
que : (Queue A)

Function enqueue takes an element and a queue and enqueues the given element into the queue.

Example:

> (enqueue 10 (queue 1 2 3 4 5 6))
- : (U (IntQue Integer) Null)
#<IntQue>

In the above example, (enqueue 10 (queue 1 2 3 4 5 6)) adds the 10 to the queue (queue 1 2 3 4 5 6). 10 as its last element.

procedure
(head que) → A
que : (Queue A)

Function head takes a queue and gives the first element in the queue if queue is not empty else throws an error.

Examples:

> (head (queue 1 2 3 4 5 6))
- : Integer
1
> (head empty)
head: given queue is empty

procedure
(tail que) → (Queue A)
que : (Queue A)

Function tail takes a queue and returns the same queue without the first element of the given queue if its a non empty queue else throws an error.

Examples:

> (tail (queue 1 2 3 4 5 6))
- : (U (IntQue Integer) Null)
#<IntQue>
> (tail empty)
tail: given queue is empty

In the above example, (tail (queue 1 2 3 4 5 6)), removes the head of the given queue returns (queue 2 3 4 5 6).

procedure
(queue->list que) → (Queue A)
que : (Queue A)

Function queue->list takes a queue and returns a list of elements. The list will have head of the given queue as its first element. If the given queue is empty, then it returns an empty list.

Examples:

> (queue->list (queue 10 2 34 4 15 6))
- : (Listof Integer)
'(10 2 34 4 15 6)
> (queue->list empty)
- : (Listof Nothing)
'()

procedure
(map func que1 que2 ...) → (Queue A)
  func : (A B ... B -> C)
  que1 : (Queue A)
  que2 : (Queue B)

Function map is similar to map for lists.

Examples:

> (queue->list (map add1 (queue 1 2 3 4 5 6)))
- : (Listof Integer)
'(2 3 4 5 6 7)
> (queue->list (map * (queue 1 2 3 4 5 6) (queue 1 2 3 4 5 6)))
- : (Listof Integer)
'(1 4 9 16 25 36)

procedure
(fold func init que1 que2 ...) → C
  func : (C A B ... B -> C)
  init : C
  que1 : (Queue A)
  que2 : (Queue B)

Function fold is similar to foldl or foldr

fold currently does not produce correct results when the given function is non-commutative.

Examples:

> (fold + 0 (queue 1 2 3 4 5 6))
- : Integer
21
> (fold * 1 (queue 1 2 3 4 5 6) (queue 1 2 3 4 5 6))
- : Integer
518400

procedure
(filter func que) → (Queue A)
func : (A -> Boolean)
que : (Queue A)

Function filter is similar to filter.

Examples:

> (define que (queue 1 2 3 4 5 6))
> (queue->list (filter (λ: ([x : Integer]) (> x 5)) que))
- : (Listof Integer)
'(6)
> (queue->list (filter (λ: ([x : Integer]) (< x 5)) que))
- : (Listof Integer)
'(1 2 3 4)
> (queue->list (filter (λ: ([x : Integer]) (<= x 5)) que))
- : (Listof Integer)
'(1 2 3 4 5)

procedure
(remove func que) → (Queue A)
func : (A -> Boolean)
que : (Queue A)

Function remove is similar to filter but remove removes the elements which match the predicate.

Examples:

> (queue->list (remove (λ: ([x : Integer]) (> x 5))
                       (queue 1 2 3 4 5 6)))
- : (Listof Integer)
'(1 2 3 4 5)
> (queue->list (remove (λ: ([x : Integer]) (< x 5))
                       (queue 1 2 3 4 5 6)))
- : (Listof Integer)
'(5 6)
> (queue->list (remove (λ: ([x : Integer]) (<= x 5))
                       (queue 1 2 3 4 5 6)))
- : (Listof Integer)
'(6)

procedure
(andmap func que1 que2 ...) → Boolean
  func : (A B ... B -> Boolean)
  que1 : (Queue A)
  que2 : (Queue B)

Function andmap is similar to andmap.

Examples:

> (andmap even? (queue 1 2 3 4 5 6))
- : Boolean
#f
> (andmap odd? (queue 1 2 3 4 5 6))
- : Boolean
#f
> (andmap positive? (queue 1 2 3 4 5 6))
- : Boolean
#t
> (andmap negative? (queue -1 -2))
- : Boolean
#t

procedure
(ormap func que1 que2 ...) → Boolean
  func : (A B ... B -> Boolean)
  que1 : (Queue A)
  que2 : (Queue B)

Function ormap is similar to ormap.

Examples:

> (ormap even? (queue 1 2 3 4 5 6))
- : Boolean
#t
> (ormap odd? (queue 1 2 3 4 5 6))
- : Boolean
#t
> (ormap positive? (queue -1 -2 3 4 -5 6))
- : Boolean
#t
> (ormap negative? (queue 1 -2))
- : Boolean
#t

procedure
(build-queue size func) → (Queue A)
size : Natural
func : (Natural -> A)

Function build-queue is similar to build-list.

Examples:

> (queue->list (build-queue 5 (λ:([x : Integer]) (add1 x))))
- : (Listof Integer)
'(1 2 3 4 5)
> (queue->list (build-queue 5 (λ:([x : Integer]) (* x x))))
- : (Listof Integer)
'(0 1 4 9 16)

procedure
(head+tail que) → (Pair A (Queue A))
que : (Queue A)

Function head+tail returns a pair containing the head and the tail of the given queue.

Examples:

> (head+tail (queue 1 2 3 4 5))
- : (Pairof Integer (U (IntQue Integer) Null))
'(1 . #<IntQue>)
> (head+tail (build-queue 5 (λ:([x : Integer]) (* x x))))
- : (Pairof Integer (U (IntQue Integer) Null))
'(0 . #<IntQue>)
> (head+tail empty)
head+tail: given queue is empty

1.5 Real-Time Queue🔗ℹ

(require pfds/queue/real-time)

package: pfds

Real-Time Queues eliminate the amortization by employing laziness and a technique called Scheduling. The data structure gives a worst case running time of O(1) for the operations head, tail and enqueue.

syntax
(Queue A)

A real-time queue of type A.

procedure
(queue a ...) → (Queue A)
a : A

Function queue creates a Real-Time Queue with the given inputs.

Example:

> (queue 1 2 3 4 5 6)
- : #(struct:Queue
      ((Rec
        g294125
        (U (Boxof (U (-> (Pairof Integer g294125)) (Pairof Integer g294125)))
           Null))
       (Listof Integer)
       (Rec
        g294128
        (U (Boxof (U (-> (Pairof Integer g294128)) (Pairof Integer g294128)))
           Null))))
#<Queue>

In the above example, the queue obtained will have 1 as its first element.

procedure
(empty t) → (Queue A)
t : A

An empty queue.

Examples:

> (empty Nothing)
- : (Queue Nothing)
#<Queue>
> (empty Integer)
- : (Queue Integer)
#<Queue>

procedure
(empty? que) → Boolean
que : (Queue A)

Function empty? checks if the given queue is empty or not.

Examples:

> (empty? (queue 1 2 3 4 5 6))
- : Boolean
#f
> (empty? (empty Integer))
- : Boolean
#t

procedure
(enqueue a que) → (Queue A)
a : A
que : (Queue A)

Functionenqueue takes an element and a queue and enqueues the given element into the queue.

Example:

> (enqueue 10 (queue 1 2 3 4 5 6))
- : #(struct:Queue
      ((Rec
        g294181
        (U (Boxof (U (-> (Pairof Integer g294181)) (Pairof Integer g294181)))
           Null))
       (Listof Integer)
       (Rec
        g294184
        (U (Boxof (U (-> (Pairof Integer g294184)) (Pairof Integer g294184)))
           Null))))
#<Queue>

In the above example, (enqueue 10 que) adds 10 to the end of (queue 1 2 3 4 5 6) and returns (queue 1 2 3 4 5 6 10).

procedure
(head que) → A
que : (Queue A)

Function head takes a queue and gives the first element in the queue if queue is not empty else throws an error.

Examples:

> (head (queue 1 2 3 4 5 6))
- : Integer
1
> (head (empty Integer))
head: given queue is empty

procedure
(tail que) → (Queue A)
que : (Queue A)

Function tail takes a queue and returns the same queue without head element of the given queue if its a non empty queue else throws an error.

Examples:

> (tail (queue 1 2 3 4 5 6))
- : #(struct:Queue
      ((Rec
        g294221
        (U (Boxof (U (-> (Pairof Integer g294221)) (Pairof Integer g294221)))
           Null))
       (Listof Integer)
       (Rec
        g294224
        (U (Boxof (U (-> (Pairof Integer g294224)) (Pairof Integer g294224)))
           Null))))
#<Queue>
> (tail (empty Integer))
tail: given queue is empty

In the above example, (tail (queue 1 2 3 4 5 6)), returns (queue 2 3 4 5 6).

procedure
(queue->list que) → (Queue A)
que : (Queue A)

Function queue->list takes a queue and returns a list of elements. The list will have head of the given queue as its first element. If the given queue is empty, then it returns an empty list.

Example:

> (queue->list (queue 10 2 34 4 15 6))
- : (Listof Integer)
'(10 2 34 4 15 6)

procedure
(map func que1 que2 ...) → (Queue A)
  func : (A B ... B -> C)
  que1 : (Queue A)
  que2 : (Queue B)

Function map is similar to map for lists.

Examples:

> (queue->list (map add1 (queue 1 2 3 4 5 6)))
- : (Listof Integer)
'(2 3 4 5 6 7)
> (queue->list (map * (queue 1 2 3 4 5 6) (queue 1 2 3 4 5 6)))
- : (Listof Integer)
'(1 4 9 16 25 36)

procedure
(fold func init que1 que2 ...) → C
  func : (C A B ... B -> C)
  init : C
  que1 : (Queue A)
  que2 : (Queue B)

Function fold is similar to foldl or foldr

fold currently does not produce correct results when the given function is non-commutative.

Examples:

> (fold + 0 (queue 1 2 3 4 5 6))
- : Integer
21
> (fold * 1 (queue 1 2 3 4 5 6) (queue 1 2 3 4 5 6))
- : Integer
518400

procedure
(filter func que) → (Queue A)
func : (A -> Boolean)
que : (Queue A)

Function filter is similar to filter.

Examples:

> (define que (queue 1 2 3 4 5 6))
> (queue->list (filter (λ: ([x : Integer]) (> x 5)) que))
- : (Listof Integer)
'(6)
> (queue->list (filter (λ: ([x : Integer]) (< x 5)) que))
- : (Listof Integer)
'(1 2 3 4)
> (queue->list (filter (λ: ([x : Integer]) (<= x 5)) que))
- : (Listof Integer)
'(1 2 3 4 5)

procedure
(remove func que) → (Queue A)
func : (A -> Boolean)
que : (Queue A)

Function remove is similar to filter but remove removes the elements which match the predicate.

Examples:

> (queue->list (remove (λ: ([x : Integer]) (> x 5))
                       (queue 1 2 3 4 5 6)))
- : (Listof Integer)
'(1 2 3 4 5)
> (queue->list (remove (λ: ([x : Integer]) (< x 5))
                       (queue 1 2 3 4 5 6)))
- : (Listof Integer)
'(5 6)
> (queue->list (remove (λ: ([x : Integer]) (<= x 5))
                       (queue 1 2 3 4 5 6)))
- : (Listof Integer)
'(6)

procedure
(andmap func que1 que2 ...) → Boolean
  func : (A B ... B -> Boolean)
  que1 : (Queue A)
  que2 : (Queue B)

Function andmap is similar to andmap.

Examples:

> (andmap even? (queue 1 2 3 4 5 6))
- : Boolean
#f
> (andmap odd? (queue 1 2 3 4 5 6))
- : Boolean
#f
> (andmap positive? (queue 1 2 3 4 5 6))
- : Boolean
#t
> (andmap negative? (queue -1 -2))
- : Boolean
#t

procedure
(ormap func que1 que2 ...) → Boolean
  func : (A B ... B -> Boolean)
  que1 : (Queue A)
  que2 : (Queue B)

Function ormap is similar to ormap.

Examples:

> (ormap even? (queue 1 2 3 4 5 6))
- : Boolean
#t
> (ormap odd? (queue 1 2 3 4 5 6))
- : Boolean
#t
> (ormap positive? (queue -1 -2 3 4 -5 6))
- : Boolean
#t
> (ormap negative? (queue 1 -2))
- : Boolean
#t

procedure
(build-queue size func) → (Queue A)
size : Natural
func : (Natural -> A)

Function build-queue is similar to build-list.

Examples:

> (queue->list (build-queue 5 (λ:([x : Integer]) (add1 x))))
- : (Listof Integer)
'(1 2 3 4 5)
> (queue->list (build-queue 5 (λ:([x : Integer]) (* x x))))
- : (Listof Integer)
'(0 1 4 9 16)

procedure
(head+tail que) → (Pair A (Queue A))
que : (Queue A)

Function head+tail returns a pair containing the head and the tail of the given queue.

Examples:

> (head+tail (queue 1 2 3 4 5))
- : (Pairof
     Integer
     #(struct:Queue
       ((Rec
         g294604
         (U (Boxof (U (-> (Pairof Integer g294604)) (Pairof Integer g294604)))
            Null))
        (Listof Integer)
        (Rec
         g294607
         (U (Boxof (U (-> (Pairof Integer g294607)) (Pairof Integer g294607)))
            Null)))))
'(1 . #<Queue>)
> (head+tail (build-queue 5 (λ:([x : Integer]) (* x x))))
- : (Pairof
     Integer
     #(struct:Queue
       ((Rec
         g294623
         (U (Boxof (U (-> (Pairof Integer g294623)) (Pairof Integer g294623)))
            Null))
        (Listof Integer)
        (Rec
         g294626
         (U (Boxof (U (-> (Pairof Integer g294626)) (Pairof Integer g294626)))
            Null)))))
'(0 . #<Queue>)
> (head+tail (empty Integer))
head+tail: given queue is empty

1.6 Hood-Melville Queue🔗ℹ

(require pfds/queue/hood-melville)

package: pfds

Similar to real-time queues in many ways. But the implementation is much more complicated than Real-Time Queue. Uses a technique called Global Rebuilding. The data structure gives a worst case running time of O(1) for the operations head, tail and enqueue.

syntax
(Queue A)

A Hood-Melville queue of type A.

procedure
(queue a ...) → (Queue A)
a : A

Function queue creates a Hood-Melville with the given inputs.

Example:

> (queue 1 2 3 4 5 6)
- : #(struct:Queue
      (Integer
       (Listof Positive-Byte)
       (U (Appending Positive-Byte)
          (Done Positive-Byte)
          (Reversing Positive-Byte)
          Null)
       Integer
       (Listof Positive-Byte)))
#<Queue>

In the above example, the queue obtained will have 1 as its head element.

value
empty : (Queue Nothing)

An empty queue.

procedure
(empty? que) → Boolean
que : (Queue A)

Function empty? checks if the given queue is empty or not.

Examples:

> (empty? (queue 1 2 3 4 5 6))
- : Boolean
#f
> (empty? empty)
- : Boolean
#t

procedure
(enqueue a que) → (Queue A)
a : A
que : (Queue A)

Function enqueue takes an element and a queue and enqueues the given element into the queue.

Example:

> (enqueue 10 (queue 1 2 3 4 5 6))
- : #(struct:Queue
      (Integer
       (Listof Positive-Byte)
       (U (Appending Positive-Byte)
          (Done Positive-Byte)
          (Reversing Positive-Byte)
          Null)
       Integer
       (Listof Positive-Byte)))
#<Queue>

In the above example, enqueue adds the element 10 to (queue 1 2 3 4 5 6) and returns (queue 1 2 3 4 5 6 10).

procedure
(head que) → A
que : (Queue A)

Function head takes a queue and gives the first element in the queue if queue is not empty else throws an error.

Examples:

> (head (queue 1 2 3 4 5 6))
- : Integer [more precisely: Positive-Byte]
1
> (head empty)
head: given queue is empty

procedure
(tail que) → (Queue A)
que : (Queue A)

Function tail takes a queue and returns a queue with rest elements if its a non empty queue else throws an error.

Examples:

> (tail (queue 1 2 3 4 5 6))
- : #(struct:Queue
      (Integer
       (Listof Positive-Byte)
       (U (Appending Positive-Byte)
          (Done Positive-Byte)
          (Reversing Positive-Byte)
          Null)
       Integer
       (Listof Positive-Byte)))
#<Queue>
> (tail empty)
tail: given queue is empty

In the above example, (tail (queue 1 2 3 4 5 6)), returns (queue 2 3 4 5 6).

procedure
(queue->list que) → (Queue A)
que : (Queue A)

Function queue->list takes a queue and returns a list of elements. The list will have head of the given queue as its first element. If the given queue is empty, then it returns an empty list. For

Examples:

> (queue->list (queue 10 2 34 4 15 6))
- : (Listof Positive-Byte)
'(10 2 34 4 15 6)
> (queue->list empty)
- : (Listof Nothing)
'()

procedure
(map func que1 que2 ...) → (Queue A)
  func : (A B ... B -> C)
  que1 : (Queue A)
  que2 : (Queue B)

Function map is similar to map for lists.

Examples:

> (queue->list (map add1 (queue 1 2 3 4 5 6)))
- : (Listof Positive-Index)
'(2 3 4 5 6 7)
> (queue->list (map * (queue 1 2 3 4 5 6) (queue 1 2 3 4 5 6)))
- : (Listof Positive-Index)
'(1 4 9 16 25 36)

procedure
(fold func init que1 que2 ...) → C
  func : (C A B ... B -> C)
  init : C
  que1 : (Queue A)
  que2 : (Queue B)

Function fold is similar to foldl or foldr

fold currently does not produce correct results when the given function is non-commutative.

Examples:

> (fold + 0 (queue 1 2 3 4 5 6))
- : Integer [more precisely: Nonnegative-Integer]
21
> (fold * 1 (queue 1 2 3 4 5 6) (queue 1 2 3 4 5 6))
- : Integer [more precisely: Positive-Integer]
518400

procedure
(filter func que) → (Queue A)
func : (A -> Boolean)
que : (Queue A)

Function filter is similar to filter.

Examples:

> (define que (queue 1 2 3 4 5 6))
> (queue->list (filter (λ: ([x : Integer]) (> x 5)) que))
- : (Listof Positive-Byte)
'(6)
> (queue->list (filter (λ: ([x : Integer]) (< x 5)) que))
- : (Listof Positive-Byte)
'(1 2 3 4)
> (queue->list (filter (λ: ([x : Integer]) (<= x 5)) que))
- : (Listof Positive-Byte)
'(1 2 3 4 5)

procedure
(remove func que) → (Queue A)
func : (A -> Boolean)
que : (Queue A)

Function remove is similar to filter but remove removes the elements which match the predicate.

Examples:

> (queue->list (remove (λ: ([x : Integer]) (> x 5))
                       (queue 1 2 3 4 5 6)))
- : (Listof Positive-Byte)
'(1 2 3 4 5)
> (queue->list (remove (λ: ([x : Integer]) (< x 5))
                       (queue 1 2 3 4 5 6)))
- : (Listof Positive-Byte)
'(5 6)
> (queue->list (remove (λ: ([x : Integer]) (<= x 5))
                       (queue 1 2 3 4 5 6)))
- : (Listof Positive-Byte)
'(6)

procedure
(andmap func que1 que2 ...) → Boolean
  func : (A B ... B -> Boolean)
  que1 : (Queue A)
  que2 : (Queue B)

Function andmap is similar to andmap.

Examples:

> (andmap even? (queue 1 2 3 4 5 6))
- : Boolean
#f
> (andmap odd? (queue 1 2 3 4 5 6))
- : Boolean
#f
> (andmap positive? (queue 1 2 3 4 5 6))
- : Boolean
#t
> (andmap negative? (queue -1 -2))
- : Boolean
#t

procedure
(ormap func que1 que2 ...) → Boolean
  func : (A B ... B -> Boolean)
  que1 : (Queue A)
  que2 : (Queue B)

Function ormap is similar to ormap.

Examples:

> (ormap even? (queue 1 2 3 4 5 6))
- : Boolean
#t
> (ormap odd? (queue 1 2 3 4 5 6))
- : Boolean
#t
> (ormap positive? (queue -1 -2 3 4 -5 6))
- : Boolean
#t
> (ormap negative? (queue 1 -2))
- : Boolean
#t

procedure
(build-queue size func) → (Queue A)
size : Natural
func : (Natural -> A)

Function build-queue is similar to build-list.

Examples:

> (queue->list (build-queue 5 (λ:([x : Integer]) (add1 x))))
- : (Listof Integer)
'(1 2 3 4 5)
> (queue->list (build-queue 5 (λ:([x : Integer]) (* x x))))
- : (Listof Integer)
'(0 1 4 9 16)

procedure
(head+tail que) → (Pair A (Queue A))
que : (Queue A)

Function head+tail returns a pair containing the head and the tail of the given queue.

Examples:

> (head+tail (queue 1 2 3 4 5))
- : (Pairof
     Positive-Byte
     #(struct:Queue
       (Integer
        (Listof Positive-Byte)
        (U (Appending Positive-Byte)
           (Done Positive-Byte)
           (Reversing Positive-Byte)
           Null)
        Integer
        (Listof Positive-Byte))))
'(1 . #<Queue>)
> (head+tail (build-queue 5 (λ:([x : Integer]) (* x x))))
- : (Pairof
     Integer
     #(struct:Queue
       (Integer
        (Listof Integer)
        (U (Appending Integer) (Done Integer) (Reversing Integer) Null)
        Integer
        (Listof Integer))))
'(0 . #<Queue>)
> (head+tail empty)
head+tail: given queue is empty

1	Queues
2	Deques
3	Heaps
4	Random Access Lists
5	VList
6	Streams
7	Red-Black Trees
8	Tries
9	Treap

1.1	Banker’s Queue
1.2	Physicist’s Queue
1.3	Implicit Queue
1.4	Bootstraped Queue
1.5	Real-Time Queue
1.6	Hood-Melville Queue