template <class T>
struct Node
{
    T data;
    Node<T> *next;
};
template <class T>
class LinkQueue
{
public:
    LinkQueue()
    {
        front = rear = new Node<T>;
        front->next = NULL;
    }
    ~LinkQueue();
    void EnQueue(T x);
    T DeQueue();
    T GetQueue();
    bool Empty() { return rear == front; }

private:
    Node<T> *front;
    Node<T> *rear;
};
template <class T>
LinkQueue<T>::~LinkQueue()
{
    while (front)
    {
        rear = front->next;
        delete front;
        front = rear;
    }
}
template <class T>
void LinkQueue<T>::EnQueue(T x)
{
    Node<T> *now = new Node<T>;
    now->data = x;
    rear->next = now;
    rear = now;
    rear->next = NULL;
}
template <class T>
T LinkQueue<T>::DeQueue()
{

    if (Empty())
        throw "空";
    Node<T> *now = front->next;
    front->next = now->next;
    T x = now->data;
    if (!(front->next)) // if (rear == now)
        rear = front;
    delete now;
    return x;
}
template <class T>
T LinkQueue<T>::GetQueue()
{
    if (Empty())
        throw "空";
    return front->next->data;
}