JavaScript queues

Queues can be implemented in JavaScript using arrays, by using the push or unshift functions to add items to one end of the array, and the shift or pop functions to remove them from the other. This method, while simple, is inefficient for large queues as the shift and unshift functions move every item in the array.
Queue.js is a simple and efficient queue implementation for JavaScript whose dequeue function runs in amortised constant time. As a result, for larger queues it can be significantly faster than using arrays.

Creating and using queues

 After creating a queue, the enqueue and dequeue functions can be used to add items to the end of the queue and remove them from the front:

// create a new queue
var queue = new Queue();

// enqueue an item
queue.enqueue('item');

// dequeue an item
var item = queue.dequeue();

The peek function can be used to inspect the item at the front of the queue without dequeuing it:

// get the item at the front of the queue
var item = queue.peek(); 

Both the dequeue and peek functions return the value ‘undefined’ if the queue is empty. The getLength and isEmpty functions can be used to determine the the current state of the queue:

// determine the number of items in the queue
var length = queue.getLength();

// determine whether the queue is empty
var isEmpty = queue.isEmpty();

Performance benchmarks

The following benchmark compares simple array-based queues with the Queue function by creating queues of various lengths and repeatedly enqueueing and dequeueing items. The results are given in terms of queue operations per millisecond, where a queue operation consists of enqueueing and dequeueing an item. Click on the ‘Run benchmark’ button to run the benchmarks in your browser — the results will appear in the table as the benchmark progresses.

Implementation

Queue.js is implemented using an array, but avoids the expensive shift operation. Instead of shifting an item from the front of the array when it is dequeued, Queue.js increments an internal offset to indicate that there is space at the front of the array. When this space takes up half the array, Queue.js uses the slice function to remove it. Because n items are moved only after n dequeuing operations have occurred, the dequeue function runs in amortised constant time.

Limitations

Queue.js aims for speed at the expensive of increased memory consumption, reflecting the fact that for the current generation of JavaScript applications speed is a greater issue than memory consumption. When the dequeue function increases the internal offset, as described under Implementation, it leaves a reference to the item that was previously at the front of the queue. Due to these references, the JavaScript garbage collector cannot free the referred object until a call to the dequeue function removes the space from the front of the queue. This issue can be avoided by modifying the dequeue function to set the former item to null; this does however reduce the speed of the function.

Source URL : http://code.stephenmorley.org/javascript/queues/