【数据结构与算法（C 语言）】队列 --链队列

1. 前言

1.1 定义

队列：一种先进先出(first in first out,缩写 FIFO)的线性表。

队尾：允许插入的一端（rear）
队头：允许删除的一端 (front）
用链表标识的队列简称 链队列

1.2 队列示意图

在这里插入图片描述

2. 链队列存储结构和函数说明

2.1 队列结点

typedef struct QNode{
	QElemType data;
	struct QNode * next;
}QNode;  	//定义队列的结点

2.2 队列类型

typedef struct{
	QNode * front;  //队头指针 
	QNode * rear;	//队尾指针
	int length; 
}LinkQueue;

基本操作原型:

Status InitQueue(LinkQueue * queue);   /*初始化队列,申请一个头结点的内存*/
void DestroyQueue(LinkQueue *queue);   /*销毁队列*/
Status ClearQueue(LinkQueue * queue);  //将队列queue清空
Status QueueEmpty(LinkQueue queue);    //判断队列是否为空
Status GetHead(LinkQueue queue ,QElemType * e); //获取队列第一个元素
int QueueLength(LinkQueue queue);		//返回队列长度
Status EnQueue(LinkQueue  * queue, QElemType e);	//元素e 插入队列queue
Status DeQueue(LinkQueue * queue ,QElemType * e);  //若队列queue不空，则删除Q的队头元素，用e返回其值，并返回 OK；否则返回ERROR
Status QueueTraverse(LinkQueue queue,void (*visit)())//遍历队列，对队列的每个元素调用Visit函数

3. 完整代码

#include <stdio.h>
#include <stdlib.h>

#define TRUE  1
#define FALSE 0
#define OK    1
#define ERROR 0
#define MAXSIZE 30

typedef  int Status;

typedef  int QElemType; //定义元素类型为整型

typedef struct QNode{
	QElemType data;
	struct QNode * next;
}QNode;  	//定义队列的结点

typedef struct{
	QNode * front;  //队头指针 
	QNode * rear;	//队尾指针
	int length; 
}LinkQueue;     //定义一个队列类型 


Status InitQueue(LinkQueue * queue);   /*初始化队列,申请一个头结点的内存*/
void DestroyQueue(LinkQueue *queue);   /*销毁队列*/
Status ClearQueue(LinkQueue * queue);  //将队列queue清空
Status QueueEmpty(LinkQueue queue);    //判断队列是否为空
Status GetHead(LinkQueue queue ,QElemType * e); //获取队列第一个元素
int QueueLength(LinkQueue queue);		//返回队列长度
Status EnQueue(LinkQueue  * queue, QElemType e);	//元素e 插入队列queue
Status DeQueue(LinkQueue * queue ,QElemType * e);  //若队列queue不空，则删除Q的队头元素，用e返回其值，并返回 OK；否则返回ERROR
Status QueueTraverse(LinkQueue queue,void (*visit)());//遍历队列，对队列的每个元素调用Visit函数

/*初始化队列,申请一个头结点的内存*/
Status InitQueue(LinkQueue * queue)
{
	queue->front = (QNode*) malloc(sizeof(QNode)); //申请一个队列结点作为头结点的内存地址给 队头指针；
	if(queue->front == NULL)
		return FALSE;
	queue->front->next = NULL;		
	queue->rear=queue->front;
	queue->length=0;
	return TRUE;
}

/*销毁队列*/
void DestroyQueue(LinkQueue *queue)
{
	ClearQueue(queue);
	free(queue->front);
	queue->front = queue->rear=NULL;
	queue->length=0;
}

//将队列queue清空
Status ClearQueue(LinkQueue * queue)
{
	QNode * curNode;
	while((curNode = queue->front->next) == NULL)
	{
		queue->front->next=curNode->next;	
		free(curNode);
	}
	queue->rear = queue->front;
	queue->length = 0;
	return OK;	
}

//判断队列是否为空
Status QueueEmpty(LinkQueue queue)
{
	return queue.front == queue.rear? TRUE:FALSE; 
}

//获取队列第一个元素
Status GetHead(LinkQueue queue ,QElemType * e)
{
	if(queue.length == 0)
		return FALSE;
	*e=queue.front->next->data;
	return TRUE;
}


//返回队列长度
int QueueLength(LinkQueue queue)
{
	return queue.length;
}


//元素e 插入队列queue
Status EnQueue(LinkQueue  * queue, QElemType e)
{
	QNode * curNode=(QNode*) malloc(sizeof(QNode));
	if(!curNode)
		return FALSE;
	curNode->data=e;
	curNode->next=NULL;
	queue->rear->next = curNode;
	queue->rear =curNode;
	queue->length++;
	return TRUE;
}

//若队列queue不空，则删除Q的队头元素，用e返回其值，并返回 OK；否则返回ERROR
Status DeQueue(LinkQueue * queue ,QElemType * e)
{
	QNode * curNode;
	if(queue->length == 0)
		return FALSE;
	curNode = queue->front->next;
	*e=curNode->data;
	queue->front->next=curNode->next;
	free(curNode);
	queue->length--;
	return TRUE;
}
void Visit(QElemType e)
{
	printf("%3d",e);
}
//遍历队列，对队列的每个元素调用Visit函数
Status QueueTraverse(LinkQueue queue,void (*visit)())
{
	QNode * curNode=queue.front->next;
	while(curNode)
	{
		visit(curNode->data);
		curNode=curNode->next;
	}
}

int main()
{
	QElemType e;
	LinkQueue queue;
	InitQueue(&queue);
	printf("队头分别插入数字3、4、5后:");
	EnQueue(&queue,3);
	EnQueue(&queue,4);
	EnQueue(&queue,5);
	QueueTraverse(queue,Visit);
	printf("\n删除队头数字后:");
	DeQueue(&queue,&e);
	QueueTraverse(queue,Visit);	
	printf("\n清空队列");
	ClearQueue(&queue);
	printf("\n队列长度:%d\n",QueueLength(queue));
	DestroyQueue(&queue);
	getchar();
	return 0;
}