😏专栏导读
👻作者简介：M malloc，致力于成为嵌入式大牛的男人
👻专栏简介：本文收录于 初阶数据结构，本专栏主要内容讲述了初阶的数据结构，如顺序表，链表，栈，队列等等，专为小白打造的文章专栏。
👻相关专栏推荐：LeetCode刷题集，C语言每日一题。
🤖文章导读
本章我将详细的讲解关于栈的知识点
🙀什么是队列？
队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out) 入队列：进行插入操作的一端称为队尾 出队列：进行删除操作的一端称为队头
队列的两种概念：
1、入队列：进行插入操作的一端称为队尾
2、出队列：进行删除操作的一端称为队头
🙀画图描述
如下图所示，就是入队列出队列全过程啦！关于队列有一个特点就是先进先出不要忘记啦！
关于队列的指示就是，先进先出，队尾进，队头出。
😳队列的代码实现及其各类讲解
😳队列实现的理论过程
队列也可以用数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低。
队列的初始化代码实现及其讲解
😳队列的初始化
首先我们先定义一个结构体类型(这里我们选择使用的是链式队列)：
typedef int QDatatype; typedef struct QueueNode { struct QueueNode* next; QDatatype data; }QNode; typedef struct Queue { QNode* phead; QNode* ptail; int size; }Queue;
第一段结构体类型其实是定义这个节点的类型，第二个结构体定义的是这个队列类型。
队列的初始化
代码如下：
void QueueInit(Queue* pq) { assert(pq); pq->phead = NULL; pq->ptail = NULL; pq->size = 0; }
首先assert是断言，当我们这个队列为空的时候，我们程序就会报错，直接结束进程。相对应的初始化，如果指针的话我们赋值为NULL就行啦！
😳队列的销毁代码实现及其讲解
因为我们用的是链式队列，而不是数组队列，所以对于每一个节点我们都应该释放掉，因为malloc开辟的是在堆上开辟的。那么具体的是指什么时候呢？
首先：这是我们最开始的情况
我们要记住，在遍历的过程中永远不要动最初的指针，我们一定要把它赋值给一个指针，让他遍历，我们应该从头开始删除，于是就有了下图，我们把head赋给了cur
如下图所示，此时的next值存储的是cur->next，当我们在遍历的过程中，我们把cur，free掉之后，我们就可以通过next找到下一个我们想要销毁的指针，直到这一片位置全被销毁位置！
void QueueDestroy(Queue* pq) { assert(pq); QNode* cur = pq->phead; while (cur) { QNode* next = cur->next; free(cur); cur = next; } pq->phead = pq->ptail = NULL; pq->size = 0; }
😳队列的插入代码实现及其讲解
在实现代码的时候，我们要先考虑，我们应该怎么插入。此时我们会发现插入其实很像单链表的头插，我们可以理解为这是加入了限制条件的链表，也就是队列。
在插入的时候我们应该考虑多种情况，例如
1、此时这是一个空的队列，我们应该如何插入
2、也就是有节点的队列如何插入。
好啦知道了我们要做什么了，现在我们就应该开始进行我们的画图描述啦！
1、首先我们应该先malloc一块新的节点出来，然后让他赋给链表，那我们如何知道这块队列是空的呢？这个时候，就需要来看到tail了，我们可以想象一下，如果尾结点是NULL值，那么是不是代表着此时的队列就是空的呢？是滴！
所以我们第一步就应该先判断我们的tail指针是否为空，如果为空，我们直接把新节点赋给尾指针就行了。
那么此时是不是已经有一个节点了呢？如下图所示：
接下来我们要做的操作类似于单链表的尾插操作啦！首先我们要让tail的next指向newnode，然后在把tail指针的位置移动到newnode此时的位置，并且最后再让size++
void QueuePush(Queue* pq, QDatatype x) { assert(pq); QNode* newnode = (QNode*)malloc(sizeof(QNode)); if (newnode == NULL) { perror("malloc fail\n"); return; } newnode->data = x; newnode->next = NULL; if (pq->ptail == NULL) { assert(pq->phead == NULL); pq->phead = pq->ptail = newnode; } else { pq->ptail->next = newnode; pq->ptail = newnode; } pq->size++; }
😳队列的删除代码实现及其讲解
在队列做删除操作时，我们也要知道，我们删除的时候也是从队头进行删除，其实就是头删啦。
这里我们也得考虑两种情况，例如：
1、当我们队列只有一个节点的时候，我们应该如何删除呢？
2、也就是正常情况啦，也就是多个节点的情况
如果节点只有一个的情况我们需要考虑的是，直接free掉就行啦，
但是如果有多个节点的时候，我们就需要保存下一节点的地址，当我们删除上一节点时，我们就需要把下一节点的地址赋给头结点指针就行啦，如下图所示，我们把head，free掉，此时head的指针就应该指向next处，这样就可以进行删除啦！
void QueuePop(Queue* pq) { assert(pq); assert(!QueueEmpty(pq)); if (pq->phead->next == NULL) { free(pq->phead); pq->phead = pq->ptail = NULL; } else { QNode* next = pq->phead->next; free(pq->phead); pq->phead = next; } pq->size--; }
😳队列的判空代码实现及其讲解
判空代码的实际过程其实是这样的，当头指针和尾指针都是空的时候，它就是空啦！！
bool QueueEmpty(Queue* pq) { assert(pq); return pq->phead == NULL && pq->ptail == NULL; }
😳队列的全部代码的实现
queue.h
#pragma once #include<stdio.h> #include<assert.h> #include<stdlib.h> #include<stdbool.h> typedef int QDatatype; typedef struct QueueNode { struct QueueNode* next; QDatatype data; }QNode; typedef struct Queue { QNode* phead; QNode* ptail; int size; }Queue; void QueueInit(Queue* pq); void QueueDestroy(Queue* pq); void QueuePush(Queue* pq, QDatatype x); void QueuePop(Queue* pq); QDatatype QueueFront(Queue* pq); QDatatype QueueBack(Queue* pq); int QueueSize(Queue* pq); bool QueueEmpty(Queue* pq);
queue.c
#define _CRT_SECURE_NO_WARNINGS 1 #include "Queue.h" void QueueInit(Queue* pq) { assert(pq); pq->phead = NULL; pq->ptail = NULL; pq->size = 0; } void QueueDestroy(Queue* pq) { assert(pq); QNode* cur = pq->phead; while (cur) { QNode* next = cur->next; free(cur); cur = next; } pq->phead = pq->ptail = NULL; pq->size = 0; } void QueuePush(Queue* pq, QDatatype x) { assert(pq); QNode* newnode = (QNode*)malloc(sizeof(QNode)); if (newnode == NULL) { perror("malloc fail\n"); return; } newnode->data = x; newnode->next = NULL; if (pq->ptail == NULL) { assert(pq->phead == NULL); pq->phead = pq->ptail = newnode; } else { pq->ptail->next = newnode; pq->ptail = newnode; } pq->size++; } void QueuePop(Queue* pq) { assert(pq); assert(!QueueEmpty(pq)); if (pq->phead->next == NULL) { free(pq->phead); pq->phead = pq->ptail = NULL; } else { QNode* next = pq->phead->next; free(pq->phead); pq->phead = next; } pq->size--; } QDatatype QueueFront(Queue* pq) { assert(pq); assert(!QueueEmpty(pq)); return pq->phead->data; } QDatatype QueueBack(Queue* pq) { assert(pq); assert(!QueueEmpty(pq)); return pq->ptail->data; } int QueueSize(Queue* pq) { assert(pq); return pq->size; } bool QueueEmpty(Queue* pq) { assert(pq); return pq->phead == NULL && pq->ptail == NULL; //pq->size == 0 }
总结
我是爱你们的M malloc，如果你觉得这一期对你有帮助你可以一键三连鸭！！！！下一期会继续更细数据结构！！
