@datastructures-js/queue

A performant queue implementation in javascript.

Showing:

Popularity

Downloads/wk

496

GitHub Stars

22

Maintenance

Last Commit

3mos ago

Contributors

0

Package

Dependencies

0

License

MIT

Type Definitions

Tree-Shakeable

No?

Categories

Readme

@datastructures-js/queue

build:? npm npm npm

A performant queue implementation in javascript.

Contents

Install

npm install --save @datastructures-js/queue

require

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(elements)

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(element)

adds an element at the back of the queue.

params return runtime
element: T Queue<T> O(1)
queue.enqueue(10).enqueue(20);

.front()

peeks on the front element of the queue.

return runtime
T O(1)
console.log(queue.front()); // 10

.back()

peeks on the back element in the queue.

return runtime
T O(1)
console.log(queue.back()); // 20

.dequeue()

dequeue the front element in the queue. It does not use .shift() to dequeue the element. Instead, it uses a pointer to get the front element and only remove elements when reaching half size of the queue.

return runtime
T O(n*log(n))
console.log(queue.dequeue()); // 10
console.log(queue.front()); // 20

Dequeuing all elements takes O(n*log(n)) instead of O(n2) when using shift().

benchmark:

dequeuing 1 million elements in Node v12

.dequeue().shift()
~ 40 ms~ 3 minutes

.isEmpty()

checks if the queue is empty.

return runtime
boolean O(1)
console.log(queue.isEmpty()); // false

.size()

returns the number of elements in the queue.

return runtime
number O(1)
console.log(queue.size()); // 1

.clone()

creates a shallow copy of the queue.

return runtime
Queue<T> O(n)
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.

return runtime
T[] O(n)
queue.enqueue(4).enqueue(2);
console.log(queue.toArray()); // [20, 4, 2]

.clear()

clears all elements from the queue.

runtime
O(1)
queue.clear();
queue.size(); // 0

Build

grunt build

License

The MIT License. Full License is here

Rate & Review

Great Documentation0
Easy to Use0
Performant0
Highly Customizable0
Bleeding Edge0
Responsive Maintainers0
Poor Documentation0
Hard to Use0
Slow0
Buggy0
Abandoned0
Unwelcoming Community0
100