queue

queue

Two-array implementation of queue (.push, .shift) for JavaScript

Originally created as a simple fast queue implementation around 2010 in one of @creationix repos (nStore, maybe) where implementation sucked because of .shift() being slow.

This repo only contains the Queue class itself, written as traditional (new-able) JavaScript class, and fixing .push to be able to take variable number of arguments.

How to install

The Queue class is available in both npm and bower, usable as either node.js module, AMD module or global in the browser. You can install it with either of:

npm install hqueue

bower install hqueue

The idea

The idea behind this queue is to avoid shift call. This is accomplished by increasing the read index in an array and returning the element at that index. If using single array, this would fill the memory with ever-growing array. So two arrays are used - the read array is only used to read the front element by increasing the read index as told above. The second array is used to append new elements at the back. When the read array is exhausted, the write array becomes the read array, and empty write array is used to continue writing.

As implementation of array .push tends to be O(n) in average, and so should be the Queue. Moveover, exhausted read array is just shortened (.length = 0) and reused as write array, to allow to reuse already allocated capacity to make appending O(1) most of the times.

API

Reuses small subset of Array API so as to allow direct replacement of an array:

• .shift() remove and return front element or undefined
• .push(...args) append ...args at the back of the queue
• .length return number of elements in the queue