【数据结构初阶第十节】队列（详解+附源码）

 好久不见。。。别不开心了，听听喜欢的歌吧

必须有为成功付出代价的决心，然后想办法付出这个代价。云边有个稻草人-CSDN博客

目录

一、概念和结构

二、队列的实现

Queue.h

Queue.c

 test.c

Relaxing Time！

————————————《有没有那么一首歌会让你想起我》————————————

---

这节课我们学习队列的概念和结构以及实现，需要提前具备前面顺序表和链表的相关知识，这样这节课就会变得非常简单！

一、概念和结构 概念： 只允许在⼀端进行插⼊数据操作，在另⼀端进⾏删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out)。 入队列： 进行 插⼊操作的⼀端称为队尾。 出队列： 进行 删除操作的⼀端称为队头。 队列底层结构选型 ： 队列也可以数组和链表的结构实现，使⽤链表的结构实现更优⼀些，因为如果使⽤数组的结构，出队列在数组头上出数据，效率会⽐较低。 下图解释为什么用链表来实现队列

二、队列的实现 Queue.h #pragma once #include<stdio.h> #include<stdlib.h> #include<assert.h> #include<stdbool.h> //创建节点的结构 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刘宪华_高音质在线试听_有没有一首歌会让你想起我歌词|歌曲下载_酷狗音乐

至此结束！

我是云边有个稻草人

期待与你的下一次相遇。。。