// 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
//-----------------------------------------------------------------------------

template<class ItemType>
void StackType<ItemType> :: CopyNth(int N, ItemType& copyitem)
{
    NodeType<ItemType>* tempPtr;
    int i=1;

    if (!IsEmpty())
    {
        tempPtr = topPtr;
        while(i < N && tempPtr != NULL)
        {
            tempPtr = tempPtr->next;
 
            i++;
        }   
        copyitem = tempPtr->info;
    }
    else
        cout << "\nError - attempting to copy an item from an empty stack.";
}