Is this queue properly implemented?

Question

I tried to implement a queue which stores it's elements in a resizing array. Seems to work fine. Can you tell me if i did something wrong?

public class Queue<T>
{
    private T[] array;

    public Queue()
    {
        array = new T[16];
    }

    private void Enqueue(T item)
    {
        if(Count == array.Length/2)
            Grow();

        array[Count++] = item;
    }

    public void Grow()
    {
        var temp = array;
        array = new T[array.Length * 2];
        Array.Copy(temp,startingPos,array,0,Count);
        startingPos = 0;
    }

    public void Shrink()
    {
        var temp = array;
        array = new T[array.Length / 2];
        Array.Copy(temp,startingPos,array,0,Count);
        startingPos = 0;
    }

    public T Dequeue()
    {
        if(Count == array.Length/4)
            Shrink();

        var item = array[startingPos];
        array[startingPos++] = default(T);
        Count--;
        return item;
    }

    int startingPos = 0;

    public int Count {get;set;}
}

Answer 1

This is a partial review about some things I saw reading through your code fast.

The setter of your Count property shouldn't be public, because I could set it to one million when there's only one element in the queue.

You should specify the accessibility modifier for your member field, I guess it is private int startingPos, and I think you should put it at the top of your class, it is easier to read this way.

I don't think you should expose methods Shrink and Grow as they aren't part of a Queue but more of its implementation. Exposing these methods imply that you use an Array behind and the users of your class shouldn't know about this.

Also, in your Enqueue method, you grow your array every time your array is half filled, it is overkill. You should expand it only when the current array is full, otherwise you will always have half your array wasted.

Answer 2

Here's a bug:

var queue = new Queue<int>();
queue.Enqueue(1);
Console.WriteLine(queue.Dequeue());
Console.WriteLine(queue.Dequeue());

This prints 1 0, but the second call to Dequeue should throw an exception, since the queue is empty. I would follow System.Collections.Generic.Queue<T> and throw an InvalidOperationException.

If we call Dequeue another 15 times, we do get an exception, but it's an IndexOutOfRangeException.

This bug also stops us from enqueueing: the last line here will throw an IndexOutOfRangeException, since Count is -1.

var queue = new Queue<int>();
queue.Enqueue(1);
queue.Dequeue();
queue.Dequeue();
queue.Enqueue(1);

---

Here's another bug:

var queue = new Queue<int>();
queue.Enqueue(1);
queue.Dequeue();
queue.Enqueue(2);
queue.Enqueue(3);
Console.WriteLine(queue.Dequeue());

This prints 3, when it should print 2.

---

Elements can get lost during a resize. Consider this client program

var queue = new Queue<int>();
queue.Enqueue(1);
queue.Dequeue();
for (int i = 2; i <= 10; i++)
{
    queue.Enqueue(i);
}

array before the resize:

2, 3, 4, 5, 6, 7, 8, 9, 0, 0, 0, 0, 0, 0, 0, 0

array after the resize:

3, 4, 5, 6, 7, 8, 9, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
^
missing 2

array are enqueueing 10:

3, 4, 5, 6, 7, 8, 9, 0, 10, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
                     ^
                     gap in the queue

Answer 3

When you write a class or an API in general you have to ask yourself three simple questions.

1. What are the functionalities expected by the users of this class
2. What are the things that users shouldn't care about
3. What shall I hide so users don't break it.

Answers:

1. The first thing you expect from a queue is to be able to Enqueue, and for some reason you are hiding this function by declaring it private where this should be public.

2. Do I really need to care about growing and shrinking the array in this queue, I am not supposed to know that they exist, so these should be declared private.

   private Grow()
   { ..
   }
   
   private Shrink()
   { ..
   }
   

3. A user of this class shouldn't be able to set the count of elements in the queue to the value they want (-1 for instance), can you imagine a queue that is in debt? and therefore Count set should be private.

   public int Count { get; private set;}
   

Answer 4

I would avoid code like

if(Count == array.Length/2)
if(Count == array.Length/4)

Something more like

if ( startingPos + Count >= array.Length )
if ( Count <= array.Length/4 )

is more robust. For example, what if you change Enqueue to take a collection of items? Note that you want to compare the sum of startingPos and Count to the array length. Otherwise, you may overrun your array even though it doesn't have much in it.

Also, you may not always want to Grow when you hit the startingPos + Count issue. Some of the time, you may want to just reset the array so that startingPos is 0 again. Alternately, you could make the data circular (when you hit the end of the array, start putting things at the beginning again), but the logic for that is trickier. Unless you are really memory or time short, the dumber solution is better for robustness reasons.

If you implement a Reset function, you may want to refactor Grow and Shrink so that all three call a function that handles the array initialization and copying. Or just replace them with something like

    private void Resize(int size)
    {
        var temp = array;
        array = new T[size];
        Array.Copy(temp, startingPos, array, 0, Count);
        startingPos = 0;
    }

Maybe I'm missing something, but shouldn't

array[Count++] = item;

be

array[startingPos + Count++] = item;

It seems to me that the original code will only work if you do all your Enqueue calls before doing your Dequeue calls. You can reset this by doing a Shrink or Grow, but there still seems to be a problem if you do an Enqueue after a Dequeue without an intervening size change.

Why is Enqueue private? I'd expect two public methods: Enqueue and Dequeue. The constructor and the Count get property should also be public (as others have noted, set should be private). Everything else can be private.

Note: I didn't try to be comprehensive here. These comments are in addition to those in the other answers, not replacements for them. If someone wants a comprehensive answer, feel free to copy my contributions.

Answer 5

Depending on how you're using this queue thread safety may be an issue (for instance if used in a web application as a shared queue). Two threads could definitely dequeue the same item looking at your code, which would be a problem. You'll want to use a lock.

As for the use of an array, the concept of growing is done already in List<>, so there's no reason to do it yourself outside of homework. As someone else said there's also a built-in Queue class which is likely to be more reliable than anything you're writing (unless it needs to have specific functionality). Even then Queue isn't a sealed class so you could add to it if you really need to.

Edit: You can also read about the ins-and-outs of shrinking array problems here.