数据结构队列的实现

在这里插入图片描述
本章介绍数据结构队列的内容，我们会从队列的定义以及使用和OJ题来了解队列，话不多说，我们来实现吧

队列

1。队列的概念及结构
队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出
FIFO(First In First Out) 入队列：进行插入操作的一端称为队尾出队列：进行删除操作的一端称为队头。
我们来看一下下面的这张图，让我们更好的理解它
在这里插入图片描述
我们从队尾入，队头出，只能是这样入栈和出栈

2。队列的实现
队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数
组头上出数据，效率会比较低。

那队列的实现我们是用链式结构来实现的，因为用数组下标的话，出栈的时候要往前挪动数据，会更麻烦，这样队列的意义就下降了，所以我们这里用的方法是链式结构。

typedef int QueueDataType;
typedef struct QueueNode
{QueueDataType* next;QueueDataType data;
}QueueNode;typedef struct Queue
{QueueDataType* head;QueueDataType* tail;
}Queue;

这里我们定义的结构体Queue有很大的作用，因为队列不是像单链表那样，队列是有它的特点的，其中最大的一个特点就是入栈只能从尾入，出栈就是头出，所以我们在这里定义head和tail有很大的作用，定义在结构体当中会方便不少，那我们现在继续往下看我们的接口函数吧。

给大家看一下下面实现队列的接口函数，然后我们一步一步的来实现他们

// 初始化队列
void QueueInit(Queue* q);
// 队尾入队列
void QueuePush(Queue* q, QueueDataType data);
// 队头出队列
void QueuePop(Queue* q);
// 获取队列头部元素
QueueDataType QueueFront(Queue* q);
// 获取队列队尾元素
QueueDataType QueueBack(Queue* q);
// 获取队列中有效元素个数
int QueueSize(Queue* q);
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
bool QueueEmpty(Queue* q);
// 销毁队列
void QueueDestroy(Queue* q);

队列的初始化

void QueueInit(Queue* q);

初始化我们初始的是结构体Queue中的内容

void QueueInit(Queue* q)
{assert(q);q->head = q->tail = NULL;
}

首先要判断传过来的指针是否是为空，然后将头指针和尾指针都置为NULL。

销毁队列

void QueuePush(Queue* q, QueueDataType data)

首先我们要创造一个节点将它放入，创造节点的结构体就是QueueNode，然后我们要更新后面节点中的head和tail，这里大家肯定有疑问，我们竟然是更新指针，那我们应该传指针的地址才能起到作用，一级指针只能改变结构体的内容，那我们在这里传的话，难道不会产生问题吗？答案是不会，我们的结构体中放的就是指针，那我们只需要改变结构体的内容，就是head和tail就行，竟然是这样的话，我们传一个一级指针就可以起到我们的作用，所以传的是一级，那现在我们在插入函数中先创造一个节点，因为只能从队列的尾插入，而且有了这个指针，我们就不需要像单链表那样再去找尾，我们每次插入都会更新尾。

void QueuePush(Queue* q, QueueDataType data)
{assert(q);QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));if (newnode == NULL){printf("malloc fail\n");exit(-1);}newnode->data = data;newnode->next = NULL;if (q->head == NULL){q->head = q->tail = newnode;}else{q->tail->next = newnode;q->tail = newnode;}
}

有了入栈就有出栈，出栈的话是从我们的队列最开始的地方出队，我们来实现一下吧！

void QueuePop(Queue* q)
{assert(q);assert(!QueueEmpty(q));QueueNode* headnext = q->head->next;free(q->head);q->head = headnext;}
/

这里的空是因为如果我们的队列都是空的话，我们哪里还有数据进行删除呢
所以要先检查一下是不是为空，那接着我们把这个函数也实现一下吧

bool QueueEmpty(Queue* q)
{assert(q);return q->head == NULL;
}

这个很好理解，如果为空就代表一个数也没有，那我们就不能再对队列进行操作了，那再来看我们下面的接口函数吧。

// 获取队列头部元素
QueueDataType QueueFront(Queue* q)
{assert(q);return q->head->data;
}

有头就有尾，希望我们的人生也是
那我再来实现一下取尾的接口吧

QueueDataType QueueBack(Queue* q)
{assert(q);return q->tail->data;
}

我们继续往下走，实现一下我们后面的接口函数，这些基本上都很简单，我就也不再解释了，看代码就能理解的

int QueueSize(Queue* q)
{assert(q);int count = 0;QueueNode* cur = q->head;while (cur){count++;cur = cur->next;}return count;
}

销毁队列

void QueueDestroy(Queue* q)
{while (!QueueEmpty(q)){QueueNode* headnext = q->head->next;free(q->head);q->head = headnext;}}

统计我们队列节点的数量我们遍历一遍就可以实现了，定义一个cur指针进行遍历，那其他的我们也都讲完了，后面分享栈和队列的OJ题给大家，看完之后对队列有了更深的理解

完整代码

#include"Queue.h"// 初始化队列
void QueueInit(Queue* q)
{assert(q);q->head = q->tail = NULL;
}
// 队尾入队列
void QueuePush(Queue* q, QueueDataType data)
{assert(q);QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));if (newnode == NULL){printf("malloc fail\n");exit(-1);}newnode->data = data;newnode->next = NULL;if (q->head == NULL){q->head = q->tail = newnode;}else{q->tail->next = newnode;q->tail = newnode;}
}
// 队头出队列
void QueuePop(Queue* q)
{assert(q);assert(!QueueEmpty(q));QueueNode* headnext = q->head->next;free(q->head);q->head = headnext;}
// 获取队列头部元素
QueueDataType QueueFront(Queue* q)
{return q->head->data;
}
// 获取队列队尾元素
QueueDataType QueueBack(Queue* q)
{return q->tail->data;
}
// 获取队列中有效元素个数
int QueueSize(Queue* q)
{assert(q);int count = 0;QueueNode* cur = q->head;while (cur){count++;cur = cur->next;}return count;
}
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
bool QueueEmpty(Queue* q)
{assert(q);return q->head == NULL;
}
// 销毁队列
void QueueDestroy(Queue* q)
{while (!QueueEmpty(q)){QueueNode* headnext = q->head->next;free(q->head);q->head = headnext;}}


#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>typedef int QueueDataType;
typedef struct QueueNode
{QueueDataType* next;QueueDataType data;
}QueueNode;typedef struct Queue
{QueueDataType* head;QueueDataType* tail;
}Queue;// 初始化队列
void QueueInit(Queue* q);
// 队尾入队列
void QueuePush(Queue* q, QueueDataType data);
// 队头出队列
void QueuePop(Queue* q);
// 获取队列头部元素
QueueDataType QueueFront(Queue* q);
// 获取队列队尾元素
QueueDataType QueueBack(Queue* q);
// 获取队列中有效元素个数
int QueueSize(Queue* q);
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
bool QueueEmpty(Queue* q);
// 销毁队列
void QueueDestroy(Queue* q);