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 ).

• brainydexter: I will work on your suggestions. This problem was more about me getting circular queues implemented. But, I'll definitely try to integrate the recommendations.
• brainydexter: Why is it not thread-safe ? How can I make it thread safe ?
• Steven Jeuris: @brainydexter: That's a whole different subject. I'm not saying you should make it thread safe. I'm only saying you should be aware it's not. E.g. comment it in the summary of the class. The caller can also do thread safe calls to the queue in a multithreaded environment. If you don't need it, don't worry about it for now.

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.

• Steven Jeuris: Very true. I'm guessing it was just an exercise. :) Perhaps one advantage is, when adjusting his code, it could work on any existing array without having to copy all elements to the LinkedList. :) There might also be a small performance gain.
• brainydexter: @Steven Jeuris: What was that bit about copying all the elements, if I were to use a linked list ? (Even if Linked list is used, I don't think elements would be copied. Please correct me, if am wrong).
• brainydexter: @Snowbear: One of the requirements was to have a maximum capacity and array felt like a natural choice to me, since array is usually a fixed size data structure. Also, I could not use any external class, so if I were to use either Linkedlist or a Queue, I'd have to write my own implementation. I'd still be interested to learn why would you use linkedlists over arrays ?
• Steven Jeuris: @brianydexter: I mean that your class can easily be adjusted to work on an existing array. (if you ever want to do that anyway ...) This class can too, but then you will have to add all items from the array into the linked list, and the original array won't change along. Just mentioning it, probably not important. :)
• brainydexter: Also, shouldn't queSize condition be: quesize <= 0 :: throw exception ?

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.

• Steven Jeuris: I was doubting to mention the modulo. The function already describes what it does, and somehow, when you use it often, it is readable. Never thought about performance however. :O Would be interesting to do some benchmarks for that. Not that performance would be an issue :) just out of curiosity.
• Dyppl: Modulo is fine.. It's more natural in these cases, everyone uses it to deal with overflowing/circularity, so it's pretty natural for any programmer who reads it