// Implementation file for Stack ADT.
// Class definition is in "stackll.h".

// Class is templated; implementation is linked.
// ItemType is determined when a specific Stack class is instantiated.

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

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

//-------------------------------------------------------------------------------
// Stack Constructor - initializes an empty stack
//-------------------------------------------------------------------------------

template<class ItemType>
StackType<ItemType>::StackType()
{
    topPtr = NULL;
}

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

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

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

//-------------------------------------------------------------------------------
// IsEmpty - tests for empty stack
//-------------------------------------------------------------------------------

template <class ItemType>
bool StackType<ItemType>::IsEmpty() const
{
    return (topPtr == NULL);
}

//-------------------------------------------------------------------------------
// IsFull - tests for full stack  (linked implementation "never" full!)
//-------------------------------------------------------------------------------

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

//-------------------------------------------------------------------------------
// Push  - adds item to top of stack
//-------------------------------------------------------------------------------
// Accepts:   Item to be added
//-------------------------------------------------------------------------------

template <class ItemType>
void StackType<ItemType>::Push(ItemType newItem)
{
    NodeType<ItemType>* ptr;
    ptr = new NodeType<ItemType>;
    ptr->info = newItem;
    ptr->next = topPtr;
    topPtr = ptr;
}

//-------------------------------------------------------------------------------
// Pop - removes top item from stack
//-------------------------------------------------------------------------------

template<class ItemType>
void StackType<ItemType>::Pop()
{
    if (!IsEmpty())
    {
        NodeType<ItemType>* tempPtr;
        tempPtr = topPtr;
        topPtr = topPtr->next;
        delete tempPtr;
    }
    else 
        cout << "\nError - attempting to pop empty stack!";
}

//-------------------------------------------------------------------------------
// Top - shows copy of top stack item leaving stack structure intact
//-------------------------------------------------------------------------------
// Returns:  copy of top item
//-------------------------------------------------------------------------------

template<class ItemType>
ItemType StackType<ItemType>::Top()
{
    if (!IsEmpty())
        return topPtr->info;
    else
        cout << "\nError - viewing top of empty stack - returned item ??";
}


//-------------------------------------------------------------------------------
// Copy
//-------------------------------------------------------------------------------

template<class ItemType>
void StackType<ItemType>::CopyNth(int N, ItemType& copyitem)
{
   NodeType<ItemType>* ptr;
   int count = 1;
   bool found = false;
   ptr = topPtr;
   if(!IsEmpty())
   {	  
     while(count < N+1 && ptr != NULL && found == false)
     {
     	if(count == N)
	{
	   copyitem = ptr->info;
	   found = true;
	}
	else
	{  
	   ptr = ptr->next;
	   count++; 
	}	  
     }
   }		
}