#include <iostream>

using namespace std;

template <typename DataType>
struct Node
{
    DataType data;
    Node<DataType> *next; 
};

template <typename DataType>
class LinkQueue
{
public:
    LinkQueue( );          //构造函数，初始化一个空的链队列
    ~LinkQueue( );      //析构函数，释放链队列中各结点的存储空间
    void EnQueue(DataType x);  //将元素x入队
    DataType DeQueue( );       //将队头元素出队
    DataType GetHead( );     //取链队列的队头元素
    void Empty( );     //判断链队列是否为空
private:
    Node<DataType> *front, *rear;  //队头和队尾指针，分别指向头结点和终端结点
};

// 初始化
template <typename DataType>
LinkQueue<DataType>::LinkQueue( )
{
    Node <DataType> *s;
    s = new Node<DataType>;
    s->next = NULL;
    front = rear = s;
}

// 析构函数 链队的销毁
template <typename DataType>
LinkQueue<DataType>::~LinkQueue( )
{
    Node <DataType> *p;
    while(front != NULL)
    {
        p = front->next;
        delete front;
        front = p;
    }
}

// 入队操作
template <typename DataType>
void LinkQueue<DataType>:: EnQueue(DataType x)
{
    Node<DataType> * s = nullptr;
    s = new Node<DataType>;
    s->data = x; // 将节点s插入到队尾
    s->next = nullptr;
    rear->next = s;
    rear = s;  
}

// 出队操作
template <typename DataType>
DataType LinkQueue<DataType>:: DeQueue()
{
    DataType x;
    Node<DataType> * p = nullptr;
    if (rear == front) throw "下溢";
    p = front->next;
    x = p->data; // 暂存对头元素
    front->next = p->next; // 对头元素所在结点摘链
    if (p->next == nullptr) rear = front; // 出对前队列长度为1时候,要特殊考虑
    delete p;
    return x;
}

// 取对头操作
template <typename DataType>    
DataType LinkQueue<DataType>:: GetHead()
{
    return front->next->data;
}

// 判空操作
template <typename DataType>
void LinkQueue<DataType>:: Empty()
{
    if (front == rear) cout << "为空" << endl;
    else cout << "不空" << endl;
}

int main()
{
    LinkQueue<int> Q;         //创建模版类的实例 
    Q.Empty();

    cout<<"元素10和15执行入队操作:"<<endl;
    try
    {
        Q.EnQueue(10);             //入队操作
        Q.EnQueue(15);
    }
    catch (char* wrong)
    {
        cout<<wrong<<endl;;
    }
    cout<<"查看队头元素:"<<endl;
    cout<<Q.GetHead( )<<endl;     //读队头元素
    cout<<"执行出队操作:"<<endl;  //出队操作
    try
    {
        Q.DeQueue( );              
    }
    catch (char* wrong)
    {
        cout<<wrong<<endl;
    }
    cout<<"查看队头元素:"<<endl;
    cout<<Q.GetHead( )<<endl;

    return 0;
}