Mnemonist

Queue


A queue is simply a list in First In First Out (FIFO) order.

This just means that inserted items will get out in their insertion order.

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

var Queue = require('mnemonist/queue');

Use case

A queue is really useful to perform, for instance, the breadth-first traversal of a tree:

var queue = new Queue();
queue.enqueue(tree.root);

while (queue.size) {
  var node = queue.dequeue();
  console.log('Traversed node:', node);

  node.children.forEach(function(child) {
    queue.enqueue(child);
  });
}

Constructor

The Queue takes no argument.

Static #.from

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

var list = Queue.from([1, 2, 3]);

Static #.of

You can also build a Queue from an arbitrary set of arguments:

var queue = Queue.of(1, 2, 3);

Members

Methods

Mutation

Read

Iteration

#.size

Number of items in the queue.

var queue = new Queue();
queue.size
>>> 0

#.enqueue

Adds an item to the queue.

O(1)

var queue = new Queue();

queue.enqueue(1);

#.dequeue

Retrieve & remove the next item of the queue.

O(1) amortized

var queue = new Queue();

queue.enqueue(1);
queue.dequeue();
>>> 1

#.clear

Completely clears the queue.

var queue = new Queue();

queue.enqueue(1);
queue.clear();
queue.toArray();
>>> []

#.peek

Retrieves the next item of the queue.

O(1)

var queue = new Queue();

queue.enqueue(1);
queue.peek();
>>> 1

#.forEach

Iterates over the queue in FIFO order.

var queue = new Queue();

queue.enqueue(1);
queue.enqueue(2);

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

#.toArray

Converts the queue into a FIFO JavaScript array.

var queue = new Queue();

queue.enqueue(1);
queue.enqueue(2);

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

#.values

Returns an iterator over the queue’s values.

var queue = Queue.from([1, 2, 3]);

var iterator = queue.values();

iterator.next().value
>>> 1

#.entries

Returns an iterator over the queue’s entries.

var queue = Queue.from([1, 2, 3]);

var iterator = queue.entries();

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

Iterable

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

var queue = Queue.from([1, 2, 3]);

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