Queue

This module provides an adapter for a list so it can be used with a queue-like interface. See the Wikipedia's Queue article for more information.

Legend for tables

• API

  • value - the value to be stored in the queue
  • values - an iterable that provides values
  • iterator - an Iterator instance or an object with an iterator/iterable protocol

• Complexity

  • O - complexity of an operation
  • O(1) - constant time
  • O(n) - linear time proportional to the cache size
  • O(log n) - logarithmic time
  • O(k) - linear time proportional to the argument size

queue.js

This module provides an adapter for a list so it can be used with a queue-like interface. By default it uses ValueList:

import Queue from 'list-toolkit/queue.js';

const queue = new Queue();

Class Queue

The following properties are available:

Member	Return type	Description	O
constructor(underlyingList = new ValueList())	this	constructs a new Queue	O(k)
isEmpty()	boolean	checks if the queue is empty	O(1)
size	number	the queue's size	O(1)
list	list	the underlying list	O(1)
top	value or undefined	the queue's top element	O(1)
peek()	value or undefined	the queue's top element	O(1)
add(value)	this	add an element to the queue	O(1)
push(value)	this	an alias for add(value)	O(1)
pushBack(value)	this	an alias for add(value)	O(1)
enqueue(value)	this	an alias for add(value)	O(1)
remove()	value or undefined	remove and return the queue's top element	O(1)
pop()	value or undefined	an alias for remove()	O(1)
popFront()	value or undefined	an alias for remove()	O(1)
dequeue()	value or undefined	an alias for remove()	O(1)
addValues(values)	this	add an array of elements to the queue	O(k)
clear()	this	remove all elements from the queue	O(1)
[Symbol.iterator]()	iterator	return the default iterator starting from the first element	O(1)
getReverseIterator()	iterator or undefined	return the reverse iterator starting from the last element	O(1)

constructor(underlyingList) takes any list (DLL or SLL) as an argument. By default, it uses ValueList.

underlyingList can be non-empty. In this case it will be traversed to initialize size, which is an O(n) operation.

top and peek() is the same code packaged as a getter and as a argument-less function. They both assume that a front node has the value property, which is returned as a result. All value-based lists satisfy this requirement. If your nodes don't have value, you can always access the node directly with list.front.

add() and remove() use popFront() and pushBack() respectively. It means that for value-based lists they operate with values, not nodes. For node-based lists they operate with nodes.

If the underlying list is SLL, getReverseIterator() will return undefined.

The implementation supports several traditional queue operation schemas:

• top and peek()
• add() and remove()
• push() and pop()
• pushBack() and popFront()
• enqueue() and dequeue()

They are implemented as aliases and do not impose a penalty of thunks.

Exports

Queue is exported as Queue and as the default export.