动态链式队列详解及完整实例演示

队列

队列(Queue)是只允许在一端(队尾rear)进行插入，而在另一端(队头front)进行删除的运算受限的线性表。它是一种可以实现“先进先出”(FIFO)的存储结构。队列在具体应用中通常用链表或者数组来实现，因此我们也常常将队列分为静态队列(数组队列)，链式队列(主要以链表方式进行操作)。当队列中没有元素时，我们称之为空队列。一般队列的存储结构是顺序存储，当队列的存储结构是链式存储结构(即队列中每个元素都包含一个指向其后继的指针，最后一个指针元素也就是尾结点的指针域为NULL)时，就是链式队列了。和栈不同，队列通常需要对其两端进行操作，而栈一般只需对通过栈顶指针进行操作即可。

对链式队列的相关操作思路

typedef struct Node
{
	int data;//数据域
	struct Node *pNext;//指针域
}NODE,*PNODE;
typedef struct Queue
{
	PNODE pFront;//始终指向头结点（没有实际含义的结点）
	PNODE pRear;//始终指向尾结点（注意：尾结点数据域含有效数据，但指针域为空）
}QUEUE,*PQUEUE;//PQUEUE等价于struct Queue*

伪算法：

1.初始化。初始化的目的主要是为了造空队列

void init(PQUEUE pQ)//造空队列

{

造头结点；

让尾结点指向头结点；

将尾结点指针域赋为NULL；

return;

}

2.入队

void enter(PQUEUE pQ,int val)

{

造新节点；

将val赋给新节点的数据域；

将新节点的指针域赋为NULL；

· 将尾结点的指针域指向新节点；

使该新结点成为尾结点；

}

3.出队

bool del(PQUEUE pQ)

{

找到第一个有效节点；

判断队列是否为空；

不为空时输出有效节点的数据域；

找出第一个有效节点，并让指向第一个结点的指针指向第二个；

释放第一个结点所占内存；

注意：若队列中只有一个元素时，将头结点的地址赋给队尾，让尾结点成为无效结点；

}

4.遍历：在输出尾结点的值后，跳出循环。当然前提先要判断该队列是否为空；

5. 清空：先判断该队列是否为空；再找出第一个有效结点，用一个临时变量保存下一个有效节点的地址，并让队头(队首)指向该地址，然后释放第一个结点所占内存，最后将下一个结点的地址赋给该队列的头结点（即让头结点指向下一个结点的地址），如此进行循环直到队尾删除完（只剩头结点，再让尾结点指向头结点，这样相当于又完成了一次对该链式队列的初始化）。

实例说明：

#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
typedef struct Node
{
	int data;//数据域
	struct Node *pNext;//指针域
}NODE,*PNODE;
typedef struct Queue
{
	PNODE pFront;//始终指向头结点（没有实际含义的结点）
	PNODE pRear;//始终指向尾结点（注意：尾结点数据域含有效数据，但指针域为空）
}QUEUE,*PQUEUE;//PQUEUE等价于struct Queue*
void init(PQUEUE);//初始化队列
void enter(PQUEUE,int);//入队
bool del(PQUEUE);//出队
bool traverse(PQUEUE);//遍历
int length(PQUEUE);//求链式队列长度
bool clear(PQUEUE);//清空链式队列

int main()
{
	QUEUE Q;
	init(&Q);
	enter(&Q,1);
	enter(&Q,2);
	enter(&Q,3);
	traverse(&Q);
	del(&Q);
    traverse(&Q); 
    printf("队列长度为：%d\n",length(&Q));
	clear(&Q);
	printf("清空后");
    traverse(&Q);  
	return 0;
}
void init(PQUEUE pQ)//造空队列
{
	pQ->pFront=(PNODE)malloc(sizeof(NODE));//造头结点，并让pFront指向该头结点
	if(NULL==pQ->pFront)
	{
		printf("动态内存分配失败！\n");
		exit(-1);//终止程序运行
	}
	pQ->pRear=pQ->pFront;
    pQ->pFront->pNext=NULL;
	return; 
}
void enter(PQUEUE pQ,int val)
{
	PNODE pNew=(PNODE)malloc(sizeof(NODE));//造新临时结点
	if(NULL==pNew)
	{
		printf("动态内存分配失败！\n");
		exit(-1);//终止程序运行
	}
	pNew->data=val;
	pNew->pNext=NULL;
	pQ->pRear->pNext=pNew;
	pQ->pRear=pNew;
	return;
}
bool del(PQUEUE pQ)//出队
{
	PNODE p=pQ->pFront->pNext;//让p指向队头的第一个有效节点	
	if(NULL==p)
	{
		printf("队列为空，出队失败！\n");
		return false;
	}
	else
	{
		printf("出队元素的值为：%d\n",p->data);
		if(p==pQ->pRear)//如果是队尾，说明只有一个有效结点
			pQ->pRear=pQ->pFront;//因为pFront始终指向的是头结点的地址，这里将头结点的地址赋给队尾(此时队尾成为无效结点)
		pQ->pFront->pNext=p->pNext;
		free(p);
		p=NULL;
		return true;
	}
}
bool traverse(PQUEUE pQ)
{
	PNODE p=pQ->pFront;
	if(NULL==p->pNext)
	{
		printf("队列为空，遍历失败！\n");
		return false;
	}
	printf("队列元素有：");
	while(p!=pQ->pRear)
	{
		p=p->pNext;
		printf("%d  ",p->data);
	}
	printf("\n");
    return true; 
}
int length(PQUEUE pQ)
{
	int len=0;
	PNODE p=pQ->pFront;
	if(NULL==p->pNext)
	{
		printf("队列为空！\n");
		return 0;
	}
	while(p!=pQ->pRear)
	{
		p=p->pNext;
		++len;
	}
	return len;
}
bool clear(PQUEUE pQ)
{
	PNODE p=pQ->pFront->pNext,q;//让p指向队头的第一个有效节点	
	if(NULL==p)
	{
		printf("队列为空，清空失败！\n");
		return false;
	}
	else
	{
		while(p!=pQ->pRear)
		{
			q=p->pNext;//用q来保存p的下一个结点的地址
			pQ->pFront=q;
			free(p);
			p=q;
		}
		pQ->pRear=pQ->pFront;
        return true; 
	}	
}

注意：

1. 在上篇栈中，压栈(进栈)的时候pTop指向了第一个有效结点，而该链式队列中入队的时候pFront仍然还是指向了队列初始化是的头结点(没有实际含义的结点)。

2.该链式队列中，pRear始终指向尾结点，队尾数据域为有效数据，但其指针域为空；pFront始终指向头结点(附结头结点的目的和上篇栈中的一样，为了方便对链式进行操作)。如：PNODE p=pQ->pFront->pNext;就可以让p指向队首(第一个)有效结点