1 Queues

9.1

Racket

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
        g292853
        (U (Pairof Positive-Byte g292853) (Promiseof g292853) 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
        g292959
        (U (Pairof Positive-Byte g292959) (Promiseof g292959) 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
        g293019
        (U (Pairof Positive-Byte g293019) (Promiseof g293019) 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
         g294056
         (U (Pairof Positive-Byte g294056) (Promiseof g294056) Null))
        Integer
        (Listof Positive-Byte)
        Integer)))
'(1 . #<Queue>)
> (head+tail (build-queue 5 (λ:([x : Integer]) (* x x))))
- : (Pairof
     Integer
     #(struct:Queue
       ((Rec g294079 (U (Pairof Integer g294079) (Promiseof g294079) 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
        g302225
        (U (Boxof (U (-> (Pairof Integer g302225)) (Pairof Integer g302225)))
           Null))
       (Listof Integer)
       (Rec
        g302228
        (U (Boxof (U (-> (Pairof Integer g302228)) (Pairof Integer g302228)))
           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
        g302281
        (U (Boxof (U (-> (Pairof Integer g302281)) (Pairof Integer g302281)))
           Null))
       (Listof Integer)
       (Rec
        g302284
        (U (Boxof (U (-> (Pairof Integer g302284)) (Pairof Integer g302284)))
           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
        g302321
        (U (Boxof (U (-> (Pairof Integer g302321)) (Pairof Integer g302321)))
           Null))
       (Listof Integer)
       (Rec
        g302324
        (U (Boxof (U (-> (Pairof Integer g302324)) (Pairof Integer g302324)))
           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
         g302704
         (U (Boxof (U (-> (Pairof Integer g302704)) (Pairof Integer g302704)))
            Null))
        (Listof Integer)
        (Rec
         g302707
         (U (Boxof (U (-> (Pairof Integer g302707)) (Pairof Integer g302707)))
            Null)))))
'(1 . #<Queue>)
> (head+tail (build-queue 5 (λ:([x : Integer]) (* x x))))
- : (Pairof
     Integer
     #(struct:Queue
       ((Rec
         g302723
         (U (Boxof (U (-> (Pairof Integer g302723)) (Pairof Integer g302723)))
            Null))
        (Listof Integer)
        (Rec
         g302726
         (U (Boxof (U (-> (Pairof Integer g302726)) (Pairof Integer g302726)))
            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