5
\$\begingroup\$

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;}
}
\$\endgroup\$
  • 5
    \$\begingroup\$ First question would be: Why? System.Collections.Generic.Queue does this. \$\endgroup\$ – Peter Ritchie Oct 6 '14 at 17:16
  • 1
    \$\begingroup\$ Agreed, an explanation of your goals for rolling out your own instead of using the built-in functionality will help with review advice. Is it for learning, existing one is too slow, homework, etc...? What makes you think that perhaps you implemented something wrong? \$\endgroup\$ – xDaevax Oct 6 '14 at 17:17
  • 1
    \$\begingroup\$ And your growing/shrinking is strange, this should be circular. You Queue will grow beyond limits in producer-consumer balance. \$\endgroup\$ – user52292 Oct 6 '14 at 17:21
  • 1
    \$\begingroup\$ @PeterRitchie for educational purposes. \$\endgroup\$ – Raz Megrelidze Oct 6 '14 at 19:35
  • 1
    \$\begingroup\$ You can find a good reference implementation of a queue backed by a resizing array here (in Java, easily translatable to C#). \$\endgroup\$ – mjolka Oct 6 '14 at 21:59
13
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Yeah i somehow managed to miss that. But are there any functional flaws? \$\endgroup\$ – Raz Megrelidze Oct 6 '14 at 17:26
  • \$\begingroup\$ So i have to grow every time "Count == array.Length". Yeah thanks for that. \$\endgroup\$ – Raz Megrelidze Oct 6 '14 at 17:34
  • \$\begingroup\$ It is a weird thing to say, but I believe you should wait to have other answers before accepting mine. Questions that don't have accepted answers tend to have a little more attention ;) \$\endgroup\$ – IEatBagels Oct 6 '14 at 17:37
  • \$\begingroup\$ This review is good :) What I don't like is the Grow/Shrink and startingPos = 0; restarts, it is sooo strange and memory wasting.... but I am afraid that it may fail completely in certain scenairos (but not sure, it may work thanks to Shrink=restart condition). \$\endgroup\$ – user52292 Oct 6 '14 at 18:01
10
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ if(IsEmpty) throw new InvalidOperationException(); \$\endgroup\$ – Raz Megrelidze Oct 6 '14 at 22:30
  • \$\begingroup\$ I missed that. :) \$\endgroup\$ – Raz Megrelidze Oct 6 '14 at 22:32
7
\$\begingroup\$

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;}
    
\$\endgroup\$
  • \$\begingroup\$ I would changing your third question. You're implying that everything is public and you have to decide what should not be visible. I believe everything by default should be hidden, and you ask yourself what methods does the consumer need access to. This also helps define limits on your unit tests. \$\endgroup\$ – Sam Oct 7 '14 at 17:18
6
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ you are probably correct about array[startingPos + Count++] = item. I wrote this queue out of my head. Next time i'll spend more time testing the implementation (using NUnit would be a good idea). \$\endgroup\$ – Raz Megrelidze Oct 6 '14 at 23:18
  • 3
    \$\begingroup\$ getCount? This is C#! We have properties for that! \$\endgroup\$ – user54490 Oct 7 '14 at 2:04
3
\$\begingroup\$

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.

\$\endgroup\$
  • 4
    \$\begingroup\$ It's not recommended that types like this try to be thread-safe. The thread-safety needs of the caller cannot be pre-determined so trying to make something thread-safe for every type of caller and scenario is impossible. That's not to say that some level of thread-safety wouldn't be useful; but it's generally very hard and forces callers to take that performance hit even if they don't need thread-safety. \$\endgroup\$ – Peter Ritchie Oct 6 '14 at 19:51
  • \$\begingroup\$ Pretty much that. If the caller needs thread safety, that's their responsibility, not yours, because it needs to be tailored to their particular case. A one-size-fits-all approach to thread safety simply doesn't work -- and even when it sorta does, it's sub-optimal. \$\endgroup\$ – cHao Oct 6 '14 at 23:32

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.