#ifndef __QUEUE
#define __QUEUE

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

  Node *Front, *Rear;

 public:

  Queue::Queue () 
    { Front = Rear = NULL; }
  
  Queue::~Queue () 
    { 
      while (Front != NULL)
	{
	  Rear = Front->next;
	  delete Front;
	  Front = Rear;
	}
    }
  
  bool Queue::Enqueue (T c)
    {
      Node *ptr;
      
      ptr = new Node;
      if (ptr == NULL)
	return false;
      ptr->key = c; ptr->next = NULL;
      if (Rear != NULL)
	{
	  Rear->next = ptr;
	}
      else
	{
	  Front = ptr;
	}
      Rear = ptr;
      return true;
    }
  
  bool Queue::Dequeue (T& c)
    {
      Node *ptr = Front;
      
      if (Front != NULL)
	{
	  Front = Front->next;
	  c = ptr->key;
	  delete ptr;
	}
      if (Front == NULL)
        {
	  Rear = NULL;
          return false;
        }
      return true;
    }
  
  bool Queue::isEmpty () { return Front ? false : true; }
  
  bool Queue::Print () 
    {
      Node *Prev = Front;
      
      while (Prev) {
	cout << Prev->key << " ";
	Prev = Prev->next;
      }
      cout << endl;
    }
  
  bool Queue::Reverse () 
    {
      if (isEmpty ())
	return true;
      Node* current = Front;
      Node* nextElem = Front->next;
      Front->next = NULL;
      while (nextElem != NULL) {
	Node* tmp = nextElem->next;
	nextElem->next = current;
	current = nextElem;
	nextElem = tmp;
      }
      Front = current;
      return true;
    }

};

#endif