[数据结构与算法]数据结构详解(其五) 队列

????????实现队列可选用链表和数组，在这里选用的是链表（方便删除），且为了提高尾插效率，在队列结构体里加入了一个指向队尾的尾指针。

?Queue.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>

typedef int QDatatype;

typedef struct QueueNode//定义队列结点结构体
{
	QDatatype data;
	struct QueueNode* next;
}QNode;

typedef struct Queue//队列结构体，用于记录头尾结点
{
	QNode* head;
	QNode* tail;
}Queue;

void QueueInit(Queue* pq);//初始化函数
void QueueDestroy(Queue* pq);//销毁函数

void QueuePush(Queue* pq, QDatatype x);//插入
void QueuePop(Queue* pq);//删除

QDatatype QueueFront(Queue* pq);//取出队头的数据

bool QueueEmpty(Queue* pq);//判断队列是否为空
int QueueSize(Queue* pq);//计算队列长度

?Queue.c

#include"Queue.h"

void QueueInit(Queue* pq)//初始化函数（用于初始化队列结构体）
{
	assert(pq);//防御性检查，传入队列结构体不应为空

	pq->head = pq->tail = NULL;
}

void QueueDestroy(Queue* pq)//销毁函数
{
	assert(pq);//防御性检查，传入队列结构体不应为空
	
	QNode* cur = pq->head;//记录当前要删除的结点
	while (cur)//遍历队列链表中的每个结点，依次删除
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}
	//链表类型的数据结构销毁时一定要 遍历每个结点 ，依次free掉
	pq->head = pq->tail = NULL;//置空，防止野指针
}


void QueuePush(Queue* pq, QDatatype x)//插入（尾插）
{
	assert(pq);//防御性检查，传入队列结构体不应为空
	
	//建立新的结点
	QNode* newnode = (QNode*)malloc(sizeof(QNode));//注意sizeof()的大小,传入的如果是指针就只有8个字节
	if (newnode == NULL)
	{
		printf("malloc fail!\n");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;

	//如果队列为空,更新头尾结点
	if (pq->head == NULL)
	{
		pq->head = pq->tail = newnode;
	}
	else//如果队列不为空，尾插
	{
		pq->tail->next = newnode;//尾插
		pq->tail = newnode;//更新尾结点
	}
}

void QueuePop(Queue* pq)//删除(头删)
{
	assert(pq);//防御性检查，传入队列结构体不应为空
	assert(!QueueEmpty(pq));//队列为空，不支持删除

	//当队列仅剩下一个结点时，删除后要，使头尾指针置空,以防止野指针
	if (pq->head->next == NULL)
	{
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	else//当队列还有多个结点时，头删
	{
		QNode* next = pq->head->next; //保存第二个结点
		free(pq->head);//释放头结点
		pq->head = next;//更新头结点
	}
}


QDatatype QueueFront(Queue* pq)//取出队头的数据
{
	assert(pq);//防御性检查，传入队列结构体不应为空
	assert(!QueueEmpty(pq));//队列为空，不支持取数据
	return pq->head->data;
}

bool QueueEmpty(Queue* pq)//判断队列是否为空
{
	assert(pq);//防御性检查，传入队列结构体不应为空

	return pq->head == NULL;
}

int QueueSize(Queue* pq)//计算队列长度
{
	assert(pq);//防御性检查，传入队列结构体不应为空

	int size = 0;

	//遍历队列链表中的每个结点，计算链表长度
	QNode* cur = pq->head;
	while (cur)
	{
		++size;
		cur = cur->next;
	}

	return size;
}

QueueTest.c(测试用例)?

#include"Queue.h"

int main()
{
	Queue q;
	QueueInit(&q);

	QueuePush(&q, 1);
	QueuePush(&q, 2);
	QueuePush(&q, 3);

	printf("%d\n", QueueSize(&q));

	while (!QueueEmpty(&q))
	{
		printf("%d ", QueueFront(&q));
		QueuePop(&q);
	}
	putchar(10);

	QueueDestroy(&q);

	return 0;
}