假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点（算法）

内容：

      假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点（注意不设头指针），试编写相应的置空队、判空对、入队和出队等算法。

步骤：

1.算法分析：

       要写出置空队、判空队、入队和出队的算法之前，需要先定义链队结构。其中，首先需要定义结点类型，而且只设置一个指向队尾元素的指针。

       定义好链队结构之后，先写置空队的算法。所谓置空队，就是使头结点成为队尾元素，将队尾指针指向头结点。但是这里可能会出现一个意外情况，就是队中元素非空，所以接下来需要将队中元素逐个出队，这里使用while语句进行操作，条件为Q->rear!=Q->rear->next，将队中元素全部出队后，回收其结点空间，避免空间浪费。

       判队空的算法十分简单，就是头结点的next指针指向自己时为空队。

      入队，也就是在尾结点处插入元素。插入前需要申请新结点，申请完成后，初始化新结点并链入，最后将尾指针移动至新结点，完成入队。

      出队，即为把头结点之后的元素摘下，p指向将要摘下的结点，操作为：p=Q->rear->next->next;并且保存结点中的数据。这里需要注意的是，当队列只有一个结点时，需要将p结点出队，此时需要将队尾指针指向头结点。否则摘下结点p，释放被删结点。

2.概要设计：

函数	作用
InitQueue()	置空队
EmptyQueue()	判空队
EnQueue()	入    队
DeQueue()	出     队

3.源代码（算法）：

首先定义链队结构：

  //先定义链队结构
    typedf struct queuenode{        //结点类型的定义 
	     Datetype data;
	     struct queuenode *next;
	} QueueNode；
	typedef struct{      //只设一个指向队尾元素的指针 
		queuenode *rear;
	}LinkQueue; 

置空队：

//置空队
	void InitQueue(LinkQueue *Q)
	{                    //置空队：就是使头结点成为队尾元素 
		QueueNode *s;
		Q->rear=Q->rear->next;      //将队尾指针指向头结点
		while(Q->rear!=Q->rear->next)  //当队列非空，将队中元素逐个出队 
		{
			s=Q->raer->next;
			Q->rear->next=s->next;
			free(s);
		}         //回收结点空间 
	 } 
	 

判空队：

 //判队空
	 int EmptyQueue(LinkQueue *Q)
	 {                     
	 	return Q->rear->next==Q->rear; //判队空，当头结点的next指针指向自己时为空队 
	  } 

入队：
 

//入队
	  void EnQueue(LinkQueue *Q,Datatype x)   //入队，也就是在尾节点 处插入元素 
	  {
	  	QueueNode *p=(QueueNode *)malloc(sizeof(QueueNode));  //申请新结点 
	  	p->data=x;p->next=Q->rear->next;       //初始化新结点并链入 
		Q-rear->next=p;
		Q->rear=p;                  //将尾指针移至新结点 
	   } 

出队：

// 出队
	Datatype DeQueue(LinkQueue *Q)     //出队，把头结点之后的元素摘下 
	{
		Datatype t;
		QueueNode *P;
		if(EmptyQueue(Q))
		    Error("Queue underflow");
		p=Q->rear->next->next;            //p指向将要摘下得结点 
		x=p->data;                        //保存结点中的数据 
		if(p==Q->rear)                    //当队列中只有一个结点时，p结点出队后，要将队尾指针指向头结点 
		{
			Q->rear=Q->rear->next;Q->rear->next=p->next;
		}
		else
		    Q->rear->next=p->next;
		free(p);                            //摘下结点p 
		return x;                           //释放被删结点 
	 }