【数据结构初阶第十节】队列（详解+附源码）_3063610934,队列文字
好久不见。。。别不开心了，听听喜欢的歌吧
必须有为成功付出代价的决心，然后想办法付出这个代价。云边有个稻草人-CSDN博客
目录
一、概念和结构
二、队列的实现
Queue.h
Queue.c
test.c
Relaxing Time！
————————————《有没有那么一首歌会让你想起我》————————————
这节课我们学习队列的概念和结构以及实现，需要提前具备前面顺序表和链表的相关知识，这样这节课就会变得非常简单！
一、概念和结构
概念： 只允许在⼀端进行插⼊数据操作，在另⼀端进⾏删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out)。 入队列： 进行 插⼊操作的⼀端称为队尾。 出队列： 进行 删除操作的⼀端称为队头。 队列底层结构选型 ： 队列也可以数组和链表的结构实现，使⽤链表的结构实现更优⼀些，因为如果使⽤数组的结构，出队列在数组头上出数据，效率会⽐较低。 下图解释为什么用链表来实现队列
二、队列的实现
Queue.h
#pragma once#include#include#include#include//创建节点的结构typedef int QUDatatype;typedef struct QueueNode{QUDatatype data;struct QueueNode* next;}QueueNode;//创建队列的结构typedef struct Queue{QueueNode* phead;QueueNode* ptail;int size;//队列里面有效数据个数}Queue;//初始化void QueueInit(Queue* pq);//入队列void QueuePush(Queue* pq,QUDatatype x);//出队列void QueuePop(Queue* pq);//取队头数据QUDatatype QueueFront(Queue* pq);//取队尾数据QUDatatype QueueBack(Queue* pq);//取队列有效元素个数int QueueSize(Queue* pq);//销毁void QueueDestroy(Queue* pq);Queue.c
#include\"Queue.h\"//初始化void QueueInit(Queue* pq){assert(pq);pq->phead = pq->ptail = NULL;pq->size = 0;}//入队列void QueuePush(Queue* pq,QUDatatype x){assert(pq);//申请一个新的结点QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));if (newnode == NULL){perror(\"malloc fail！\");exit(1);}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;}//判空bool QueueEmpty(Queue* pq){assert(pq);//下面这样写也ok，return pq->phead == NULL && pq->ptail == NULL ;return pq->phead == NULL;}//出队列void QueuePop(Queue* pq){assert(pq);assert(!QueueEmpty(pq));//若只有一个结点,防止ptail成为野指针if (pq->phead == pq->ptail){free(pq->phead);pq->phead = pq->ptail = NULL;}else{//删除对头元素QueueNode* Next = pq->phead->next;free(pq->phead);pq->phead = Next;}--pq->size;}//取队头数据QUDatatype QueueFront(Queue* pq){assert(pq);assert(!QueueEmpty(pq));return pq->phead->data;}//取队尾数据QUDatatype QueueBack(Queue* pq){assert(pq);assert(!QueueEmpty(pq));return pq->ptail->data;}//取队列有效元素个数,时间复杂度为O(N),我们可以优化一下//我们可以增加一个变量size去记录队列里面有效数据的个数然后直接返回int QueueSize(Queue* pq){assert(pq);/*QueueNode* pcur = pq->phead;int count = 0;while (pcur){count++;QueuePop(pq);pcur = pq->phead;}*//*return count;*/return pq->size;}//销毁void QueueDestroy(Queue* pq){assert(pq);assert(!QueueEmpty(pq));QueueNode* pcur = pq->phead;while (pcur){QueueNode* next = pcur->next;free(pcur);pcur = next;}//针对队列里面的结构进行销毁pq->phead = pq->ptail = NULL;pq->size = 0;}test.c
#include\"Queue.h\"void test(){Queue pq;QueueInit(&pq);QueuePush(&pq, 1);QueuePush(&pq, 2);QueuePush(&pq, 3);QueuePush(&pq, 4);/*QueuePop(&pq);QueuePop(&pq);QueuePop(&pq);QueuePop(&pq);QueuePop(&pq);*/printf(\"head:%d\\n\", QueueFront(&pq));printf(\"back:%d\\n\", QueueBack(&pq));//两种 取队列里面有效数据的个数 方法printf(\"队列里面有效数据个数为：%d \\n\",QueueSize(&pq));printf(\"size:%d\\n\", QueueSize(&pq));printf(\"size:%d\\n\", pq.size);QueueDestroy(&pq);}int main(){test();return 0;}实现队列需要注意的比较重要的点见下
- 取队列里面有效数据的个数，如果用老方法套路实现时间复杂度为O(N)，但是我们可以在队列里面重新定义一个结构，size来记录，每次入数据，出数据直接调整size即可，取有效数据个数的时候直接返回 size 就简单了很多。
- 在队列销毁的时候，不要忘记最后把队列结构里面的phead和ptail指针置为NULL，size == 0。
- 我们定义了ptail指针，指向队尾，可以直接找到队尾入数据。
经过前几节顺序表，单链表，双链表，栈的学习，今天学习队列真是游刃有余呦，下一节是栈和队列的算法题，期待一下啦~~
完——
Relaxing Time！
————————————《 有没有那么一首歌会让你想起我 》————————————
有没有一首歌会让你想起我_HENRY刘宪华_高音质在线试听_有没有一首歌会让你想起我歌词|歌曲下载_酷狗音乐
至此结束！
我是云边有个稻草人
期待与你的下一次相遇。。。
