10
\$\begingroup\$

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;
    }

}
\$\endgroup\$
12
\$\begingroup\$
  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 ).
\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – brainydexter Mar 10 '11 at 1:09
  • \$\begingroup\$ Why is it not thread-safe ? How can I make it thread safe ? \$\endgroup\$ – brainydexter Mar 10 '11 at 1:10
  • \$\begingroup\$ @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. \$\endgroup\$ – Steven Jeuris Mar 10 '11 at 1:15
4
\$\begingroup\$

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;
        _internalList.RemoveFirst();
        return elem;
    }
}

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

\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – Steven Jeuris Mar 10 '11 at 12:41
  • \$\begingroup\$ @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). \$\endgroup\$ – brainydexter Mar 10 '11 at 15:56
  • \$\begingroup\$ @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 ? \$\endgroup\$ – brainydexter Mar 10 '11 at 16:00
  • \$\begingroup\$ @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. :) \$\endgroup\$ – Steven Jeuris Mar 10 '11 at 16:02
  • 1
    \$\begingroup\$ Also, shouldn't queSize condition be: quesize <= 0 :: throw exception ? \$\endgroup\$ – brainydexter Mar 10 '11 at 16:03
3
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – Steven Jeuris Mar 10 '11 at 0:50
  • 2
    \$\begingroup\$ 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 \$\endgroup\$ – Dyppl Mar 10 '11 at 5:05
3
\$\begingroup\$
  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)
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.