String Queue implementation Is the implementation clean enough &amp; can be used in production?
I tried to write clean &amp; bug-free code. It looks good to me.

I would appreciate any improvement suggestions. 

One question I have is, what are the corner cases one might need to consider while implementing a Queue like this that might be part of a 3rd party library?


  I am aware of the build-in C# Queue type. In production obviously that's what I would use


using System;

internal class Queue
{
    private System.String[] _container;
    private System.Int32 _topHook = 0;
    private System.Int32 _downHook = 0;

    public Queue(System.Int32 capacity = 5)
    {
        _container = new System.String[capacity];
    }

    public bool IsEmpty() =&gt; Count == 0;

    public System.Int32 Count { get { return _topHook - _downHook; } }

    public void Enqueue(System.String item)
    {
        if(Count == _container.Length) ReSize(Count * 2);
        _container[_topHook++] = item;
    }

    public System.String Dequeue()
    {
        if(IsEmpty()) throw new Exception("No Element In Queue");
        if(Count == _container.Length / 4) ReSize(Count * 2);

        var dequeuedValue = _container[_downHook++];

        _container[_downHook - 1] = null;

        return dequeuedValue;
    }

    private void ReSize(System.Int32 capacity)
    {
        System.String[] container = new System.String[capacity];
        var j = 0;

        for(var i = 0; i &lt; _container.Length; i++)
            if(_container[i] != null)
                container[j++] = _container[i];

        _container = container;
        _topHook = Count;//_topHook will point to the NEXT element
        _downHook = 0;
    }

}
using System;


If you're going to say using System then don't be putting lots of System.s in the file; the point of this is to eliminate those.



internal class Queue


Is the class intended to be subclassed? If not, seal it. You can always unseal it later if you need to design it for extension.

Why do you not implement IEnumerable&lt;string&gt; ? Surely one of the primary use cases of a collection is enumerating it.

There is nothing in here that is specific to strings; it would be just as easy to write Queue&lt;T&gt;. 



private System.String[] _container


Using System.String, System.Int32 and so on is legal, but not idiomatic in C#. Use string, int, and so on.



public Queue(System.Int32 capacity = 5)


What led you to believe that 5 is the correct number here? The maintenance programmer in the future will want to know what the consequences are of changing it to 10 or 1 or a million. Document the things that are not obvious from the code, and avoid "magic numbers".



public bool IsEmpty() =&gt; Count == 0;


This could be a property.



    if(Count == _container.Length) ReSize(Count * 2);
    _container[_topHook++] = item;


You might consider making a private property Capacity:

private int Capacity =&gt; _container.Length;


And now your code reads better. 

if(Count == Capacity) ReSize(Count * 2);


Remember, keep your code in the business domain as much as possible. The length of the container is a mechanism.

Use assertions to document your invariants. That way if you break them, you get informed in your tests:

    Debug.Assert(Count &lt;= Capacity); // precondition of resize
    if(Count == Capacity) 
      ReSize(Count * 2);
    Debug.Assert(Count &lt; Capacity); // postcondition of resize


Do this throughout; any invariant you can think of, document it with an assertion. Like, the count goes up when you enqueue and down when you dequeue, and so on.

Now, of course, this code is still completely wrong.

Suppose the array length is 5, top is 0, bottom is 0.  We enqueue four strings, so top is 4, bottom is 0. Now we dequeue. Top is 4, bottom is 1.  Now we enqueue. Follow your logic:


count is 4 - 1 = 3
3 is not 5, so no resize
top increments to 5


Now we enqueue again


count is 5 - 1 = 4
4 is not 5, so no resize
and we dereference container[5], which is out of bounds.


Do you see your bug here?

The problem is that the condition you are attempting to avoid -- dereferencing out of bounds -- and the condition you are checking -- count vs capacity -- have nothing to do with each other. The code should be:

    Debug.Assert(_topHook &lt;= _container.Length);
    Debug.Assert(Count &lt;= Capacity);
    if (_topHook == _container.Length)
      ReSize(Count * 2);
    Debug.Assert(Count &lt; Capacity);
    Debug.Assert(_topHook &lt; _container.Length);
    _container[_topHook++] = item;




    _container[_topHook++] = item;


I understand that C programmers like this sort of thing. I don't. A line of code should have one effect, and this one has two, and requires that you correctly reason about the ordering of effects.  Write the code so that it is crystal clear:

    _container[_topHook] = item;
    _topHook += 1;
    Debug.Assert(_topHook &lt;= _container.Length);
    Debug.Assert(Count &lt;= Capacity);




if(IsEmpty()) throw new Exception("No Element In Queue");  


Don't use Exception as anything but a base class in production code. This could be an invalid operation exception, or make your own exception.



    if(Count == _container.Length / 4) ReSize(Count * 2);


The logic here is correct, but is nowhere documented. The logic is: we wish to maintain two properties, first, that there is never more than a ratio of three to one for wasted space to used space, and second, that there is never a sequence of enqueue-dequeue or dequeue-enqueue operations that both cause an expensive resize. Give a justification here for why and how this logic maintains those invariants.

Consider also: who cares if we are "wasting" in a 4:1 ratio in the case where we have capacity 5 and count 1 ?  Resizing the array to size 2 in this case is a waste of time.  Consider taking a more sophisticated approach for small queues. Abstract the decision of whether to resize, and by how much, to a helper method that encapsulates that policy.



    var dequeuedValue = _container[_downHook++];
    _container[_downHook - 1] = null;


See what your obsession with putting the ++ in place has cost you? You do work in the decrement, and then you undo that work because you did it too soon! This is hard to reason about and a bug waiting to happen given any modification to this code.  If you find you are undoing work you just did, you are doing something wrong; write the code more clearly:

    var dequeuedValue = _container[_downHook];
    _container[_downHook] = null;
    _downHook -= 1;




"Resize" is a word; it's not "re size". So the method should be Resize, not ReSize.



As noted in the other answer the resize logic is wrong.  The correct logic is to copy all the elements from downhook to tophook-1 in the original array into 0 to count-1 in the new array.

Never just fix a bug. Ask yourself "how could I have better reasoned about this code so as to avoid the bug?" and "how could I have changed the design of the code so as to avoid the bug?"  For example:

Resizing a queue should not be affected in any way by the contents of the queue, and so if you are making a comparison against an element of the queue during a resize, you know immediately that you've done something wrong.

Also, resizing a queue should take as many operations as there are elements in the queue, but you do as many operations as there are in the array. So again, you could have known from first principles that the code was probably wrong.

Finally, this bug would have been never written in the first place had you made a generic Queue&lt;T&gt;, since there is no "null" T to use as a marker. Solving the more general problem is sometimes easier than solving a specific problem, because it forces you to not try to take advantages of specifics, like the nullability of strings.

Develop the ability to reason about these sorts of invariants, and you will find that you will write code that is more likely correct and better performing.

Also, there are already helper methods on Array to help you copy elements from one array to another, and added bonus, they are possibly faster than the code you're writing. Use them.



There's another bug in Resize. Suppose your user says that they expect the capacity to be 1000. Fine; we allocate a thousand items for the array. Then they do 250 enqueues and a dequeue. What happens? The capacity is reset to 500! 

The user said that they had an expectation of how much storage they'd need, in order to cut down on the number of resizes on the way there. But you possibly give them a resize on the way to 1000 items. 

Keep track of the user's capacity preference, and use that as the minimum array capacity; don't shrink to less than that. They said they're cool with using that much memory, so honour that request.



There is no logic in here that will help with debugging or testing. For example, it would be nice to see something like an implementation of ToString that dumps out a comma-separated list.



EXERCISE: Resizes are expensive; they are an O(n) operation, and so should be done as little as possible. Consider a queue where you enqueue a thousand items, then for the rest of the program you do enqueue-dequeue-enqueue-dequeue-enqueue-dequeue a few million times. How many resizes are there? 

Plainly there could be zero resizes because the queue never grows in size beyond 1001 items in this scenario. And yet there are a great many resizes!  What can you do to eliminate resizes in this scenario?