Immutable Queue

list.js

exports.list = list;
exports.of = listOf;
exports.empty = empty;
exports.cons = cons;
exports.head = head;
exports.tail = tail;
exports.reverse = reverse;
exports.foldl = foldl;
exports.foldr = foldr;
exports.concat = concat;
exports.toString = toString;

var EMPTY = new List(void 0, void 0);
EMPTY.tail = EMPTY;

function List(head, tail) {
	this.head = head;
	this.tail = tail;
}

function list(head, tail) {
	return new List(head, tail);
}

function listOf(x) {
	return cons(x, EMPTY);
}

function empty() {
	return EMPTY;
}

function cons(x, list) {
	return new List(x, list);
}

function head(list) {
	return list.head;
}

function tail(list) {
	return list.tail;
}

function reverse(list) {
	return rev(list, EMPTY);
}

function rev(l, r) {
	return l === EMPTY ? r
		 : rev(l.tail, cons(l.head, r))
}

function concat(l, r) {
	return l === EMPTY ? r
		 : r === EMPTY ? l
		 : foldr(consFlip, r, l);
}

function consFlip(r, x) {
	return cons(x, r);
}

function foldl(f, z, list) {
	return list === EMPTY ? z
		 : foldl(f, f(z, list.head), list.tail);
}

function foldr(f, z, list) {
	return list === EMPTY ? z
		 : f(foldr(f, z, list.tail), list.head);
}

function toString(list) {
	return list === EMPTY ? '[]'
		 : foldl(appendStringItem, String(list.head), list.tail);
}

function appendStringItem(s, x) {
	return s + ':' + x;
}

queue.js

var list = require('./list');

exports.queue = queue;
exports.empty = empty;
exports.head = head;
exports.tail = tail;
exports.push = push;
exports.isEmpty = isEmpty;
exports.length = length;

function Queue(front, frontLen, back, backLen) {
	this.front = front;
	this.frontLen = frontLen;
	this.back = back;
	this.backLen = backLen;
}

function empty() {
	return new Queue(list.empty(), 0, list.empty(), 0);
}

function isEmpty(q) {
	return q.frontLen === 0 && q.backLen === 0;
}

function length(q) {
	return q.frontLen + q.backLen;
}

function queue(front, frontLen, back, backLen) {
	if(frontLen === 0) {
		return new Queue(list.reverse(back), backLen, list.empty(), 0);
	}
	return new Queue(front, frontLen, back, backLen);
}

function head(q) {
	return list.head(q.front);
}

function push(x, q) {
	return queue(q.front, q.frontLen, list.cons(x, q.back), q.backLen + 1);
}

function tail(q) {
	return queue(list.tail(q.front), q.frontLen - 1, q.back, q.backLen);
}

function toString(q) {
	return list.toString(list.concat(q.front, list.reverse(q.back)));
}