// Stack class interface: linked list implementation
//
// Etype: must have zero-parameter and copy constructor
// CONSTRUCTION: with (a) no initializer;
//     copy construction of Stack objects is DISALLOWED
//
// ******************PUBLIC OPERATIONS*********************
// void Push( Etype X )   --> Insert X
// void Pop( )            --> Remove most recently inserted item
// Etype Top( )           --> Return most recently inserted item
// int IsEmpty( )         --> Return 1 if empty; else return 0
// int IsFull( )          --> Return 1 if full; else return 0
// void MakeEmpty( )      --> Remove all items
// ********************************************************

#ifndef __StkList
#define __StkList

#include <stdlib.h>

template <class Etype>
class Stack
{
  private:
    struct StackNode
    {
        Etype 		Element;
        StackNode 	*Next;
    };
    StackNode 		*TopOfStack;            // Only data member
    Stack(const Stack &);                   // Prevent copy

  public:
    Stack( ) : TopOfStack( NULL ) { }        // Initialize pointer
    ~Stack( ) { MakeEmpty( ); }              // Make sure it's gone

    void Push( const Etype & X );
    void Pop( );
    const Etype & Top( ) const;
	int IsEmpty( ) const
		{ return TopOfStack == NULL; }      // Just check pointer
	int IsFull( ) const
		{ return 0; }                       // Not possible
	void MakeEmpty( );                      
};

template <class Etype>
void Stack<Etype>::Push( const Etype & X )
{
	StackNode	*temp;

	temp = new StackNode;                   // Make node
	temp->Element = X;                      // Fill in parts
    temp->Next = TopOfStack;
	TopOfStack = temp;                      // Add to top
}

template <class Etype>
void Stack<Etype>::Pop( )
{
	StackNode 	*Old = TopOfStack;

	if (IsEmpty())                          // Insure validity
    { 	cout << "Attempt to Pop an empty stack.\n";
    	exit(1);   }
	TopOfStack = TopOfStack->Next;          // Remove top
    delete Old;
}

template <class Etype>
const Etype & Stack<Etype>::Top( ) const
{
    if (IsEmpty())                          // Insure validity
    { 	cout << "Attempt to access top of empty stack.\n";
    	exit(1);   }
	return TopOfStack->Element;             // Get top element
}

template <class Etype>
void Stack<Etype>::MakeEmpty( )
{
    while( !IsEmpty( ) )
		Pop( );                            // Remove an element
}

#endif