#include <string>

template <typename T>
struct node
{
  T nodeData;
  node<T> *next;
  node<T> *prev;

  node(const T& _data, node<T> *nxt = NULL, node<T> *prv = NULL)
  {
    this->nodeData = _data;
    this->next = nxt;
    this->prev = prv;
  }
};

template <typename T>
class Queue
{
private:
  node<T> *front;
  node<T> *rear;
public:
  Queue() { front = rear = NULL; }

  void enqueue(const T& _input)
  {
    node<T> *tmp = new node<T>(_input);
    if(rear == NULL)
      rear = front = tmp;
    else
      {
    rear->next = tmp;
    tmp->prev = rear;
    rear = tmp;
      }
  }

  T dequeue()
  {
    node<T>* tmp = this->front;
    T result;
    if(this->front == NULL)
      {
    std::cout << "\nQueue underflow\n";
    return T();
      }
    else
      {
    if(tmp->next != NULL)
      {
        tmp = tmp->next;
        result = this->front->nodeData;
        delete this->front;
        this->front = tmp;
        return result;
      }
    else
      {
        result = this->front->nodeData;
        delete this->front;
        this->front = NULL;
        this->rear = NULL;
        return result;
      }
      }
  }

  bool isEmpty()
  {
    return this->front == NULL;
  }

  // void remove(node<T> *n)
  // {
  //   if(front == NULL || n == NULL)
  //     return;

  //   if(front == n)
  //     front = front->next;

  //   if(n->next != NULL)
  //     n->next->prev = n->prev;

  //   if(n->prev != NULL)
  //     n->prev->next = n->next;

  //   delete n;
  // }

  void printQueue()
  {
    node<T> *tmp = front;
    while(tmp != NULL)
      {
    std::cout << tmp->nodeData << " ";
    tmp = tmp->next;
      }
  }

  void printTail()
  {
    node<T> *tmp = rear;
    while(tmp != NULL)
      {
    std::cout << tmp->nodeData << " ";
    tmp = tmp->prev;
      }
  }

  node<T>* getHead() { return this->front; }
  node<T>* getTail() { return this->rear; }
};