😏专栏导读
👻作者简介：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文章来源：https://www.toymoban.com/news/detail-475868.html
#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，如果你觉得这一期对你有帮助你可以一键三连鸭！！！！下一期会继续更细数据结构！！文章来源地址https://www.toymoban.com/news/detail-475868.html
到了这里，关于初阶数据结构之队列的实现（六）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
