template <class DT>
struct QNode  //结点
{
	DT data;     //数据域，存储数据元素值
	QNode *next;//指针域，指向下一个结点
};

template<class DT>
struct LinkQueue
{
	QNode<DT> * front;
	QNode<DT> * rear;
};


//【算法3.19】
template <class DT>
void InitQueue(LinkQueue<DT> &Q)//创建空队列
{
	Q.front=new QNode<DT>;     //创建头结点
	if(!Q.front) exit(1);  //创建失败，结束运行
	Q.front->next=NULL;
	Q.rear=Q.front;
}

//【算法3.20】
template <class DT>
void DestroyQueue(LinkQueue<DT> &Q)//释放链队
{
	QNode<DT> *p;
	while(Q.front)//从头结点开始，依次释放结点
	{
		p=Q.front;
		Q.front=Q.front->next;
	    delete p;
	}
}

//【算法3.21】
template<class DT>
bool EnQueue(LinkQueue<DT> &Q,DT e)
{
    QNode<DT> *p;
    p=new QNode<DT>;
    if(!p) return false;  //创建失败，结束运行
    p->data=e;       // 新结点赋值
    p->next=NULL;  //
    Q.rear->next=p;
    Q.rear=p;
	return true;    // 插入成功，返回true
}

//【算法3.22】
template<class DT>
bool DeQueue(LinkQueue<DT> &Q,DT &e)
{
    QNode<DT> *p;
    if(Q.front==Q.rear)  return false;     //队空
    p=Q.front->next;
    e=p->data;
    Q.front->next=p->next;
    if(Q.rear==p)   Q.rear=Q.front;    //最后一个元素被删
    delete p;
	return true;    // 删除成功，返回true
}


//【算法3.23】
template<class DT>
bool GetHead(LinkQueue<DT> Q,DT &e)
{
	if(Q.front==Q.rear)  return false;     //队空
    e=Q.front->next->data;
	return true;    // 删除成功，返回true
}

//取队尾元素
template<class DT>
bool GetTail(LinkQueue<DT> Q,DT &e)
{
	//LNode<DT> *p;
    if(Q.front==Q.rear)  return false;
    e=Q.rear->data;
	return true;    // 删除成功，返回true
}

//测队空
template<class DT>
bool QueueEmpty(LinkQueue<DT> Q)
{
	if(Q.front==Q.rear)
		return true;
	else
		return false;
}

//显示队列内容
template<class DT>
void DispQueue(LinkQueue<DT> Q)
{
    QNode<DT> *p;
    p=Q.front->next;
	while(p)
	{
		cout<<p->data<<"\t";
		p=p->next;
	}
	cout<<endl;
}