A Functional Queue in JavaScript

It's been over a year since I've posted here, but I've been busy delving into Android and Ruby on Rails among other things. To get back into blogging (hopefully more regularly...we'll see), I thought I'd share an interesting JavaScript exercise I was asked to complete as part of a job interview recently.

The task was to build a functional queue in JavaScript.  A functional queue is a queue (first in, first out) which is implemented with no side-effects.  For instance, a function to enqueue a value onto an existing queue will return a new object which represents the larger queue.  The original (smaller) queue is still available.

In order to implement a functional queue, we need to be able to do a few things that are not immediately obvious in Javascript:

1. Create a new instance of the array of queue items when an item is enqueued/dequeued
2. Overload the class constructor so it can be created with an empty array (new queue) or an existing array (result of a enqueue/dequeue operation
3. Return both the dequeued item and a new queue as a result of a dequeue operation

To return a new instance of the array of queue items, we can leverage the array.slice() method, which selects part of an array and returns a new array.  The trick here is to pass an index of zero to the slice method to get a new array instance and then use array.push() to enqueue or array.shift() to dequeue.

To overload the class constructor, we can use the arguments array to pass an existing array and create a new one if none is passed.

Finally, to return both the dequeued item and a new queue as a single result, we can use an object literal.

The finished product looks like this:

var Queue = function() {
	var items = arguments.length > 0 ? arguments[0] : new Array();

	return {
		length: function() {
			return items.length;
		},
		isEmpty: function() {
			return this.length() == 0;
		},
		enqueue: function(item) {
			var newItems = items.slice(0);
			newItems.push(item);
			return new Queue(newItems);
		},
		dequeue: function() {
			var newItems = items.slice(0);
			var item = newItems.shift();
			return {
				queue: new Queue(newItems),
				value: item
			};
		},
		head: function() {
			return items[0];
		}
	};
}