天津建设监理协会网站,搭建个人网站,公司网站建设应注意什么,网站建设保障机制Hello everybody!今天给大家讲讲队列的相关知识。队列#xff0c;属于一种数据结构。从字面意思上理解#xff0c;就像是排队一样#xff0c;在食堂中#xff0c;先排队的人自然就先买到饭。队列也是如此#xff0c;先入队列的数据自然就先出队列。希望大家可以通过这篇文…Hello everybody!今天给大家讲讲队列的相关知识。队列属于一种数据结构。从字面意思上理解就像是排队一样在食堂中先排队的人自然就先买到饭。队列也是如此先入队列的数据自然就先出队列。希望大家可以通过这篇文章解决自己心中的疑惑那废话不多说让我们开始叭
1.队列的概念及结构
队列只允许在一端进行插入数据操作在另一端进行删除数据操作的特殊线性表队列遵循先进先出FIFOFirst In First Out
入队列进行插入操作的一端称为队尾
出队列进行删除操作的一端称为队头 2.队列的实现
队列可以以数组和链表的结构实现使用链表的结构实现更优因为如果使用数组的结构出队列是需要移动数据时间复杂度是O(n),效率比较低。 由于实现队列需要较长的代码因此我们要像公司中做大型项目一样创建一个头文件Queue.h和两个源文件Queue.c Test.c。
头文件中需要包含所需要的库文件接口的声明队列的声明。总之就是要我们清晰的看到队列的结构和功能。
而源文件Queue.c需要实现在头文件中声明的接口。
源文件Test.c用于测试队列的功能是否正常。
当然源文件需要包含头文件这样才能把它们关联起来。
创建三个文件使得代码逻辑更加清晰有利于后期代码的维护。
2.1接口的声明队列的声明 这是队列的结构结构体QNode是队列的链式结构它可以存放当前结点的值和下一个结点的地址。但是当队列为空插入第一个数据时需要改变头指针。因此需要传递二级指针这样显然是有些麻烦的。所以我们再创建一个结构体Queue用于存放队列的头指针和尾指针更方便入队和出队。size用来记录队列中的元素个数。 以上是队列主要功能的接口下面我们来逐个实现它们。
2.2接口的实现及功能测试 目前为止我们已经实现了初始化和入队两个接口。下面测试一下它们的功能。 通过调试我们可以看到初始化后在队尾成功插入1和2。目前队列中有两个数值接口功能正常。
下面我们来实现一下其他的接口 这是队列剩下的接口咱们也来测试一下。 从测试结果来看各个接口功能正常销毁队列后头指针和尾指针都被置为空指针队列大小size为0。符合要求。
3.代码
为了方便大家更好的学习队列的代码我也给出来
#pragma once
#include stdio.h
#include assert.h
#include stdlib.h
#include stdbool.h
typedef int QDataType;
typedef struct QueueNode {QDataType val;struct QueueNode* next;
}QNode;
typedef struct Queue {QNode* phead;QNode* ptail;int size;
}Queue;void QueueInit(Queue* pq);//初始化
void QueuePush(Queue* pq, QDataType x);//入队
void QueuePop(Queue* pq);//出队
void QueueDestroy(Queue* pq);//销毁
QDataType QueueFront(Queue* pq);//返回队头的值
QDataType QueueBack(Queue* pq);//返回队尾的值
bool QueueEmpty(Queue* pq);//判断队列是否为空
int QueueSize(Queue* pq);//返回队列的数据个数
#include Queue.h
void QueueInit(Queue* pq) {assert(pq);//检验pq是否为空指针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);exit(-1);}newnode-val x;newnode-next NULL;if (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(pq-phead);//队列不能为空QNode* next pq-phead-next;//记录头结点的下一个结点free(pq-phead);pq-phead next;if (pq-phead NULL) {//当phead为NULL时ptail没有变化。但ptail指向的空间已经还给操作系统此时ptail就是野指针必须处理掉pq-ptail NULL;}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-phead NULL;
}
int QueueSize(Queue* pq) {assert(pq);return pq-size;
}
void QueueDestroy(Queue* pq) {assert(pq);while (pq-phead) {QNode* next pq-phead-next;free(pq-phead);pq-phead next;}pq-phead pq-ptail NULL;pq-size 0;
}
#include Queue.h
int main() {Queue pq;QueueInit(pq);QueuePush(pq, 1);QueuePush(pq, 2);QueuePush(pq, 3);QueuePush(pq, 4);printf(%d\n, QueueBack(pq));printf(%d\n, QueueSize(pq));while (!QueueEmpty(pq)) {printf(%d, QueueFront(pq));QueuePop(pq);}QueueDestroy(pq);return 0;
}
4.结语
好啦关于队列的讨论就到这里叭。不知道大家有没有收获呢如果有疑问可以发在评论区。
最后希望宝子们每天都有所进步成为自己想成为的人做自己想做的事\(0^◇^0)/
