代码有写的不好的地方，请大家多多指点
MyQueue.h
// MyQueue.h
#define TRUE 1
#define FALSE 0
#define bool _Bool
//使用 伪bool 类型
#ifndef MYQUEUE_H
#define MYQUEUE_H
#include <stdlib.h>
#define NODE_DATA_TYPE int
//? NODE_DATA宏代表每一个节点的数据类型
//todo 实现队列
//! 队列的节点
typedef struct MyQueueNode {
NODE_DATA_TYPE NodeValue;//! 当前节点值
struct MyQueueNode* Next;//指向下一个节点
}MyQueueNode;
//! 队列
typedef struct MyQueue {
unsigned int Length;//当前队列长度
MyQueueNode* Head;//队头
MyQueueNode* Back;//队尾
}MyQueue;
//队列只能从后端加入，从前端弹出
MyQueue* newMyQueue(void);
//新建一个MyQueue的结构体对象,void代表该函数不接受任何的参数
MyQueueNode* newMyQueueNode(NODE_DATA_TYPE Value);
//新建一个MyQueue的结构体对象,Value是这个节点的值
void pushToQueue(MyQueue* self, NODE_DATA_TYPE Value);
//添加到队尾,self是队列的指针,Value是要添加到末尾的值
void popFromQueue(MyQueue* self);
//弹出队头元素,self是队列的指针
bool isEmpty(MyQueue* self);
//判断是否为空,返回当前的长度是否为0,假设长度为100,返回0,否则返回1
unsigned int QueueSize(MyQueue* self);
//获取队列长度,self是队列的指针
NODE_DATA_TYPE getFront(MyQueue* self);
//获取队头值,self是队列的指针
NODE_DATA_TYPE getBack(MyQueue* self);
//获取队尾值,self是队列的指针
void TraverseQueue(MyQueue* self,void(*fcp)(NODE_DATA_TYPE));
//遍历队列,fcp是一个函数指针,需要将节点值做为参数传函数
/* *
*fcp : 我本次的缩写 本意为 Function pointer
* */
#endif
MyQueue.c
//MyQueue.c
#include "MyQueue.h"
//! newMyQueue Function
MyQueue* newMyQueue(void) {
MyQueue* self = (MyQueue*)
(malloc(sizeof(MyQueue)));
//使用动态内存分配，这里需要使用malloc函数
if (self == NULL) {
//假如内存分配失败，返回NULL指针,但是这种情况发生的比较少
return NULL;
}
//假如内存分配成功
self->Head = self->Back = NULL;
self->Length = 0;
//队头就是队尾，此时队尾为空
//此时队列长度为0
return self;//返回这个结构体对象
}
//! newMyQueueNode Function
MyQueueNode* newMyQueueNode(NODE_DATA_TYPE Value) {
//Value是节点的值
MyQueueNode* self = (MyQueueNode*)
(malloc(sizeof(MyQueueNode)));
if (self == NULL) {
return NULL;
}//上面原理同newMyQueue函数
//假如内存分配成功
//当前节点的值是Value,并且下一个节点是空的
self->Next = NULL;
self->NodeValue = Value;
return self;//返回这个结构体对象
}
//! pushToQueue Function
void pushToQueue(MyQueue* self, NODE_DATA_TYPE Value) {
//将元素添加到末尾 ※
//此函数使用了isEmpty函数，详情看下方isEmpty的定义
//假如self这个队列为空时
if (isEmpty(self)) {
self->Head = newMyQueueNode(Value);//此时队列就一个元素，队尾同时也是队头
self->Back = self->Head;
self->Length++;//长度加一个
return;//结束这个函数
}
//假如self这个队列不为空,则self->Head肯定不是NULL
MyQueueNode* Temp = self->Head;//定义临时变量Temp,它充当self的队头
while (self->Head->Next != NULL) {
self->Head = self->Head->Next;//从队头出发，直到它下一个节点的指针是NULL
}
self->Head->Next = newMyQueueNode(Value);
//此时self->Head->Next为NULL,这就是我们要添加到的位置
self->Back = self->Head->Next;
//最后一个节点不是原来的最后一个节点了，此时Back应该是新的节点
self->Head = Temp;
//self->Head此时应该不是第一个指针，这个时候体现了Temp的作用
//将原来队头的位置“让给”self->Head
self->Length++;
//当前长度加一
}
//! popFromQueue Function
void popFromQueue(MyQueue* self) {
if (isEmpty(self))return;
//假如这是空的队列，哪有元素可以删？直接结束这个函数！
MyQueueNode* Temp = self->Head;
//定义变量Temp，它此时存储self->Head的信息
//self->Head指向下一个节点,释放Temp，也就释放了原来的self->Head
self->Head = self->Head->Next;
free(Temp);
if (self->Head == NULL) {
self->Back = NULL;
}//假如就一个元素，此时self->Head就是self->Back,然后这个元素被删了,那Back就也被释放了
//所以，我们需要把Back设置为NULL
self->Length--;//长度减1
}
//! isEmpty Function
bool isEmpty(MyQueue* self) {
return !self->Length;
//判断长度是不是0,也就是self->Length==0，这个表达式
/*
self->Length==0
结果:
当Length为0时，表达式为1
当Length为1时，表达式为0
所以我们可以将这个表达式设置为!self->Length，不为0就是0,否则为1
*/
}
//! QueueSize Function
unsigned int QueueSize(MyQueue* self) {
return self->Length;
//返回长度，没什么好说的
}
//! getFront Function
NODE_DATA_TYPE getFront(MyQueue* self) {
return self->Head->NodeValue;
//返回队列self的队头的值
}
//! getBack Function
NODE_DATA_TYPE getBack(MyQueue* self) {
return self->Back->NodeValue;
//返回队列self的队尾的值
}
//! raverseQueue Function
void TraverseQueue(MyQueue* self,void(*fcp)(NODE_DATA_TYPE)) {
MyQueueNode* Temp = self->Head;//临时变量，意义同其他函数的Temp变量
//遍历self这个队列
while (self->Head != NULL) {
fcp(self->Head->NodeValue);//每一次循环都调用这个函数
self->Head = self->Head->Next;
}
self->Head = Temp;//Head指向原来的位置
}
示例
#include <stdio.h>
#include <time.h>//time()
#include "MyQueue.h"
void putNumber(int Number) {
printf("%d\t", Number);
}
int main(int argc, char* argv[]) {
MyQueue* Queue = newMyQueue();//创建一个队列
//尝试 判断队列是否为空，获取队列当前长度
srand(time(NULL));//随机数种子
if (isEmpty(Queue)) {
printf("当前队列Queue为空\r\n");
}
else {
printf("当前队列Queue不为空\r\n");
}
printf("当前队列长度:%d\r\n", QueueSize(Queue));
printf("-------------------------------\r\n");
//向队列添加5个随机值
printf("随机生成了5个值并且添加到队列Queue\r\n");
for (int i = 0,j=0; i < 5; i++) {
j = rand() % 10 + 1;
printf("%d\t", j);
pushToQueue(Queue, j);
}
printf("\r\n-------------------------------\r\n");
//遍历当前队列
printf("当前队列Queue值\r\n");
TraverseQueue(Queue, putNumber);
printf("\r\n-------------------------------\r\n");
printf( "当前队列Queue的长度是%d\r\n"
"当前队列Queue队头节点值是%d\r\n"
"当前队列Queue队尾节点值是%d\r\n",
QueueSize(Queue),getFront(Queue),getBack(Queue));
printf("-------------------------------\r\n");
printf("弹出队头元素\r\n");
popFromQueue(Queue);
printf("当前队列Queue的长度是%d\r\n"
"当前队列Queue队头节点值是%d\r\n"
"当前队列Queue队尾节点值是%d\r\n",
QueueSize(Queue), getFront(Queue), getBack(Queue));
printf("---------------Queue----------------\r\n\r\n");
MyQueue* Queue2 = newMyQueue();//创建一个队列
//尝试单个元素Debug
pushToQueue(Queue2, 100);
printf("当前队列Queue2的长度是%d\r\n"
"当前队列Queue2队头节点值是%d\r\n"
"当前队列Queue2队尾节点值是%d\r\n",
QueueSize(Queue2), getFront(Queue2), getBack(Queue2));
//删除元素
printf("弹出队列Queue2队头\r\n");
popFromQueue(Queue2);
printf("当前队列Queue2长度:%d\r\n", QueueSize(Queue2));
int Value[3];
printf("输入三个值用于加入队列Queue2:");
scanf_s("%d %d %d", &Value[0], &Value[1], &Value[2]);
while (QueueSize(Queue2) != 3) {
pushToQueue(Queue2,Value[QueueSize(Queue2)]);
}
printf("当前队列Queue2的值\r\n");
TraverseQueue(Queue2, putNumber);
printf("\r\n");
printf("正在清空当前队列Queue2\r\n");
while (QueueSize(Queue2)) {
popFromQueue(Queue2);
}
printf("当前队列长度为%d,是否为空:%d\r\n",QueueSize(Queue2),isEmpty(Queue2));
printf("---------------Queue2----------------\r\n\r\n");
return 0;
}
示例输入：1234,7890,6666
示例结果：
原理部分
队列是一种特殊的线性表，是一种先进先出（FIFO）的数据结构。它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列。声明 [转自https://baike.baidu.com/item/queue/4511093)
草图
详情原理请看代码注释