← Index

x/type/deque

A double-ended queue, homed on the Deque class.

Two-list construction: each element moves between the lists at most once, so both ends pop amortized O(1); length rides a counter.

Class Deque

A double-ended queue: push!/pop! work the right end, push-left!/pop-left! the left, all amortized O(1) (the two-list construction). Empty pops raise tag ‘value.

front

Member: data carried by a Deque instance.

back

Member: data carried by a Deque instance.

len

Member: data carried by a Deque instance.

(Deque make)

An empty deque.

Returns: Deque — A new empty deque

Examples:

((Deque make) length) => 0

(push-left! v)

Push onto the left end: O(1). Returns the deque for chaining.

Instance method: called on a Deque instance.

Parameters:

• v : ANY — Value for the left end

Returns: Deque — self

(push! v)

Push onto the right end: O(1). Returns the deque for chaining.

Instance method: called on a Deque instance.

Parameters:

• v : ANY — Value for the right end

Returns: Deque — self

(%feed-front!)

Instance method: called on a Deque instance.

(%feed-back!)

Instance method: called on a Deque instance.

(pop-left!)

Remove and return the leftmost value: amortized O(1); raises tag ‘value when empty.

Instance method: called on a Deque instance.

Returns: ANY — The leftmost value

Examples:

(let ((d (Deque make))) (d push! 1) (d push! 2) (d pop-left!)) => 1

(pop!)

Remove and return the rightmost value: amortized O(1); raises tag ‘value when empty.

Instance method: called on a Deque instance.

Returns: ANY — The rightmost value

Examples:

(let ((d (Deque make))) (d push! 1) (d push! 2) (d pop!)) => 2

(peek-left)

The leftmost value without removing it; raises tag ‘value when empty.

Instance method: called on a Deque instance.

Returns: ANY — The leftmost value

(peek)

The rightmost value without removing it; raises tag ‘value when empty. O(n) when every element sits on the far list; the pops stay amortized O(1).

Instance method: called on a Deque instance.

Returns: ANY — The rightmost value

(length)

How many values the deque holds (kept O(1)).

Instance method: called on a Deque instance.

Returns: INT — The count

(empty?)

Is the deque empty?

Instance method: called on a Deque instance.

Returns: BOOL — #t when it holds nothing

(->list)

The deque’s values, left to right, as a fresh list; the deque is untouched.

Instance method: called on a Deque instance.

Returns: LIST — Values in deque order