Huge News!Announcing our $40M Series B led by Abstract Ventures.Learn More
Socket
Sign inDemoInstall
Socket

@datastructures-js/queue

Package Overview
Dependencies
Maintainers
1
Versions
23
Alerts
File Explorer

Advanced tools

Socket logo

Install Socket

Detect and block malicious and high-risk dependencies

Install

@datastructures-js/queue

a performant queue implementation in javascript

  • 4.2.3
  • latest
  • Source
  • npm
  • Socket score

Version published
Weekly downloads
18K
decreased by-7.33%
Maintainers
1
Weekly downloads
 
Created
Source

@datastructures-js/queue

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

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()); // 10

back

peeks on the back element in the queue.

console.log(queue.back()); // 20

dequeue (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()); // 20

Dequeuing 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.dequeueArray.shift
~27 ms~4 mins 31 secs

isEmpty

checks if the queue is empty.

console.log(queue.isEmpty()); // false

size

returns the number of elements in the queue.

console.log(queue.size()); // 1

clone

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(); // 0

Build

grunt build

License

The MIT License. Full License is here

Keywords

FAQs

Package last updated on 05 Sep 2022

Did you know?

Socket

Socket for GitHub automatically highlights issues in each pull request and monitors the health of all your open source dependencies. Discover the contents of your packages and block harmful activity before you install or update your dependencies.

Install

Related posts

SocketSocket SOC 2 Logo

Product

  • Package Alerts
  • Integrations
  • Docs
  • Pricing
  • FAQ
  • Roadmap
  • Changelog

Packages

npm

Stay in touch

Get open source security insights delivered straight into your inbox.


  • Terms
  • Privacy
  • Security

Made with ⚡️ by Socket Inc