1.队列的链式存储结构

用链式存储结构存储的队列称为链队列，它是一个仅在表头删除结点和在表尾插入结点的单链表。因此，在链队列中需要使用两个指针：头指针front和尾指针rear。用front指向链队列的队头，用rear指向链队列的队尾。如图3-8所示。

为操作方便，在链队列中添加一个头结点，该结点不存储任何元素，并让头指针指向头结点。可见空的链队列的判定条件是头指针和尾指针均指向头结点。

链队列的类型LinkQueue可定义如下：

	struct node { /*链队列的结点类型*/
	ElemType data ; /*链队列结点的数据域*/
	struct node *next; /*链队列结点的指针域*/
	};
	struct node *front,*rear; /*front和rear分别为链队列的头指针和尾指针*/

2.链队列的基本操作

假设在链队列中，front、rear均为node类型的全局变量。

（1）链队列的初始化

算法步骤：

1.首先产生一个头结点，将其后继指针设置为空；

2.将队头和队尾指针均指向该结点。

链队列的初始化算法

	void InitQueue() /*初始化链队列*/
	{
	struct node *p=malloc(sizeof(struct node));/*生成新结点p*/
	p->next=NULL; /*使新结点的指针域为空*/
	front=rear=p; /*队头和队尾指针均指向新结点*/
	}

（2）判队空

判断队列是否为空，也就是判断队头、队尾指针是否相等。

链队列判队空算法

	int QueueEmpty()
	{
	if(front==rear) return 1; /* 如果链队列为空，则返回1 */
	else return 0; /* 否则返回0 */
	}

（3）入队

算法要点：

1.生成一个新结点p，给新结点的数据域和指针域分别赋值；

2.使新结点成为新的队尾结点；

3.修改队尾指针rear，使rear指向新的队尾结点。

链队列入队算法

	void InQueue(ElemType x)
	{
	struct node *p;
	p=malloc(sizeof(struct node)); /*生成新结点p*/
	p->data=x; /*给新结点的数据域赋值*/
	p->next=NULL; /*给新结点的指针域赋值*/
	rear->next=p; /*新结点成为新的队尾结点*/
	rear=p; /*让队尾指针指向新的队尾结点*/
	}

（4）出队

算法要点：

1.首先检查链队列是否为空，若为空队列，则进行“下溢出”错误处理；

2.保存队头结点的值；

3.修改队头指针，使其指向队列的第二个结点，建立新的链接队列；

4.删除原队头结点；

5.返回原队头结点的信息。

链队列出队算法

	ElemType OutQueue()
	{
	int x;
	if(front==rear){ /*检查链队列是否为空*/
	printf("队列下溢错误！\n");
	exit(1); /*若队空不能出队，则退出运行*/
	}
	else {
	struct node *p=front->next; /*用指针变量p指向队列的第一个结点*/
	x=p ->data; /*用x暂存第一个结点数据域*/
	front->next=p->next; /*修改队头指针，指向下一个结点*/
	if(p->next==NULL) rear=front; /*若队列已空则修改队尾指针*/
	free(p); /*回收原队头结点*/
	return x; /*返回原队头元素的值*/
	}
	}