On this page:
2.1 Bankers Deque
Deque
deque
empty
empty?
enqueue
enqueue-front
head
last
tail
init
deque->list
map
foldl
foldr
filter
remove
2.2 Implicit Deque
Deque
deque
empty
empty?
enqueue
enqueue-front
head
last
tail
init
deque->list
map
foldl
foldr
filter
remove
2.3 Real-Time Deque
Deque
deque
empty
empty?
enqueue
enqueue-front
head
last
tail
init
deque->list
map
foldl
foldr
filter
remove
Version: 5.0.1.3

2 Deques

Following Deque data structures implement and provide the functions deque, empty?, enqueue, enqueue-front, head, tail, last, init and deque->list. All the deque structures are polymorphic.

    2.1 Bankers Deque

    2.2 Implicit Deque

    2.3 Real-Time Deque

2.1 Bankers Deque

 (require (planet krhari/pfds:1:3/bankers-deque))

Bankers Deques are Amortized double ended deques also known as deque developed using Bankers method. Provides amortized running time of O(1) for the operations head, tail, last, init, enqueue-front and enqueue. Uses lazy evaluation and memoization to achieve the amortized running time.

(Deque A)
A banker’s deque of type A.

(deque a ...)  (Deque A)
  a : A
Function deque creates a Bankers Deque with the given inputs.

Example:

  > (deque 1 2 3 4 5 6)

  - : (Deque Positive-Fixnum)

  #<Deque>

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

empty : (Deque Nothing)
An empty deque

(empty? dq)  Boolean
  dq : (Deque A)
Function empty? checks if the given deque is empty.

Examples:

  > (empty? empty)

  - : Boolean

  #t

  > (empty? (deque 1 2))

  - : Boolean

  #f

(enqueue a deq)  (Deque A)
  a : A
  deq : (Deque A)
Function enqueue takes an element and a deque and enqueues the given element in the deque.

Example:

  > (enqueue 10 (deque 3 2 4))

  - : (Deque Positive-Fixnum)

  #<Deque>

In the above example, (enqueue 10 deq) adds the element 10 to (deque 3 2 4). 10 will be the last element in the deque.

(enqueue-front a deq)  (Deque A)
  a : A
  deq : (Deque A)
Function enqueue-front takes an element and a deque and puts the given element to the front of the given deque.

Example:

  > (enqueue-front 10 (deque 5 6 3 4))

  - : (Deque Positive-Fixnum)

  #<Deque>

In the above example, (enqueue-front 10 (deque 5 6 3 4)) adds 10 to the front of the (deque 5 6 3 4). 10 will be the head element.

(head deq)  A
  deq : (Deque A)
Function head takes a deque and gives the first element in the deque if deque is not empty else throws an error.

Examples:

  > (head (deque 5 2 3))

  - : Positive-Fixnum

  5

  > (head empty)

  head: given deque is empty

In the above example, (head empty) throws an error since the given deque is empty.

(last deq)  A
  deq : (Deque A)
Function last takes a deque and gives the last element in the deque if deque is not empty else throws an error.

Examples:

  > (last (deque 1 2 3 4 5 6))

  - : Positive-Fixnum

  6

  > (last empty)

  last: given deque is empty

In the above example, (last empty)throws an error since the given deque is empty.

(tail deq)  (Deque A)
  deq : (Deque A)
Function tail takes a deque and returns the given deque without the first element if the given deque is non empty else throws an error.

Examples:

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

  - : (Deque Positive-Fixnum)

  #<Deque>

  > (tail empty)

  tail: given deque is empty

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

(init deq)  (Deque A)
  deq : (Deque A)
Function init takes a deque and returns the given deque without the last element if the given deque is not empty else throws an error.

Examples:

  > (init (deque 1 2 3 4 5 6))

  - : (Deque Positive-Fixnum)

  #<Deque>

  > (init empty)

  init: given deque is empty

In the above example, (init (deque 1 2 3 4 5 6)), removes the last element 6 and returns (deque 1 2 3 4 5).

(deque->list deq)  (Listof A)
  deq : (Deque A)
Function deque->list takes a deque and returns a list of elements. The list will have head of the given deque as its first element. If the given deque is empty, then it returns an empty list.

Examples:

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

  - : (Listof Positive-Fixnum)

  '(10 2 34 4 15 6)

  > (deque->list empty)

  - : (Listof Nothing)

  '()

(map func deq1 deq2 ...)  (Deque A)
  func : (A B ... B -> C)
  deq1 : (Deque A)
  deq2 : (Deque B)
Function map is similar to map for lists.

Examples:

  > (deque->list (map add1 (deque 1 2 3 4 5 6)))

  - : (Listof Exact-Positive-Integer)

  '(2 3 4 5 6 7)

  > (deque->list (map * (deque 1 2 3 4 5 6) (deque 1 2 3 4 5 6)))

  - : (Listof Exact-Positive-Integer)

  '(1 4 9 16 25 36)

(foldl func init deq1 deq2 ...)  C
  func : (C A B ... B -> C)
  init : C
  deq1 : (Deque A)
  deq2 : (Deque B)
Function foldl is similar to foldl

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

Examples:

  > (foldl + 0 (deque 1 2 3 4 5 6))

  - : Exact-Nonnegative-Integer

  21

  > (foldl * 1 (deque 1 2 3 4 5 6) (deque 1 2 3 4 5 6))

  - : Exact-Positive-Integer

  518400

(foldr func init deq1 deq2 ...)  C
  func : (C A B ... B -> C)
  init : C
  deq1 : (Deque A)
  deq2 : (Deque B)
Function foldr is similar to foldr

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

Examples:

  > (foldr + 0 (deque 1 2 3 4 5 6))

  - : Exact-Nonnegative-Integer

  21

  > (foldr * 1 (deque 1 2 3 4 5 6) (deque 1 2 3 4 5 6))

  - : Exact-Positive-Integer

  518400

(filter func que)  (Deque A)
  func : (A -> Boolean)
  que : (Deque A)
Function filter is similar to filter.

Examples:

  > (define que (deque 1 2 3 4 5 6))
  > (deque->list (filter (λ: ([x : Integer]) (> x 5)) que))

  - : (Listof Positive-Fixnum)

  '(6)

  > (deque->list (filter (λ: ([x : Integer]) (< x 5)) que))

  - : (Listof Positive-Fixnum)

  '(1 2 3 4)

  > (deque->list (filter (λ: ([x : Integer]) (<= x 5)) que))

  - : (Listof Positive-Fixnum)

  '(1 2 3 4 5)

(remove func que)  (Deque A)
  func : (A -> Boolean)
  que : (Deque A)
Function remove is similar to filter but remove removes the elements which match the predicate.

Examples:

  > (deque->list (remove (λ: ([x : Integer]) (> x 5))
                         (deque 1 2 3 4 5 6)))

  - : (Listof Positive-Fixnum)

  '(1 2 3 4 5)

  > (deque->list (remove (λ: ([x : Integer]) (< x 5))
                         (deque 1 2 3 4 5 6)))

  - : (Listof Positive-Fixnum)

  '(5 6)

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

  - : (Listof Positive-Fixnum)

  '(6)

2.2 Implicit Deque

 (require (planet krhari/pfds:1:3/implicitdeque))

Deques obtained by applying Implicit Recursive Slowdown. Provides amortized running time of O(1) for the operations head, tail, last, init, enqueue-front 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.

(Deque A)
Implicit double ended queue of type A.

(deque a ...)  (Deque A)
  a : A
Function deque creates a Implicit Deque with the given inputs.

Example:

  > (deque 1 2 3 4 5 6)

  - : (U (Shallow Positive-Fixnum) (Deep Positive-Fixnum))

  #<Deep>

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

empty : (Deque Nothing)
An empty deque

(empty? dq)  Boolean
  dq : (Deque A)
Function empty? checks if the given deque is empty or not.

Examples:

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

  - : Boolean

  #f

  > (empty? empty)

  - : Boolean

  #t

(enqueue a deq)  (Deque A)
  a : A
  deq : (Deque A)
Function enqueue takes an element and a deque and enqueues the given element into the deque.

Example:

  > (enqueue 10 (deque 1 2 3 4 5 6))

  - : (U (Shallow Positive-Fixnum) (Deep Positive-Fixnum))

  #<Deep>

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

(enqueue-front a deq)  (Deque A)
  a : A
  deq : (Deque A)
Function enqueue-front takes an element and a deque and puts the given element to the front of the given deque.

Example:

  > (enqueue-front 10 (deque 5 6 3 4))

  - : (U (Shallow Positive-Fixnum) (Deep Positive-Fixnum))

  #<Deep>

In the above example, (enqueue-front 10 (deque 5 6 3 4)) adds 10 to the front of the (deque 5 6 3 4). 10 will be the head element.

(head deq)  A
  deq : (Deque A)
Function head takes a deque and gives the first element in the deque if deque is not empty else throws an error.

Examples:

  > (head (deque 1 2 3 4 5 6))

  - : Positive-Fixnum

  1

  > (head empty)

  head: given deque is empty

(last deq)  A
  deq : (Deque A)
Function last takes a deque and gives the last element in the queue if deque is not empty else throws an error.

Examples:

  > (last (deque 1 2 3 4 5 6))

  - : Positive-Fixnum

  6

  > (last empty)

  last: given deque is empty

(tail deq)  (Deque A)
  deq : (Deque A)
Function tail takes a deque and returns a deque with rest elements if its a non empty deque else throws an error.

Examples:

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

  - : (U (Shallow Positive-Fixnum) (Deep Positive-Fixnum))

  #<Deep>

  > (tail empty)

  tail: given deque is empty

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

(init deq)  (Deque A)
  deq : (Deque A)
Function init takes a deque and returns a deque without the last element if its a non empty deque else throws an error.

Examples:

  > (init (deque 1 2 3 4 5 6))

  - : (U (Shallow Positive-Fixnum) (Deep Positive-Fixnum))

  #<Deep>

  > (init empty)

  init: given deque is empty

In the above example, (init (deque 1 2 3 4 5 6)), removes the last element 6 and returns (deque 1 2 3 4 5)

(deque->list deq)  (Listof A)
  deq : (Deque A)
Function deque->list takes a deque and returns a list of elements. The list will have head of the given deque as its first element. If the given deque is empty, then it returns an empty list.

Example:

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

  - : (Listof Positive-Fixnum)

  '(10 2 34 4 15 6)

(map func deq1 deq2 ...)  (Deque A)
  func : (A B ... B -> C)
  deq1 : (Deque A)
  deq2 : (Deque B)
Function map is similar to map for lists.

Examples:

  > (deque->list (map add1 (deque 1 2 3 4 5 6)))

  - : (Listof Exact-Positive-Integer)

  '(2 3 4 5 6 7)

  > (deque->list (map * (deque 1 2 3 4 5 6) (deque 1 2 3 4 5 6)))

  - : (Listof Exact-Positive-Integer)

  '(1 4 9 16 25 36)

(foldl func init deq1 deq2 ...)  C
  func : (C A B ... B -> C)
  init : C
  deq1 : (Deque A)
  deq2 : (Deque B)
Function foldl is similar to foldl

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

Examples:

  > (foldl + 0 (deque 1 2 3 4 5 6))

  - : Exact-Nonnegative-Integer

  21

  > (foldl * 1 (deque 1 2 3 4 5 6) (deque 1 2 3 4 5 6))

  - : Exact-Positive-Integer

  518400

(foldr func init deq1 deq2 ...)  C
  func : (C A B ... B -> C)
  init : C
  deq1 : (Deque A)
  deq2 : (Deque B)
Function foldr is similar to foldr

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

Examples:

  > (foldr + 0 (deque 1 2 3 4 5 6))

  - : Exact-Nonnegative-Integer

  21

  > (foldr * 1 (deque 1 2 3 4 5 6) (deque 1 2 3 4 5 6))

  - : Exact-Positive-Integer

  518400

(filter func que)  (Deque A)
  func : (A -> Boolean)
  que : (Deque A)
Function filter is similar to filter.

Examples:

  > (define que (deque 1 2 3 4 5 6))
  > (deque->list (filter (λ: ([x : Integer]) (> x 5)) que))

  - : (Listof Positive-Fixnum)

  '(6)

  > (deque->list (filter (λ: ([x : Integer]) (< x 5)) que))

  - : (Listof Positive-Fixnum)

  '(1 2 3 4)

  > (deque->list (filter (λ: ([x : Integer]) (<= x 5)) que))

  - : (Listof Positive-Fixnum)

  '(1 2 3 4 5)

(remove func que)  (Deque A)
  func : (A -> Boolean)
  que : (Deque A)
Function remove is similar to filter but remove removes the elements which match the predicate.

Examples:

  > (deque->list (remove (λ: ([x : Integer]) (> x 5))
                         (deque 1 2 3 4 5 6)))

  - : (Listof Positive-Fixnum)

  '(1 2 3 4 5)

  > (deque->list (remove (λ: ([x : Integer]) (< x 5))
                         (deque 1 2 3 4 5 6)))

  - : (Listof Positive-Fixnum)

  '(5 6)

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

  - : (Listof Positive-Fixnum)

  '(6)

2.3 Real-Time Deque

 (require (planet krhari/pfds:1:3/realtimedeque))

Real-Time Deques eliminate the amortization by using two techniques Scheduling and a variant of Global Rebuilding called Lazy Rebuilding. The data structure gives a worst case running time of O(1) for the operations head, tail, last, init, enqueue-front and enqueue.

(Deque A)
Real-time double ended queue of type A.

(deque a ...)  (Deque A)
  a : A
Function deque creates a Real-Time Deque with the given inputs.

Example:

  > (deque 1 2 3 4 5 6)

  - : (Deque Positive-Fixnum)

  #<Deque>

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

empty : (Deque Nothing)
An empty deque

(empty? dq)  Boolean
  dq : (Deque A)
Function empty? checks if the given deque is empty or not.

Examples:

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

  - : Boolean

  #f

  > (empty? empty)

  - : Boolean

  #t

(enqueue a deq)  (Deque A)
  a : A
  deq : (Deque A)
Function enqueue takes an element and a deque and enqueues the given element into the deque.

Example:

  > (enqueue 10 (deque 1 2 3 4 5 6))

  - : (Deque Positive-Fixnum)

  #<Deque>

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

(enqueue-front a deq)  (Deque A)
  a : A
  deq : (Deque A)
Functionenqueue-front takes an element and a deque and adds the given element to the front of deque.

Example:

  > (enqueue-front 10 (deque 1 2 3 4 5 6))

  - : (Deque Positive-Fixnum)

  #<Deque>

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

(head deq)  A
  deq : (Deque A)
Function head takes a deque and gives the first element in the deque if deque is not empty else throws an error.

Examples:

  > (head (deque 1 2 3 4 5 6))

  - : Positive-Fixnum

  1

  > (head empty)

  head: given deque is empty

(last deq)  A
  deq : (Deque A)
Function last takes a deque and gives the last element in the queue if deque is not empty else throws an error.

Examples:

  > (last (deque 1 2 3 4 5 6))

  - : Positive-Fixnum

  6

  > (last empty)

  last: given deque is empty

(tail deq)  (Deque A)
  deq : (Deque A)
Function tail takes a deque and returns a deque with rest elements if its a non empty deque else throws an error.

Examples:

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

  - : (Deque Positive-Fixnum)

  #<Deque>

  > (tail empty)

  tail: given deque is empty

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

(init deq)  (Deque A)
  deq : (Deque A)
Function init takes a deque and returns a deque without the last element if its a non empty deque else throws an error.

Examples:

  > (init (deque 1 2 3 4 5 6))

  - : (Deque Positive-Fixnum)

  #<Deque>

  > (init empty)

  init: given deque is empty

In the above example, (init (deque 1 2 3 4 5 6)), removes the last element 6 of the given deque and returns (deque 1 2 3 4 5).

(deque->list deq)  (Listof A)
  deq : (Deque A)
Function deque->list takes a deque and returns a list of elements. The list will have head of the given deque as its first element. If the given deque is empty, then it returns an empty list.

Example:

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

  - : (Listof Positive-Fixnum)

  '(10 2 34 4 15 6)

(map func deq1 deq2 ...)  (Deque A)
  func : (A B ... B -> C)
  deq1 : (Deque A)
  deq2 : (Deque B)
Function map is similar to map for lists.

Examples:

  > (deque->list (map add1 (deque 1 2 3 4 5 6)))

  - : (Listof Exact-Positive-Integer)

  '(2 3 4 5 6 7)

  > (deque->list (map * (deque 1 2 3 4 5 6) (deque 1 2 3 4 5 6)))

  - : (Listof Exact-Positive-Integer)

  '(1 4 9 16 25 36)

(foldl func init deq1 deq2 ...)  C
  func : (C A B ... B -> C)
  init : C
  deq1 : (Deque A)
  deq2 : (Deque B)
Function foldl is similar to foldl

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

Examples:

  > (foldl + 0 (deque 1 2 3 4 5 6))

  - : Exact-Nonnegative-Integer

  21

  > (foldl * 1 (deque 1 2 3 4 5 6) (deque 1 2 3 4 5 6))

  - : Exact-Positive-Integer

  518400

(foldr func init deq1 deq2 ...)  C
  func : (C A B ... B -> C)
  init : C
  deq1 : (Deque A)
  deq2 : (Deque B)
Function foldr is similar to foldr

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

Examples:

  > (foldr + 0 (deque 1 2 3 4 5 6))

  - : Exact-Nonnegative-Integer

  21

  > (foldr * 1 (deque 1 2 3 4 5 6) (deque 1 2 3 4 5 6))

  - : Exact-Positive-Integer

  518400

(filter func que)  (Deque A)
  func : (A -> Boolean)
  que : (Deque A)
Function filter is similar to filter.

Examples:

  > (define que (deque 1 2 3 4 5 6))
  > (deque->list (filter (λ: ([x : Integer]) (> x 5)) que))

  - : (Listof Positive-Fixnum)

  '(6)

  > (deque->list (filter (λ: ([x : Integer]) (< x 5)) que))

  - : (Listof Positive-Fixnum)

  '(1 2 3 4)

  > (deque->list (filter (λ: ([x : Integer]) (<= x 5)) que))

  - : (Listof Positive-Fixnum)

  '(1 2 3 4 5)

(remove func que)  (Deque A)
  func : (A -> Boolean)
  que : (Deque A)
Function remove is similar to filter but remove removes the elements which match the predicate.

Examples:

  > (deque->list (remove (λ: ([x : Integer]) (> x 5))
                         (deque 1 2 3 4 5 6)))

  - : (Listof Positive-Fixnum)

  '(1 2 3 4 5)

  > (deque->list (remove (λ: ([x : Integer]) (< x 5))
                         (deque 1 2 3 4 5 6)))

  - : (Listof Positive-Fixnum)

  '(5 6)

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

  - : (Listof Positive-Fixnum)

  '(6)