// 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 ??";
}


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

	int index=0;  // counter

	tempPtr=topPtr; // temporay pointer is the same as the first pointer
        
	if(!IsEmpty())
        {
		while(index<N-1)  // search for location of Nth number
		{
			tempPtr= tempPtr->next;
			index++;
		}
		copyitem= tempPtr->info; // store value of Nth location
        }
 
}