Package Exports
- @datastructures-js/queue
- @datastructures-js/queue/index.js
This package does not declare an exports field, so the exports above have been automatically detected and optimized by JSPM instead. If any package subpath is missing, it is recommended to post an issue to the original package (@datastructures-js/queue) to support the "exports" field. If that is not possible, create a JSPM override to customize the exports field for this package.
Readme
@datastructures-js/queue
A performant queue implementation in javascript.
Contents
Install
npm install --save @datastructures-js/queuerequire
const { Queue } = require('@datastructures-js/queue');import
import { Queue } from '@datastructures-js/queue';API
constructor
JS
// empty queue
const queue = new Queue();
// from an array
const queue = new Queue([1, 2, 3]);TS
// empty queue
const queue = new Queue<number>();
// from an array
const queue = new Queue<number>([1, 2, 3]);Queue.fromArray
JS
// empty queue
const queue = Queue.fromArray([]);
// with elements
const list = [10, 3, 8, 40, 1];
const queue = Queue.fromArray(list);
// If the list should not be mutated, use a copy of it.
const queue = Queue.fromArray(list.slice());TS
// empty queue
const queue = Queue.fromArray<number>([]);
// with elements
const list = [10, 3, 8, 40, 1];
const queue = Queue.fromArray<number>(list);enqueue (push)
adds an element to the back of the queue.
queue.enqueue(10).enqueue(20); // or queue.push(123)front
peeks on the front element of the queue.
console.log(queue.front()); // 10back
peeks on the back element in the queue.
console.log(queue.back()); // 20dequeue (pop)
removes and returns the front element of the queue in O(1) runtime.
console.log(queue.dequeue()); // 10 // or queue.pop()
console.log(queue.front()); // 20Dequeuing all elements takes O(n) instead of O(n2) when using shift/unshift with arrays.
Explanation by @alexypdu:
Internally, when half the elements have been dequeued, we will resize the dynamic array using Array.slice() which runs in $O(n)$. Since dequeuing all $n$ elements will resize the array $\log_2n$ times, the complexity is $$1 + 2 + 4 + \cdots + 2^{\log_2 n - 1} = 2 ^ {(\log_2 n - 1) + 1} - 1 = n - 1 = O(n)$$ Hence the overall complexity of dequeuing all elements is $O(n + n) = O(n)$, and the amortized complexity of dequeue() is thus $O(1)$.
benchmark:
dequeuing 1 million elements in Node v14
| Queue.dequeue | Array.shift |
| ~27 ms | ~4 mins 31 secs |
isEmpty
checks if the queue is empty.
console.log(queue.isEmpty()); // falsesize
returns the number of elements in the queue.
console.log(queue.size()); // 1clone
creates a shallow copy of the queue.
const queue = Queue.fromArray([{ id: 2 }, { id: 4 } , { id: 8 }]);
const clone = queue.clone();
clone.dequeue();
console.log(queue.front()); // { id: 2 }
console.log(clone.front()); // { id: 4 }toArray
returns a copy of the remaining elements as an array.
queue.enqueue(4).enqueue(2);
console.log(queue.toArray()); // [20, 4, 2]clear
clears all elements from the queue.
queue.clear();
queue.size(); // 0Build
grunt buildLicense
The MIT License. Full License is here