JavaScript Queues

Queues can be implemented in JavaScript using either the push and shift methods or unshift and pop methods of the array object. Although this is a simple way to implement queues, it is very inefficient for large queues — because the methods operate on arrays, the shift and unshift methods move every element in the array each time they are called.

In most programming languages queues are implemented as linked lists, allowing elements to be enqueued or dequeued in constant time. However, JavaScript's dynamically resizable arrays allow for an implementation that is faster in major web browsers.

Using the Queue object

To use the Queue object, download one of the files listed above and upload it to your website. The ‘CPP’ files are identical except that the queue functions are named in the same way as in the C++ standard library. Link to it from your page with code such as:

<script type="text/javascript" src="Queue.js"></script>

A queue is created by calling the Queue function as a constructor:

var queue = new Queue();

The Queue object supports five functions:

getSize()

size() [CPP version]

Returns the size of this Queue. The size of a Queue is equal to the number of elements that have been enqueued minus the number of elements that have been dequeued.

isEmpty()

empty() [CPP version]

Returns true if this Queue is empty, and false otherwise. A Queue is empty if the number of elements that have been enqueued equals the number of elements that have been dequeued.

enqueue(element)

push(element) [CPP version]

Enqueues the specified element in this Queue. The parameter is:

• element — the element to enqueue

dequeue()

pop() [CPP version]

Dequeues an element from this Queue. The oldest element in this Queue is removed and returned. If this Queue is empty then undefined is returned.

getOldestElement()

front() [CPP version]

Returns the oldest element in this Queue. If this Queue is empty then undefined is returned. This function returns the same value as the dequeue function, but does not remove the returned element from this Queue.

The Delayed Shift Queue

The Queue object is implemented using a technique called the Delayed Shift Queue (DSQ). The DSQ dramatically increases the speed of queue operations at the expense of potentially using slightly more memory than a basic queue.

The key concept in the DSQ is that it is not necessary to move the elements in an array every time an element is dequeued. Instead, the DSQ only moves elements back when the space at the front of the array is as least as long as the queue itself, so that n items are moved only after n dequeuing operations have taken place without moving. This gives an amortised (that is, average) constant time dequeue operation, with the trade-off that the array may grow to twice the size of the queue it contains.

Delayed Shift Queue Performance

To compare different queue implementations, queues of each type repeatedly had n elements enqueued and then dequeued, where n was a power of two, and the ratio of the running times was calculated. You can benchmark the queue performance in your own browser by clicking the ‘Perform benchmarks’ button below. For each value of n, each queue type is tested for one second, and the average time to enqueue and dequeue an element is displayed in the table. Testing of a queue stops when it takes more than one second to enqueue and then dequeue n elements. A 0.1 second delay is inserted between tests in order to stop your browser from becoming unresponsive.

The following browsers were compared, on a system with a 3GHz Pentium 4 and 512MB of RAM:

• Opera 8.54.7730
• Mozilla Firefox 1.5.0.8
• Interner Explorer 7.0.5730.11

The graph below compares the Delayed Shift Queue to a queue implementated using the built-in push and shift methods of the array object. Opera was the fastest browser, and showed the least benefit from the DSQ, which only became faster when the queue reached a length of approximately 50 elements. Mozilla Firefox and Internet Explorer showed gains with queues as short as 16 and 8 elements respectively. All browsers showed massive improvements on large queues.

The comparison of the Delayed Shift Queue and linked list queue was more complex. Once again Opera was the fastest browser, which performed better with the linked list queue until the queue size was very large at which point performace of the linked list queue suddenly collapsed. A similar collapse in linked list queue speed at large queue sizes occured in Internet Explorer, but in that browser the DSQ was always faster. The behaviour of the two queue types was more consistent in Mozilla Firefox, in which the DSQ was faster by a fairly constant factor.