数据结构——队列(C语言版)
时间:2024-03-28 09:10:58 来源:网络cs 作者:利杜鹃 栏目:卖家故事 阅读:
前言:
在学习完数据结构顺序表和链表之后,其实我们就可以做很多事情了,后面的栈和队列,其实就是对前面的顺序表和链表的灵活运用,今天我们就来学习一下队列的原理和应用。
准备工作:本人习惯将文件放在test.c、SeqList.c、SeqList.h三个文件中来实现,其中test.c用来放主函数,SeqList.c用来放调用的函数,SeqList.h用来放头文件和函数声明
目录
什么是队列?
队列的节点结构
队列的基本操作
1、初始化
2、销毁
3、增加(插入数据)
4、删除
5、取队头、取队尾、取长度、判断头指针是否为空
完整的队列实例
总结
什么是队列?
队列中的数据是按照先进先出的顺序的,也就是说先进去的数字也先出来
因为队列的这种性质,所以队列我们用链表来实现比顺序表方便很多,因为用顺序表每插入一个数或者删除一个数都需要遍历整个数组,这样就会很容易出错且不够方便,我们一般采用单链表来实现队列
队列的节点结构
队列采用的单链表的结构,所以与单链表差异不大
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);//取长度QDataType QueueSize(Queue* pq);//判断是否为空bool QueueEmpty(Queue* pq);
看上面的函数声明部分我们就可以看到我们每一步要实现的内容,接下来,我们就来一步一步进行实现
1、初始化
//初始化void QueueInit(Queue* pq){assert(pq);pq->phead = NULL;pq->ptail = NULL;pq->size = 0;}
参数全是一个结构体指针,而且肯定不能为空,所以我们下面的函数基本都要对pq进行断言
2、销毁
将头指针指向的空间逐个释放,最后把头指针和尾指针均赋为空指
//销毁void QueueDestroy(Queue* pq){QNode* cur = pq->phead;while (cur){QNode* next = cur->next;free(cur);cur = next;}pq->phead = pq->ptail = NULL;pq->size = 0;}
3、增加(插入数据)
因为先进先出,实际上数据就是从尾部插入,从头部出去,即插入形式为尾插
//插入void QueuePush(Queue* pq, QDataType x){assert(pq);QNode* newnode = (QNode*)malloc(sizeof(QNode));newnode->data = x;newnode->next = NULL; //判断头部是否为空if (pq->phead == NULL){pq->phead = pq->ptail = newnode;}else{pq->ptail->next = newnode;pq->ptail = newnode;}pq->size++;}
用单链表插入数据必须要考虑头部为空和不为空两种情况
4、删除
栈和队列都有一个特点就是,数据只会输出一遍,也就是数据一经输出就会销毁删除
如下:
1在输出之后就会被删除,删除的代码如下:
//删除void QueuePop(Queue* pq){assert(pq);assert(!QueueEmpty(pq));//1、一个节点//2、多个节点if (pq->phead->next == NULL){free(pq->phead);pq->phead = pq->ptail = NULL;}else{QNode* ptr = pq->phead->next;free(pq->phead);pq->phead = ptr;}}
这里面又分为两种情况,难度不大,根据注释自行体会即可
5、取队头、取队尾、取长度、判断头指针是否为空
这几步难度不大,放在一起看看
取队头
//取队头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;}
取长度
//取长度QDataType QueueSize(Queue* pq){assert(pq);return pq->size;}
判断头指针是否为空(这个函数应用上可以在下面的完整案列上体会一下)
bool QueueEmpty(Queue* pq){assert(pq);return pq->phead == NULL;}
完整的队列实例
test.c
//队列void TestQNode(){Queue q;QueueInit(&q);QueuePush(&q, 1);QueuePush(&q, 2);QueuePush(&q, 3);QueuePush(&q, 4);printf("%d\n", QueueSize(&q));while (!QueueEmpty(&q)){printf("%d ", QueueFront(&q));QueuePop(&q);}QueueDestroy(&q);}int main(){TestQNode();return 0;}
SeqList.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);//取长度QDataType QueueSize(Queue* pq);//判断是否为空bool QueueEmpty(Queue* pq);
SeqList.c
//初始化void QueueInit(Queue* pq){assert(pq);pq->phead = NULL;pq->ptail = NULL;pq->size = 0;}//销毁void QueueDestroy(Queue* 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));newnode->data = 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(!QueueEmpty(pq));//1、一个节点//2、多个节点if (pq->phead->next == NULL){free(pq->phead);pq->phead = pq->ptail = NULL;}else{QNode* ptr = pq->phead->next;free(pq->phead);pq->phead = ptr;}}//取队头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;}//取长度QDataType QueueSize(Queue* pq){assert(pq);return pq->size;}bool QueueEmpty(Queue* pq){assert(pq);return pq->phead == NULL;}
运行后结果:
总结
总之,其实队列就是对链表的应用,熟练栈和队列,对我们巩固顺序表和链表帮助很大,当然,队列在一些场景下很实用,后面我会出一个专门的习题讲解篇章,讲数据结构的一些经典题型,感兴趣的可以点赞关注一下
创作不易,还请各位大佬点赞支持一下!!!
阅读本书更多章节>>>>本文链接:https://www.kjpai.cn/gushi/2024-03-28/149846.html,文章来源:网络cs,作者:利杜鹃,版权归作者所有,如需转载请注明来源和作者,否则将追究法律责任!