// Implementation file for Queue ADT; class specification in file queuell.h.
// Class is templated.
// Uses linked list of items with a pointer to the head and one to the tail.

//------------------------------------------------------------------------------------
// NodeType for nodes in linked list
//------------------------------------------------------------------------------------

template <class ItemType>
struct NodeType
{
    ItemType info;
    NodeType* next;
};

//------------------------------------------------------------------------------------
// Queue Constructor - Initializes an empty queue
//------------------------------------------------------------------------------------

template <class ItemType>
QueueType<ItemType>::QueueType()
{
    qFront = NULL;
    qRear = NULL;
}

//------------------------------------------------------------------------------------
// Queue Destructor - releases memory used by nodes
//------------------------------------------------------------------------------------

template <class ItemType>
QueueType<ItemType>::~QueueType()
{
    NodeType<ItemType>* tempPtr;

    while (qFront != NULL)
    {
        tempPtr = qFront;
        qFront = qFront->next;
        delete tempPtr;
    }
    qRear = NULL;
}

//------------------------------------------------------------------------------------
// IsEmpty - tests for empty queue
//------------------------------------------------------------------------------------
// Returns true if the queue is empty; false otherwise
//------------------------------------------------------------------------------------

template <class ItemType>
bool QueueType<ItemType>::IsEmpty() const
// Returns true if there are no elements on the queue; false otherwise.
{
    return (qFront == NULL);
}

//------------------------------------------------------------------------------------
// IsQueue - tests for full queue  (linked implementation "never" full!)
//------------------------------------------------------------------------------------

template <class ItemType>
bool QueueType<ItemType>::IsFull() const
{
    return false;
}

//------------------------------------------------------------------------------------
// Enqueue - adds item to rear of the queue
//------------------------------------------------------------------------------------
// Accepts:  item to be added
//------------------------------------------------------------------------------------

template <class ItemType>
void QueueType<ItemType>::Enqueue(ItemType newItem)
{
    NodeType<ItemType>* newNode;

    newNode = new NodeType<ItemType>;
    newNode->info = newItem;
    newNode->next = NULL;
    if (qRear == NULL)
        qFront = newNode;
    else
        qRear->next = newNode;
    qRear = newNode;
}

//------------------------------------------------------------------------------------
// Dequeue - removes item at front of queue
//------------------------------------------------------------------------------------
// Returns:  copy of item removed
//------------------------------------------------------------------------------------

template <class ItemType>
void QueueType<ItemType>::Dequeue(ItemType& item)
{
    NodeType<ItemType>* tempPtr;

    if (!IsEmpty())
    {
        tempPtr = qFront;
        item = qFront->info;
        qFront = qFront->next;
        if (qFront == NULL)
            qRear = NULL;
        delete tempPtr;
    }
    else
        cout << "\nError - attempting to remove item from empty queue";
}



//--------------------------------------------------------------------------
// CopyNth - shows copy of item located in Nth position from top of queue
//--------------------------------------------------------------------------
// Accepts:  The position of the item
// Returns:  copy of item at Nth position from front
//--------------------------------------------------------------------------
template<class ItemType>
void QueueType<ItemType>::CopyNth(int N, ItemType& copyitem)
{
        NodeType<ItemType>* tempPtr; // temporary pointer for transversing list

	int i=0;  // counter
	
        tempPtr=qFront;              // temporary pointer is the same as 
			             // first pointer in the queue
        if(!IsEmpty())
        {
                while(i<N-1) // search for Nth position
                {
                        tempPtr= tempPtr->next;
			i++;
                }
                copyitem= tempPtr->info; // store item located in Nth
					 // position 
        }
         
}