#ifndef __STACK
#define __STACK

template <class T>
class __StackNode {
 public:
  T key;
  __StackNode<T>* next;
};

template <class T>
class Stack {
  __StackNode<T> *Front;

public:
  
  Stack () { Front = NULL; }
  virtual ~Stack ();

  virtual bool isEmpty () { return Front ? false : true; }
  virtual bool Push (T&);
  virtual bool Pop (T&);
  virtual bool Top (T&);
  virtual bool Reverse ();
  virtual bool Print (bool (*) (T&));
  
};

template <class T>
Stack<T>::~Stack () 
{ 
  __StackNode<T> *tmpRef;
  while (Front != NULL)
    {
      tmpRef = Front->next;
      delete Front;
      Front = tmpRef;
    }
}

template <class T>
bool Stack<T>::Push (T& c)
{
  __StackNode<T> *ptr;
  
  ptr = new __StackNode<T>;
  if (ptr == NULL)
    return false;
  ptr->key = c; 
  ptr->next = Front;
  Front = ptr;
  return true;
}

template <class T>
bool Stack<T>::Pop (T& c)
{
  __StackNode<T> *ptr = Front;
  
  if (Front != NULL)
    {
      Front = Front->next;
      c = ptr->key;
      delete ptr;
      return true;
    }
  return false;
}

template <class T>
bool Stack<T>::Top (T& c)
{
  if (Front != NULL)
    {
      c = Front->key;
      return true;
    }
  return false;
}

template <class T>
bool Stack<T>::Print (bool (*p) (T&)) {
  __StackNode<T> *Prev = Front;
  
  for (Prev = Front; Prev && p (Prev->key); Prev = Prev->next);
  return true;
}

template <class T>
bool Stack<T>::Reverse () 
{
  __StackNode<T> *Prev1, *Prev2;
  
  if (Front == NULL) 
    return true;  
  Prev2 = Front; 
  Prev1 = Front->next;
  if (Prev1 == NULL) 
    return true;            
  Front = Prev1->next;  
  Prev2->next = NULL;   
  while (Front != NULL) 
    {  
      Prev1->next = Prev2;   
      Prev2 = Prev1; Prev1 = Front; 
      Front = Front->next;     
    }
  Prev1->next = Prev2;       
  Front = Prev1;             
  return true;
}


#endif