Mnemonist

Fixed Deque


The FixedDeque is a fixed capacity double-ended queue (abbr. deque) that can be used both as a LIFO or FIFO list very efficiently.

For more information about the deque, you can head here.

Note that, contrary to the CircularBuffer, the FixedDeque will throw when overflowing capacity.

var FixedDeque = require('mnemonist/fixed-deque');

Constructor

The FixedDeque takes two arguments: a array class to use, and the desired capacity.

var deque = new FixedDeque(Array, 10);

// Using byte arrays
var deque = new FixedDeque(Int8Array, 10);

Static #.from

Alternatively, one can build a FixedDeque from an arbitrary JavaScript iterable likewise:

// Attempting the guess the given iterable's length/size
var deque = FixedDeque.from([1, 2, 3], Int8Array);

// Providing the desired capacity
var deque = FixedDeque.from([1, 2, 3], Int8Array, 10);

Members

Methods

Mutation

Read

Iteration

#.capacity

Maximum number of items the deque is able to store.

var deque = new FixedDeque(Array, 10);
deque.capacity
>>> 10

#.size

Number of items in the deque.

var deque = new FixedDeque(Array, 10);
deque.size
>>> 0

#.push

Append an item at the end of the deque.

Will throw if the deque’s capacity is exceeded.

O(1)

var deque = new FixedDeque(Array, 10);

deque.push(1);

#.unshift

Prepend an item at the beginning of the deque.

Will throw if the deque’s capacity is exceeded.

O(1)

var deque = new FixedDeque(Array, 10);

deque.unshift(1);

#.pop

Retrieve & remove the last item of the deque.

O(1)

var deque = new FixedDeque(Array, 10);

deque.push(1);
deque.push(2);
deque.pop();
>>> 2

#.shift

Retrieve & remove the first item of the deque.

O(1)

var deque = new FixedDeque(Array, 10);

deque.push(1);
deque.push(2);
deque.shift();
>>> 1

#.clear

Completely clears the deque.

O(1)

var deque = new FixedDeque(Array, 10);

deque.push(1);
deque.clear();
deque.toArray();
>>> []

#.peekFirst

Retrieves the first item of the deque.

O(1)

var deque = new FixedDeque(Array, 10);

deque.push(1);
deque.push(2);
deque.peekFirst();
>>> 1

#.peekLast

Retrieves the last item of the deque.

O(1)

var deque = new FixedDeque(Array, 10);

deque.push(1);
deque.push(2);
deque.peekLast();
>>> 2

#.forEach

Iterates over the deque’s values.

var deque = new FixedDeque(Array, 10);

deque.push(1);
deque.push(2);

deque.forEach(function(item, index, deque) {
  console.log(index, item);
});

#.toArray

Converts the deque into a JavaScript array.

Note that the resulting array will be instantiated using the provided class.

var deque = new FixedDeque(Array, 10);

deque.push(1);
deque.push(2);

deque.toArray();
>>> [1, 2]

#.values

Returns an iterator over the deque’s values.

var deque = FixedDeque.from([1, 2, 3], Array);

var iterator = deque.values();

iterator.next().value
>>> 1

#.entries

Returns an iterator over the deque’s entries.

var deque = FixedDeque.from([1, 2, 3], Array);

var iterator = deque.entries();

iterator.next().value
>>> [0, 1]

Iterable

Alternatively, you can iterate over a deque’s values using ES2015 for...of protocol:

var deque = FixedDeque.from([1, 2, 3], Array);

for (var item of deque) {
  console.log(item);
}