HiveBrain v1.2.0
Get Started
← Back to all entries
patterncsharpModerate

Is this queue properly implemented?

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
thisproperlyqueueimplemented

Problem

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

Solution

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.

Context

StackExchange Code Review Q#64904, answer score: 13

Revisions (0)

No revisions yet.