#ifndef __QUEUE
#define __QUEUE


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


template <class T>
class Queue {
  __QueueNode<T> *Front, *Rear;

 public:
  Queue () { Front = Rear = NULL; }
  ~Queue ();
  
  virtual bool isEmpty () { return Front ? false : true; }
  virtual bool Enqueue (T&);
  virtual bool Dequeue (T&);
  virtual bool Print (bool (*) (T&));
  virtual bool Reverse ();

};

template <class T>
Queue<T>::~Queue () 
{ 
  while (Front != NULL)
    {
      Rear = Front->next;
      delete Front;
      Front = Rear;
    }
}

template <class T>
bool Queue<T>::Enqueue (T& c)
{
  __QueueNode<T> *ptr;
  
  ptr = new __QueueNode<T>;
  if (ptr == NULL)
    return false;
  ptr->key = c; ptr->next = NULL;
  if (Rear != NULL)
    {
      Rear->next = ptr;
    }
  else
    {
      Front = ptr;
    }
  Rear = ptr;
  return true;
}

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

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

template <class T>
bool Queue<T>::Reverse () 
{
  if (isEmpty ())
    return true;
  __QueueNode<T>* current = Front;
  __QueueNode<T>* nextElem = Front->next;
  Front->next = NULL;
  while (nextElem != NULL) {
    __QueueNode<T>* tmp = nextElem->next;
    nextElem->next = current;
    current = nextElem;
    nextElem = tmp;
  }
  Front = current;
  return true;
}

#endif