#ifndef __STACK
#define __STACK

template <class T>
class Stack {
  class Node {
  public:
    T key;
    Node* next;
  };
  Node *Front;

public:
  
  Stack::Stack () { Front = NULL; }
  Stack::~Stack () 
    { 
      Node *tmpRef;
      while (Front != NULL)
	{
	  tmpRef = Front->next;
	  delete Front;
	  Front = tmpRef;
	}
    }
  
  bool Stack::Push (T c)
    {
      Node *ptr;
      
      ptr = new Node;
      if (ptr == NULL)
	return false;
      ptr->key = c; 
      ptr->next = Front;
      Front = ptr;
      return true;
    }

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

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

  bool Stack::isEmpty ()
    {
      return Front ? false : true;
    }
  

  bool Stack::Print () {
    Node *Prev = Front;
    
    while (Prev) 
      {
	cout << Prev->key << " ";
	Prev = Prev->next;
      }
    cout << endl;
  }

  bool Stack::Reverse () 
    {
      Node *Prev1, *Prev2;
      
      if (Front == NULL) return true;      // List is empty
      Prev2 = Front; Prev1 = Front->next;  // Set initial value for Prev2
      if (Prev1 == NULL) {
	return true;                       // List has only one element
      }
      Front = Prev1->next;  // Set initial value for Prev1
      Prev2->next = NULL;                  // Set the new end of the list
      while (Front != NULL) {              // while the end is not reached
	Prev1->next = Prev2;               // Change the pointer direction
	Prev2 = Prev1; Prev1 = Front;      // Advance
	Front = Front->next;               // Advance (2)
      }
      Prev1->next = Prev2;                 // The last set
      Front = Prev1;                       // Set the new Front of the list
      return true;
    }

};

#endif