An attempt at an immutable Queue

Eric said he will write about an immutable queue implementation. I really like the way the immutable stack turned out, essentially using references between Stack<> objects to implement a linked list, but I couldn't figure out a similarly elegant way to do the same thing for Queue. Maybe people who are more clever will come up with something better, but I just had each Queue<> object contain a list of references to elements.

I wrote once in C# 2.0, using an array to store the elements. The code would be cleaner if I used a List<>, but then I would be harder to verify immutability.

class Queue<T> : IQueue<T>

{

public static readonly IQueue<T> Empty = new Queue<T>(new T[] { });

 

readonly T[] elements;

 

Queue(T[] elements)

{

this.elements = elements;

}

public bool IsEmpty { get { return this.elements.Length == 0; } }

public T Peek() { return this.elements[0]; }

public IQueue<T> Remove()

{

T[] newElements = new T[this.elements.Length - 1];

Array.Copy(this.elements, 1, newElements, 0, newElements.Length);

return new Queue<T>(newElements);

}

public IQueue<T> Add(T value)

{

T[] newElements = new T[this.elements.Length + 1];

Array.Copy(this.elements, newElements, this.elements.Length);

newElements[newElements.Length - 1] = value;

return new Queue<T>(newElements);

}

public IEnumerator<T> GetEnumerator()

{

for (IQueue<T> Queue = this; !Queue.IsEmpty; Queue = Queue.Remove())

yield return Queue.Peek();

}

System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() { return this.GetEnumerator(); }

}

Then I rewrote using C# 3.0, taking advantage of the rich support for sequences. The code is much simpler, but I think that's basically because the IEnumerable extension methods do pretty much what I did in my first attempt. But I'll take it. J

class Queue2<T> : IQueue<T>

{

readonly IEnumerable<T> elements;

 

public static IQueue<T> Empty = new Queue2<T>(new T[] { });

 

Queue2(IEnumerable<T> elements)

{

this.elements = elements;

}

 

IQueue<T> IQueue<T>.Add(T value)

{

return new Queue2<T>(this.elements.Concat(new T[] { value }));

}

 

IQueue<T> IQueue<T>.Remove()

{

return new Queue2<T>(this.elements.Skip(1));

}

 

T IQueue<T>.Peek()

{

return this.elements.First();

}

 

bool IQueue<T>.IsEmpty

{

get

{

return this.elements.Count() == 0;

}

}

 

IEnumerator<T> IEnumerable<T>.GetEnumerator()

{

return this.elements.GetEnumerator();

}

 

System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()

{

return this.elements.GetEnumerator();

}

}