Queue.cs

usingSystem;
usingSystem.Collections.Generic;

namespaceDataStructures.Lists
{
/// <summary>
/// The Queue (FIFO) Data Structure.
/// </summary>
publicclassQueue<T>:IEnumerable<T>whereT:IComparable<T>
{
/// <summary>
/// INSTANCE VARIABLE.
/// </summary>
privateint_size{get;set;}
privateint_headPointer{get;set;}
privateint_tailPointer{get;set;}

// The internal collection.
privateT[]_collection{get;set;}
privateconstint_defaultCapacity=8;

// This sets the default maximum array length to refer to MAXIMUM_ARRAY_LENGTH_x64
// Set the flag IsMaximumCapacityReached to false
boolDefaultMaxCapacityIsX64=true;
boolIsMaximumCapacityReached=false;

// The C# Maximum Array Length (before encountering overflow)
// Reference: http://referencesource.microsoft.com/#mscorlib/system/array.cs,2d2b551eabe74985
publicconstintMAXIMUM_ARRAY_LENGTH_x64=0X7FEFFFFF;//x64
publicconstintMAXIMUM_ARRAY_LENGTH_x86=0x8000000;//x86


/// <summary>
/// CONSTRUCTOR
/// </summary>
publicQueue():this(_defaultCapacity){}

publicQueue(intinitialCapacity)
{
if(initialCapacity<0)
{
thrownewArgumentOutOfRangeException();
}

_size=0;
_headPointer=0;
_tailPointer=0;
_collection=newT[initialCapacity];
}


/// <summary>
/// Resize the internal array to a new size.
/// </summary>
privatevoid_resize(intnewSize)
{
if(newSize>_size&&!IsMaximumCapacityReached)
{
intcapacity=(_collection.Length==0?_defaultCapacity:_collection.Length*2);

// Allow the list to grow to maximum possible capacity (~2G elements) before encountering overflow.
// Note that this check works even when _items.Length overflowed thanks to the (uint) cast
intmaxCapacity=(DefaultMaxCapacityIsX64==true?MAXIMUM_ARRAY_LENGTH_x64:MAXIMUM_ARRAY_LENGTH_x86);

// Handle the new proper size
if(capacity<newSize)
capacity=newSize;

if(capacity>=maxCapacity)
{
capacity=maxCapacity-1;
IsMaximumCapacityReached=true;
}

// Try resizing and handle overflow
try
{
//Array.Resize (ref _collection, newSize);

vartempCollection=newT[newSize];
Array.Copy(_collection,_headPointer,tempCollection,0,_size);
_collection=tempCollection;
}
catch(OutOfMemoryException)
{
if(DefaultMaxCapacityIsX64==true)
{
DefaultMaxCapacityIsX64=false;
_resize(capacity);
}
else
{
throw;
}
}
}
}


/// <summary>
/// Returns count of elements in queue
/// </summary>
publicintCount
{
get{return_size;}
}

/// <summary>
/// Checks whether the queue is empty.
/// </summary>
publicboolIsEmpty
{
get{return_size==0;}
}

/// <summary>
/// Returns the top element in queue
/// </summary>
publicTTop
{
get
{
if(IsEmpty)
thrownewException("Queue is empty.");

return_collection[_headPointer];
}
}

/// <summary>
/// Inserts an element at the end of the queue
/// </summary>
/// <param name="dataItem">Element to be inserted.</param>
publicvoidEnqueue(TdataItem)
{
if(_size==_collection.Length)
{
try
{
_resize(_collection.Length*2);
}
catch(OutOfMemoryExceptionex)
{
throwex;
}
}

// Enqueue item at tail and then increment tail
_collection[_tailPointer++]=dataItem;

// Wrap around
if(_tailPointer==_collection.Length)
_tailPointer=0;

// Increment size
_size++;
}

/// <summary>
/// Removes the Top Element from queue, and assigns it's value to the "top" parameter.
/// </summary>
/// <return>The top element container.</return>
publicTDequeue()
{
if(IsEmpty)
thrownewException("Queue is empty.");

vartopItem=_collection[_headPointer];
_collection[_headPointer]=default(T);

// Decrement the size
_size--;

// Increment the head pointer
_headPointer++;

// Reset the pointer
if(_headPointer==_collection.Length)
_headPointer=0;

// Shrink the internal collection
if(_size>0&&_collection.Length>_defaultCapacity&&_size<=_collection.Length/4)
{
// Get head and tail
varhead=_collection[_headPointer];
vartail=_collection[_tailPointer];

// Shrink
_resize((_collection.Length/3)*2);

// Update head and tail pointers
_headPointer=Array.IndexOf(_collection,head);
_tailPointer=Array.IndexOf(_collection,tail);
}

returntopItem;
}

/// <summary>
/// Returns an array version of this queue.
/// </summary>
/// <returns>System.Array.</returns>
publicT[]ToArray()
{
vararray=newT[_size];

intj=0;
for(inti=0;i<_size;++i)
{
array[j]=_collection[_headPointer+i];
j++;
}

returnarray;
}

/// <summary>
/// Returns a human-readable, multi-line, print-out (string) of this queue.
/// </summary>
publicstringToHumanReadable()
{
vararray=ToArray();
stringlistAsString=string.Empty;

inti=0;
for(i=0;i<Count;++i)
listAsString=String.Format("{0}[{1}] => {2}\r\n",listAsString,i,array[i]);

returnlistAsString;
}


/********************************************************************************/


publicIEnumerator<T>GetEnumerator()
{
return_collection.GetEnumerator()asIEnumerator<T>;
}

System.Collections.IEnumeratorSystem.Collections.IEnumerable.GetEnumerator()
{
returnthis.GetEnumerator();
}

}

}