1 Queues

Following queue structures implement and provide the functions empty?, enqueue, head, tail, queue and queue->list. All the queue structures are polymorphic and have the type (Queue A).

1.1 Banker’s Queue

(require "bankers-queue.ss")

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

Example:

> (queue 1 2 3 4 5 6)

- : (Queue Positive-Fixnum)

#<Queue>

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

Examples:

> (empty? (queue 1 2 3 4 5 6))

- : Boolean

#f

> (empty? empty)

- : Boolean

#t

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).

Examples:

> (tail (queue 4 5 6))

- : (Queue Positive-Fixnum)

#<Queue>

> (tail empty)

tail: given queue is empty

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

Examples:

> (queue->list (queue 10 2 34 4 15 6))

- : (Listof Positive-Fixnum)

'(10 2 34 4 15 6)

> (queue->list empty)

- : (Listof Nothing)

'()

Examples:

> (fold + 0 (queue 1 2 3 4 5 6))

- : Exact-Nonnegative-Integer

21

> (fold * 1 (queue 1 2 3 4 5 6) (queue 1 2 3 4 5 6))

- : Exact-Positive-Integer

518400

1.2 Physicist’s Queue

(require "physicists-queue.ss")

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.

Example:

> (queue 1 2 3 4 5 6)

- : (Queue Positive-Fixnum)

#<Queue>

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

Examples:

> (empty? (queue 1 2 3 4 5 6))

- : Boolean

#f

> (empty? empty)

- : Boolean

#t

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).

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

Examples:

> (queue->list (queue 10 2 34 4 15 6))

- : (Listof Positive-Fixnum)

'(10 2 34 4 15 6)

> (queue->list empty)

- : (Listof Nothing)

'()

Examples:

> (fold + 0 (queue 1 2 3 4 5 6))

- : Exact-Nonnegative-Integer

21

> (fold * 1 (queue 1 2 3 4 5 6) (queue 1 2 3 4 5 6))

- : Exact-Positive-Integer

518400

1.3 Implicit Queue

(require "implicitqueue.ss")

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.

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

Examples:

> (empty? (queue 1 2 3 4 5 6))

- : Boolean

#f

> (empty? empty)

- : Boolean

#t

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).

Examples:

> (queue->list (queue 10 2 34 4 15 6))

- : (Listof Positive-Fixnum)

'(10 2 34 4 15 6)

> (queue->list empty)

- : (Listof Nothing)

'()

Examples:

> (fold + 0 (queue 1 2 3 4 5 6))

- : Exact-Nonnegative-Integer

21

> (fold * 1 (queue 1 2 3 4 5 6) (queue 1 2 3 4 5 6))

- : Exact-Positive-Integer

518400

1.4 Bootstraped Queue

(require "bootstrapedqueue.ss")

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 Real-Time Queue.

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

Examples:

> (empty? (queue 1 2 3 4 5 6))

- : Boolean

#f

> (empty? empty)

- : Boolean

#t

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.

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).

Examples:

> (queue->list (queue 10 2 34 4 15 6))

- : (Listof Positive-Fixnum)

'(10 2 34 4 15 6)

> (queue->list empty)

- : (Listof Nothing)

'()

Examples:

> (fold + 0 (queue 1 2 3 4 5 6))

- : Exact-Nonnegative-Integer

21

> (fold * 1 (queue 1 2 3 4 5 6) (queue 1 2 3 4 5 6))

- : Exact-Positive-Integer

518400

1.5 Real-Time Queue

(require "realtimequeue.ss")

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.

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

Examples:

> (empty? (queue 1 2 3 4 5 6))

- : Boolean

#f

> (empty? empty)

- : Boolean

#t

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).

Examples:

> (tail (queue 1 2 3 4 5 6))

- : (Queue Positive-Fixnum)

#<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).

Example:

> (queue->list (queue 10 2 34 4 15 6))

- : (Listof Positive-Fixnum)

'(10 2 34 4 15 6)

Examples:

> (fold + 0 (queue 1 2 3 4 5 6))

- : Exact-Nonnegative-Integer

21

> (fold * 1 (queue 1 2 3 4 5 6) (queue 1 2 3 4 5 6))

- : Exact-Positive-Integer

518400