本文共 3314 字，大约阅读时间需要 11 分钟。

一、链队列

1、队列的链式存储结构，其实就是线性表的单链表，只不过它只能尾进头出而已，我们把它简称为链队列。

2、为了操作上的方便，我们增加一个队头结点，一个队头指针，一个队尾指针。

3、空队列时，front和rear指针都指向头结点，如图所示

4、非空队列时，对头指针指向队头结点，队尾指针指向终端结点，如图所示

二、链队列数据结构 

typedef int QElemType;//QElemType根据实际情况而定，这里假设为inttypedef struct Qnode{	QElemType data;	struct Qnode *next;}Qnode,*QueuePtr;typedef struct //队列的链表结构{	QueuePtr front,rear;//队头、队尾指针}LinkQueue,*LinkQueuePtr;

 三、基本操作

1、队列创建

bool CreateQueue(LinkQueue *Q){	if(!Q)	{		return false;	}	Q->front = Q->rear = (QueuePtr)malloc(sizeof(Qnode));	if(!Q->front)	{		return false;	}	Q->front->next = NULL;// 队头节点指向NULL	return true;}

2、入队

bool Enqueue(LinkQueue *Q, QElemType e){	QueuePtr s = (QueuePtr)malloc(sizeof(Qnode));	if(!s)		return false;	s->data = e;	s->next = NULL;	Q->rear->next = s;//把拥有元素e新结点s赋值给队尾指针的后继	Q->rear = s;//把当前的s设置为队尾结点，rear指向s	return true;}

3、出队

//注意出队分为两种情况bool Dequeue(LinkQueue *Q, QElemType *e){	QueuePtr p = NULL;	if(!Q)		return false;		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;//使尾结点指向头结点	free(p);	return true;}

4、队列是否空

bool QueueEmpty(LinkQueue *Q) {	if(!Q)		return false;    // 头指针和尾指针位置相等，队列为空    if (Q->front == Q->rear) {        return true;    } else {        return false;    }}

5、遍历队列

bool visit(QElemType e) {    printf("%d ", e);    return true;}bool QueueTravel(LinkQueue *Q) {    QueuePtr p; // 用于遍历队列中的节点		if(!Q)		return false;    p = Q->front->next; // p指向头节点    printf("遍历队列，队中的元素是:\n");    // 当队列中还有元素    while (p) {        visit(p->data); // 打印当前节点的值        p = p->next; // p移动到队列下一个位置    }	printf("\n");    return true;}

6、获取队列长度

int QueueLength(LinkQueue *Q){	if(!Q)return -1;	QueuePtr p = Q->front;	int count = 0;	while(p->next)	{		count++;		p = p->next;	}	return count;}

7、获取队列头

bool GetHead(LinkQueue *Q, QElemType *e) {    QueuePtr p;	if(!Q)		return false;    // 队列为空，获取失败    if (Q->front == Q->rear) {        return false;    }    p = Q->front->next; // p指向队列的第一个元素    *e = p->data; // 将队列头元素的值赋值给e元素    return true;}

8、清空队列

bool ClearQueue(LinkQueue *Q) {    QueuePtr p, q; // p用来遍历队列节点，q用来指向被删除的节点	if(!Q)return true;		printf("空队列\n");	printf("清空队列\n");    Q->rear = Q->front; // 队尾指针指向队头指针    p = Q->front->next; // p指向队头指针的下一个节点    Q->front->next = NULL; // 队头指针的下一个节点指向NULL（表示删除之后的所有元素）    // 当队列中还有元素，释放头节点之后的所有节点    while (p) {        q = p; // q节点指向被删除节点        p = p->next; // p指向队列的下一个节点        free(q); // 释放q节点    }    return true;}

9、销毁队列

bool DestroyQueue(LinkQueue *Q){	if(!Q)return false;	printf("销毁队列\n");	while (Q->front) 	{        Q->rear = Q->front->next;// 队尾指针指向队头指针的下一个元素        free(Q->front); // 释放队头指针所在节点        Q->front = Q->rear; // 队头指针指向队尾指针（即原来的下一个元素）    }	return true;}

四、测试代码 及测试结果

#include
   
    #include
    
     #include"malloc.h"void main(void){		LinkQueue Lqueue;	CreateQueue(&Lqueue);	QElemType i;	for(i = 0;i < 10;i++)	{		if(false == Enqueue(&Lqueue,i)) break;		else			printf("依次入队元素：%d\n",i);	}	int len = QueueLength(&Lqueue);	printf("===========len：%d===========\n",len);	QueueTravel(&Lqueue);	QElemType e;	GetHead(&Lqueue,&e);	printf("链表头为：%d\n",e);	for(i = 0;i < 5;i++)	{		if(false == Dequeue(&Lqueue,&e)) break;		else			printf("依次出队元素：%d\n",e);	}	QueueTravel(&Lqueue);	ClearQueue(&Lqueue);	QueueEmpty(&Lqueue);	DestroyQueue(&Lqueue);	system("pause");}
    
   

转载地址：http://onxxb.baihongyu.com/