追梦之旅【数据结构篇】——详解C语言实现链队列

   
😎博客昵称：博客小梦
😊最喜欢的座右铭：全神贯注的上吧！！！
😊作者简介：一名热爱C/C++，算法等技术、喜爱运动、热爱K歌、敢于追梦的小博主！
😘博主小留言：哈喽！😄各位CSDN的uu们，我是你的博客好友小梦，希望我的文章可以给您带来一定的帮助，话不多说，文章推上！欢迎大家在评论区唠嗑指正，觉得好的话别忘了一键三连哦！😘

前言🙌

    哈喽各位友友们😊，我今天又学到了很多有趣的知识，现在迫不及待的想和大家分享一下！😘我仅已此文，手把手带领大家详解C语言实现链队列~ 结合链表的相关算法，根据队列先进先出的结构特点，实现我们链队列。都是精华内容，可不要错过哟！！！😍😍😍

整体实现内容分析💞

首先先编写我们的Queue.h文件的内容，将需要的头文件和需要实现的功能函数做个声明。然后是Queue.c文件的编写，主要是针对各个功能函数的一一实现，最后是Test.c文件的编写，测试我们功能函数是否有问题。

预备小知识🙌

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

队列的结构示意图：

1.链队列头文件编写🙌

头文件的编写的整体思路分析：

这里是有关头文件的编写和各种功能函数的声明，首先用typedef关键字给存储数据类型取别名，这样做的好处是以后想要改变队列的数据类型只需修改typedef int QDataType;里的int即可。定义一个结构体，包括next指针和data。然后是各个功能函数声明

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>typedef int QDataType;
typedef struct QueueNode
{struct QueueNode* next;QDataType data;
}QNode;typedef struct Queue
{QNode* head;QNode* tail;
}Queue;
//初始化
void QueueInit(Queue* pq);
//销毁
void QueueDestory(Queue* pq);
//队尾入
void QueuePush(Queue* pq, QDataType);
//队头出
void QueuePop(Queue* pq);
//队头元素
QDataType QueueFront(Queue* pq);
//队尾元素
QDataType QueueBack(Queue* pq);
//队列元素个数
int QueueSize(Queue* pq);
//判空
bool QueueEmpty(Queue* pq);

2.链队列功能文件（Queue.c ）编写：🙌

1）初始化函数实现

编写的整体思路分析：

先用assert确保pq指针的有效性，然头尾指针置为空。

//初始化
void QueueInit(Queue* pq)
{assert(pq);pq->head = pq->tail = NULL;
}

2）销毁函数实现

编写的整体思路分析：

先用assert确保pq指针的有效性，先定义一个指针cur记录head指针的位置，然后用while循环进行一个个删除：先定义一个next指向cur指针指向的下一个队列元素，然后删掉cur指向的元素，再让cur移动到下一个。

//销毁
void QueueDestory(Queue* pq)
{assert(pq);QNode* cur = pq->head;while (cur){QNode* next = cur->next;free(cur);cur = next;}pq->head = pq->tail = NULL;}

3）队尾插入元素函数实现

编写的整体思路分析：

先用assert确保pq指针的有效性，用malloc函数申请空间，用if语句来判断空间是否开辟失败。然后让newnode->next置为空，把数据放进去。如果是一开始时为空的，则让pq->head = pq->tail = newnode;如果不为空，则让之前的tail指向的节点与新节点相连。

//队尾入
void QueuePush(Queue* pq, QDataType x)
{assert(pq);QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){printf("malloc fail\n");exit(-1);}newnode->data = x;newnode->next = NULL;if (pq->tail == NULL){pq->head = pq->tail = newnode;}else{pq->tail->next = newnode;pq->tail = newnode;

4）队头删除元素函数实现

编写的整体思路分析：

用assert确保pq指针的有效性，如果队列为空，就不用进行队头出的操作，如果执行则报错。先用next指针指向首结点的下一个节点 。然后删掉首节点，再让head指针指向next位置。删完后，将尾指针置为NULL

//队头出
void QueuePop(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));QNode* next = pq->head->next;free(pq->head);pq->head = next;if (pq->head == NULL){pq->tail = NULL;}
}

5）获取队头元素函数实现

编写的整体思路分析：

先用assert确保pq指针的有效性，如果队列为空，就不用进行此操作。然后直接返回首节点数据即可。

//队头元素
QDataType QueueFront(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->head->data;
}

6）获取队尾元素函数实现

编写的整体思路分析：

先用assert确保pq指针的有效性，如果队列为空，就不用进行此操作。然后直接返回尾节点数据即可。

//队尾元素
QDataType QueueBack(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->tail->data;}

7）获取队列元素个数的函数实现

编写的整体思路分析：

先用assert确保pq指针的有效性，定义cur指向head的位置。利用while循环，先让Size加1，然后让cur指向下一个，知道cur为空时结束循环，返回Size大小就是队列元素的个数。

//队列元素个数
int QueueSize(Queue* pq)
{assert(pq);int Size = 0;QNode* cur = pq->head;while (cur){Size++;cur = cur->next;return Size;}
}

8）判空函数实现

编写的整体思路分析：

先用assert确保pq指针的有效性，然后pq->head == NULL为真，则返回1，为假则返回0；

//判空
bool QueueEmpty(Queue* pq)
{assert(pq);return pq->head == NULL;
}

3.链队列测试文件编写🙌

（3）Tese.c文件的编写。
#define _CRT_SECURE_NO_WARNINGS 1
#include"Queue.h"
void test()
{Queue q;QueueInit(&q);QueuePush(&q, 1);QueuePush(&q, 2);QueuePush(&q, 3);QueuePush(&q, 4);printf("队首元素：%d\n", QueueFront(&q));printf("队尾元素：%d\n", QueueBack(&q));printf("队列元素的个数：%d\n", QueueBack(&q));printf("队列元素输出：");while (!QueueEmpty(&q)){QDataType* front = QueueFront(&q);printf("%d", front);QueuePop(&q);}printf("\n");QueueDestory(&q);
}
int main()
{test();return 0;
}

功能测试结果展示图：

总结撒花💞

   本篇文章旨在分享详解C语言实现链队列。希望大家通过阅读此文有所收获！本次关于队列的实现相对于之前链表和顺序表的实现简单一点，实现起来的算法和之前的栈是相似的，但结构特点与栈是相反的。指针的指向没有那么复杂，主要是对入队列和出队列的功能实现。但也有很多地方需要注意的。比如说，野指针的问题，动态开辟的空间一定要free掉，并且把指针置为NULL。用动态实现，相对于静态实现还比较灵活，也能对空间有很大的节省。
   😘如果我写的有什么不好之处，请在文章下方给出你宝贵的意见😊。如果觉得我写的好的话请点个赞赞和关注哦~😘😘😘