#include "d:\List.h"
#include<iostream.h>
#include<conio.h>
 
template<class T>
void testQueue(Queue <T> &q)
{
 int choice;
 T val;
 menuQueue();
 do {
    cout <<"?";
    cin >> choice;
switch (choice) {
  case 1:  cout <<"Input number:";
	   cin >> val;
	   q.enqueue(val);
	   q.print();
	   break;
  case 2:  if(q.dequeue(val))
	    cout << val <<"is deleted" << endl;
	   q.print();
	   break;
	  }
     } while (choice!=3);
}
 
void menuQueue()
{
 cout  <<"1-enqueue()" << endl   // помещает элемент в очередь
       <<"2-dequeue()" << endl    // извлекает элемент из очереди
       <<"3-exit()" << endl << endl;
}
 
int main()
{ clrscr();
  cout << "Queue of integer numbers:" << endl << endl;
  Queue<int>intQueue;
  testQueue(intQueue);
  getch();
  return 0;
}

//List.h
 
 
# include <iostream.h>
# include <assert.h>
template <class T>
class List;
template <class T>
class Node {
   friend class List <T>;	//класс-друг
private:
   T data;      	//элемент данных узла
   Node *next;     	//указатель на следующий узел
public:
   Node(T &);		//конструктор с параметром
   T getData();   	//чтение элемента данных узла
};
template <class T>
Node <T> :: Node(T &d)
{ 
   data = d; 
   next = NULL; 
}
template <class T>
T Node <T> :: getData() 
{ 
   return data;
}
 
template <class T>
class List {
   Node <T> *first;         	//указатель на первый узел
   Node <T> *last;         	//указатель на последний узел
   Node <T> *newNode(T &);  	// указатель на новый узел
public:
   List();				//конструктор 
   ~List();				//деструктор
   void addHead(T &);      	//добавляет узел в начало списка
   void addTail(T &);      	//добавляет узел в конец списка
   int removeHead(T &);    	//удаляет узел из начала списка
   int removeTail(T &);    	//удаляет узел из конца списка
   int isEmpty();          	//проверяет, пуст ли список
   void print();            	//печатает содержимое списка
};
template <class T>
List <T> :: List()
{ 
   first = last = NULL; 
}
template <class T>
List <T> :: ~List()
{
   if(!isEmpty()) {       		//если список не пуст
 
      Node <T> *curr = first;		//указатель на текущий узел
      Node <T> *temp;     		//указатель на удаляемый узел
      cout << endl << "Deletion of nodes:" << endl;
      while(curr != NULL) { 		//пока не конец списка
         temp = curr;			//запомнить удаляемый узел
         curr = curr->next;		//обновить текущий узел
	 cout << temp->data << ' ';	//печать удаляемого узла
         delete temp;			//удалить узел
      }
   }
   cout << endl << "All nodes are deleted" << endl;
}
template <class T>
void List <T> :: addHead(T &val)
{
   Node <T> *newPtr = newNode(val);	//создать новый узел
   if(isEmpty())         		//если список пуст
      first = last = newPtr;		//вставить в пустой список
   else {						//если список не пуст
      newPtr->next = first;		//вставить в начало списка 
      first = newPtr;
   }
}
template <class T>
void List <T> :: addTail(T &val)
{
   Node <T> *newPtr = newNode(val);	//создать новый узел
   if(isEmpty())      			//если список пуст
      first = last = newPtr;		//вставить в пустой список
   else {						//если список не пуст
      last->next = newPtr; 		//вставить в конец списка
      last = newPtr;
   }
}
template <class T>
int List <T> :: removeHead(T &val)
{
   if(isEmpty())  				//если список пуст
      return 0;   				//неудачное удаление
   else {						//если список не пуст
      Node <T> *temp = first;		//запомнить удаляемый узел
      if(first == last) 			//если конец списка
	 first = last = NULL;		//сделать список пустым
      else					//если не конец списка
         first = first->next;		//обновить первый узел
      val = temp->data;			//передать элемент данных
      delete temp;				//удалить узел
      return 1;				//успешное удаление
   }
}
template <class T>
int List <T> :: removeTail(T &val)
{
   if(isEmpty())        			//если список пуст
      return 0;         			//неудачное удаление
   else {						//если список не пуст
      Node <T> *temp = last;		//запомнить удаляемый узел
      if(first == last)			//если конец списка
         first = last = NULL; 	//сделать список пустым
      else {					//если не конец списка
         Node <T> *curr = first;	//сделать текущим первый узел 
         while (curr->next != last)	//сделать текущим
            curr = curr->next;		//предпоследний узел 
         last = curr;			//обновить последний узел
         curr->next = NULL;
      }
      val = temp->data; 			//передать элемент данных
      delete temp;				//удалить узел
      return 1;         			//успешное удаление
   }
}
template <class T>
int List <T> :: isEmpty() 
{ 
   return first == NULL;		//возвратить NULL, если список пуст
}
template <class T>
Node <T> *List <T> :: newNode(T &val)
{
   Node <T> *p = new Node <T> (val);	//создать новый узел
   assert(p != NULL);
   return p;
}
template <class T>
void List <T> :: print() 
{
   if(isEmpty()) {
      cout << "List is empty" << endl << endl;
      return;
   }
   Node <T> *curr = first;		//сделать текущим первый узел
   cout << "List:" << endl;
   while (curr != NULL) 			//пока список не пуст	
   {
      cout << curr->data << " -> ";	//напечатать текущий узел
      curr = curr->next;				//обновить текущий узел 
   }
   cout << endl << endl;
}
 
template <class T>
class Queue: public List <T> {
public:
   void enqueue(T &d)		//помещает элемент в очередь
   {
      addTail(d);
   }
   int dequeue(T &d) 		//извлекает элемент из очереди
   {
      return removeHead(d);
   }
 
};