目录：
一、队列的概念及结构
二、队列的实现
1.队列的结构
2.队列的初始化
3.队列的销毁
4.队列的插入
5.队列的删除
6.统计队列的数据个数
7.判断队列是否为空
8.返回队列表头数据
9.返回队列表尾数据
10.运行展示
三、代码
一、队列的概念及结构
二、队列的实现
1.队列的结构
既然底层是单链表，那我们就先创造一个结构体表示单链表
不会单链表的可以看这个链接:https://blog.csdn.net/xpcxpt/article/details/147569114?spm=1001.2014.3001.5501
那么单链表结构如下:
因为队列需要在表尾插入数据，每次找表尾，都需要遍历链表，非常麻烦，所以我们在创建一个尾指针指向表为，这里可以创建一个结构体，来同时包含表头指针phead和表尾指针ptail:
这里加了一个size变量，用来统计个数
2.队列的初始化
初始化很简单，那么就是表头指针phead和表尾指针ptail首先都是空，并且size在初始时候为0：
3.队列的销毁
销毁要相对麻烦一点，因为这是一个单链表，所以我们需要创建一个指针遍历链表，逐一销毁:
4.队列的插入
要插入节点，首先需要malloc一个新节点，随后进行判断，如果在初始情况，那么还没有节点，这个时候的phead和ptail就都指向新节点；如果链表中已经有了节点，那只需要尾插到后面，记得size要++:
5.队列的删除
删除同样要判断，如果只有一个节点，那么删完，phead和ptail就都要置为NULL，如果不为空，那么就要指定新的头结点,记得size要--：
6.统计队列的数据个数
统计个数就是统计size：
7.判断队列是否为空
size如果是0，那就是空:
8.返回队列表头数据
那就返回头指针指向的val:
9.返回队列表尾数据
那就返回尾指针指向的val:
10.运行展示
我们假设插入1,2,3,4：
运行如下:
三、代码
test.c:
#include"Queue.h"
int main()
{
Queue q;
QueueInit(&q);
QueuePush(&q, 1);
QueuePush(&q, 2);
QueuePush(&q, 3);
QueuePush(&q, 4);
while (!QueueEmpty(&q))
{
printf("%d ", QueueFront(&q));
QueuePop(&q);
}
printf("\n");
QueueDestroy(&q);
return 0;
}
Queue.h:
#pragma once
#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>
typedef int QDataType;
typedef struct QueueNode
{
struct QueueNode* next;
QDataType val;
}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);//队列的删除
int QueueSize(Queue* pq);//统计队列的数据个数
QDataType QueueFront(Queue* pq);//返回队列表头数据
QDataType QueueBack(Queue* pq);//返回队列表尾数据
bool QueueEmpty(Queue* pq);//判断队列是否为空
Queue.c:
#include "Queue.h"
void QueueInit(Queue* pq)
{
assert(pq);//判断是否为空
pq->phead = NULL;//初始化指向NULL
pq->ptail = NULL;//初始化指向NULL
pq->size = 0;//初始的时候，值为0
}
void QueuePush(Queue* pq, QDataType x)
{
QNode* newnode = (QNode*)malloc(sizeof(QNode));//创建一个新节点
if (newnode == NULL)//判断是否创建成功
{
perror("malloc fail");
return;
}
newnode->next = NULL;//新节点的next指针为NULL
newnode->val = x;//它的值为给的x
if (pq->ptail == NULL)//判断是否为初始情况
{
pq->phead = pq->ptail = newnode;
}
else//不是初始情况，链表中已经有节点
{
pq->ptail->next = newnode;//直接尾插
pq->ptail = newnode;//成为新的尾
}
pq->size++;//个数加一
}
void QueuePop(Queue* pq)
{
assert(pq);
assert(pq->size != 0);
if (pq->phead->next==NULL)//是否链表中只有一个节点
{
free(pq->phead);
pq->phead = pq->ptail = NULL;//都为NULL
}
else//链表中不止一个节点
{
QNode* tmp = pq->phead->next;//临时变量存放新的头结点
free(pq->phead);
pq->phead = tmp;
}
pq->size--;//删除节点，size要减少1
}
int QueueSize(Queue* pq)
{
assert(pq);
return pq->size;
}
QDataType QueueFront(Queue* pq)
{
assert(pq);
assert(pq->phead);
return pq->phead->val;
}
QDataType QueueBack(Queue* pq)
{
assert(pq);
assert(pq->ptail);
return pq->ptail->val;
}
bool QueueEmpty(Queue* pq)
{
assert(pq);
return 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;//size也变成0
}