Mdthbs

I tried to implement a cyclic Queue using an array, as a task from a coding interview.

Please comment about style, as well as any edge cases I may have missed.

using System;

using Microsoft.VisualStudio.TestTools.UnitTesting;



namespace CirucularArray

{

    [TestClass]

    public class CyclicQueueUsingArray

    {

        [TestMethod]

        public void QueueTest()

        {

            CyclicQueue Q = new CyclicQueue(5);

            Q.Enqueue(1);

            Assert.AreEqual(1, Q.Front);

            Q.Enqueue(2);

            Assert.AreEqual(1, Q.Front);

            Assert.AreEqual(2, Q.Rear);

            Q.Enqueue(3);

            Assert.AreEqual(1, Q.Front);

            Assert.AreEqual(3, Q.Rear);



            Assert.AreEqual(1, Q.Dequeue());

            Assert.AreEqual(2, Q.Front);

            Assert.AreEqual(3, Q.Rear);



            Assert.AreEqual(2, Q.Dequeue());

            Assert.AreEqual(3, Q.Front);

            Assert.AreEqual(3, Q.Rear);



            Assert.AreEqual(3, Q.Dequeue());

        }



        [TestMethod]

        public void QueueOverflowTest()

        {

            CyclicQueue Q = new CyclicQueue(5);

            Q.Enqueue(1);

            Q.Enqueue(2);

            Q.Enqueue(3);

            Q.Enqueue(4);

            Q.Enqueue(5);

            Assert.AreEqual(1, Q.Dequeue());

            Q.Enqueue(6);

            Assert.AreEqual(2, Q.Front);

            Assert.AreEqual(6, Q.Rear);

        }

    }



    public class CyclicQueue

    {

        public int[] _buffer;

        private int _start;

        private int _end;

        private int _size;

        private int _maxSize;

        public CyclicQueue(int maxSize)

        {

            _maxSize = maxSize;

            _buffer = new int[_maxSize];

            _start = 0;

            _end = 0;

        }

        public void Enqueue(int newValue)

        {

            if (_size == _maxSize)

            {

                throw new OutOfMemoryException("Queue at full capacity");

            }

            if (_size > 0)

            {

                _end = (_end + 1) % _maxSize;

            }

            _buffer[_end] = newValue;

            _size++;

        }



        public int Dequeue()

        {

            if (_size == 0)

            {

                throw new IndexOutOfRangeException("Queue is empty");

            }



            int result = _buffer[_start];

            _size--;



            _start = (_start + 1) % _maxSize;

            return result;

        }

        public int Front

        {

            get { return _buffer[_start]; }

        }



        public int Rear

        {

            get { return _buffer[_end]; }

        }

    }

}

Yay exceptions!

Though it isn't reservered for execution-ending errors, I would avoid throwing an OutOfMemoryException, because usually it signals something very inconvient indeed. IndexOutOfRangeException also seems inappropriate: I would probably use InvalidOperationException in both Enqueue and Dequeue.

The constructor could do with a check to ensure maxSize is positive, so that it doesn't throw with a cryptic error.

Front and End don't throw on an empty buffer, and probably should.

API and Encapsulation

There is no reason this class couldn't be generic: I would make it so. Indeed, because it stores ints at the moment, it would not be clear to a consumer looking at the members that Front and Rear return elements rather than indexes.

I'd expect a Count => _size property, so that the Queue can be used for the sort of things Queues tend to be used (e.g. in your previous questions).

Do you have a particular use-case in mind for exposing _buffer? What good can come of this? There is no information made available as to the content of the buffer, so it can't be used for anything because nothing except the CyclicQueue knows how to use it. I would strongly suggest making this private (also, if it is public, it should ideally following the ProperCamelCase naming conventions like your other public members).

Since this is a non-resizing queue, the MaxSize probably ought to be public information. I'd also consider making it MaxSize => _buffer.Length to reduce redundancy. You could also make _buffer readonly to signal it's not meant to be changed to the maintainers.

Correctness

I'm not sure the _size > 0 check in Enqueue works. Consider a sequence of Enqueue, (Dequeue, Enqueue)*n on a newly created CyclicQueue: this will leave _end = 0 while _start is incremented. I think this can be resolved by setting _end = _maxSize - 1 in the constructor and removing the check.

Misc/Boring Stuff

• You could do with a little more white-space between things... at the very least, be consistent with your between-member spacing.




• You could do with tests which test the exceptions (i.e. checking it throws if you try to enqueue/dequeue too many things.




• As always, inline-documentation would be appreciated. This should describe the non-resizing nature of the queue, when it throws exceptions, and resolve the confusion concerning whether Front is an index or element.