Circular Bounded Queue using C#

Question

As an exercise, I have implemented a circular bounded queue using arrays as the base data structure. I'd appreciate it if someone can review it for me.

    class BoundedQueue<T> {

    T[] que;
    int head;       // remove from head
    int tail;       // insert at tail


    public BoundedQueue(int quesize)
    {
        head = tail = -1;
        que = new T[quesize];
    }

    public void enqueue(T elem)  // if next index to tail == head => Q is FULL
    {
        int newIndex = nextIndex(tail);
        if ( newIndex == head)
            throw new BoundedQueueException(Full);

        tail = newIndex;
        que[newIndex] = elem;
        if (head == -1)
            head = 0;
    }

    public T dequeue()  // After removing from head, if that was the only element in Q
    // Mark Q to be empty by setting head and tail to -1
    {
        if (head == -1)
            throw new BoundedQueueException(Empty);

        T elem = que[head];
        que[head] = default(T);

        if (head == tail)
        {
            head = tail = -1;
        }
        else
        {
            head = nextIndex(head);
        }

        return elem;
    }

    private int nextIndex(int index)
    {
        return (index + 1) % que.Length;
    }

}

Answer 1

1. Exception handling should be added to the constructor, handling a negative quesize. Or take a look at Code Contracts.
2. Instead of initializing head and tail to -1, you could use nullable ints, and adjust your logic so it doesn't rely on the magic number -1.
3. Implement some missing features. (might have been left out intentionally): implement ICollection and IEnumerable, isFull().
4. A minor point would be naming conventions. In C# method names normally start with a capital letter.
5. Be aware that this is not a thread safe class.
6. Add some comments, this code isn't that self-documenting. Or, where possible, make it self-documenting, e.g. if ( head == tail ) could be if ( Count == 0 ).

Answer 2

It's not that clear why do you want to implement such data structure as circular queue. Externally the only it's difference from regular queue is that it has maximum capacity. But if the only point to implement it was to have a max capacity then I would use LinkedList or even regular Queue internally. Code will be more readable if you will get rid of these index games. Sample with LinkedList:

class BoundedQueue<T> {

    private readonly LinkedList<T> _internalList = new LinkedList<T>();
    private readonly int _maxQueueSize;

    public BoundedQueue(int queueSize)
    {
        if (queueSize < 0) throw new ArgumentException("queueSize");
        _maxQueueSize = queueSize;
    }

    public void Enqueue(T elem)
    {
        if (_internalList.Count == _maxQueueSize)
            throw new BoundedQueueException(Full);
        _internalList.AddLast(elem);
    }

    public T dequeue()
    {
        if (_internalList.Count == 0)
            throw new BoundedQueueException(Empty);

        T elem = _internalList.First.Value;
        _internalList.RemoveFirst();
        return elem;
    }
}

P.S.: Also consider declaring fields with readonly keyword.

Answer 3

1. Use XML-doc instead of comments when describing public method or properties. Especially for a class that is intended to be used by many people with different purposes (generic collections fall into that category)
2. Naming. Methods really should be CamelCase and you usually want to use verbs, like GetNextIndex
3. I would add a Count method or property for external and internal use (it's useful for the caller and it allows to rewrite some parts of the code more semantic way)

Answer 4

A few minor comments.

1. C# typically uses CamelCase for method names.
2. A Peek() method or a Count property could be useful.
3. I would prefer to use an if statement in the NextIndex method instead of the modulus operator.

    index++
    if (index >= que.Length)
        index = 0;
    return index;

I am not sure which would perform faster, I suspect the if, but I think that the if more clearly communicates what you are trying to do.