【数据结构入门】队列（Queue）详解（定义、销毁、入队、出队等） |
您所在的位置：网站首页 › 在用单链表表示的链式队列q中 › 【数据结构入门】队列（Queue）详解（定义、销毁、入队、出队等） |
【数据结构入门】队列（Queue）详解（定义、销毁、入队、出队等）
|
文章目录
（1）前言1）队列的概念2）队列的结构
（2）队列的实现（链式结构）1）队列的定义2）队列的初始化3）队列的销毁4）入队（尾插）5）出队（头删）6）获取队列元素个数7）获取队头元素8）获取队尾元素9）检查队列是否为空
（3）测试队列的功能
数据结构系列文章：
【数据结构入门】顺序表（SeqList）详解（初始化、增、删、查、改） 【数据结构入门】无头单向非循环链表（SList）详解（定义、增、删、查、改） | 图解链表，超生动详细哦~ 【数据结构入门】带头双向循环链表（List）详解（定义、增、删、查、改） | 配有大量图解，超详细哦~ 【数据结构入门】顺序表和链表的区别，以及啥是缓存利用率 【数据结构入门】栈（Stack）的实现（定义、销毁、入栈、出栈等） | 图解数据结构，超详细哦~ （1）前言 1）队列的概念队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出 FIFO(First In First Out) 的特点。 入队列：进行插入操作的一端称为队尾 。 出队列：进行删除操作的一端称为队头。 
入队出队形式：一种入队顺序，只有一种出队顺序。 队列的应用：比如生活中排队买东西，先排队的先购买，平时我们用微信聊天，用键盘进行各种数字的输入，到聊天框中输出，也是队列的应用。 2）队列的结构
队列的顺序结构
入队，不需要移动任何元素，时间复杂度为O(1) 出队，所有元素需要往前移动，时间复杂度为O(N) 队列的链式结构首先我们定义两个指针，队头指针指向第一个节点，队尾指针指向尾节点 入队（尾插），时间复杂度为O(1) 出队（头删），时间复杂度为O(1) （2）队列的实现（链式结构）首先新建一个工程（ 博主使用的是 VS2019 ） Queue.h（队列的类型定义、接口函数声明、引用的头文件）Queue.c（队列接口函数的实现）Test.c（主函数、测试队列各个接口功能）Queue.h 头文件代码如下： #pragma once #include /*printf*/ #include /*bool*/ #include /*assert*/ #include /*malloc*/ typedef int QDataType; typedef struct QueueNode //队列节点结构 { QDataType data; //节点数据 struct QueueNode* next; //节点指针 }QueueNode; /* 我们实现无头链表的头插头删接口时，因为需要改变头指针的指向 有以下这样方法： 1、传二级指针 2、改变返回值，返回新的头 3、给链表增加一个哨兵位的头节点 4、结构体包起来 */ typedef struct QueuePtr //队列的链式结构 { QueueNode* phead; //队头指针 QueueNode* ptail; //队尾指针 }LinkQueue; //初始化队列 void QueueInit(LinkQueue* pQ); //销毁队列 void QueueDestroy(LinkQueue* pQ); //入队（尾插） void QueuePush(LinkQueue* pQ, QDataType x); //出队（头删） void QueuePop(LinkQueue* pQ); //获取队列元素个数 int QueueSize(LinkQueue* pQ); //获取队头元素 QDataType QueueFront(LinkQueue* pQ); //获取队尾元素 QDataType QueueBack(LinkQueue* pQ); //检查队列是否为空 bool QueueEmpty(LinkQueue* pQ);这里重点讲解 Queue.c 中各个接口函数的实现。 1）队列的定义 typedef int QDataType; typedef struct QueueNode //队列节点结构 { QDataType data; //节点数据 struct QueueNode* next; //节点指针 }QueueNode; typedef struct QueuePtr //队列的链式结构 { QueueNode* phead; //队头指针 QueueNode* ptail; //队尾指针 }LinkQueue; 2）队列的初始化 //初始化队列 void QueueInit(LinkQueue* pQ) { assert(pQ); //队列为空 pQ->phead = pQ->ptail = NULL; } 3）队列的销毁 //销毁队列 void QueueDestroy(LinkQueue* pQ) { assert(pQ); QueueNode* cur = pQ->phead; while (cur) //遍历链式队列 { QueueNode* next = cur->next; free(cur); cur = next; } cur = NULL; pQ->phead = pQ->ptail = NULL; //队列为空 } 4）入队（尾插）要分为两种情况讨论，队列为空和队列不为空 //入队（尾插） void QueuePush(LinkQueue* pQ, QDataType x) { assert(pQ); QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode)); //动态申请一个节点 if (newnode == NULL) //检查是否申请成功 { perror("malloc"); exit(-1); } newnode->data = x; newnode->next = NULL; //尾节点next指针置空 if (pQ->phead == NULL) //队列为空 { pQ->phead = newnode; } else //队列不为空 { pQ->ptail->next = newnode; } pQ->ptail = newnode; //更新队尾指针 } 测试其用例
5）出队（头删）
队列不能为空哦，记得在最开头检查一下 //出队（头删） void QueuePop(LinkQueue* pQ) { assert(pQ); assert(!QueueEmpty(pQ)); //队列不能为空 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; //更新队头指针 } } 6）获取队列元素个数 //获取队列元素个数 //如果会频繁调用这个接口函数，可以在QueuePtr中加一个size记录数据个数 int QueueSize(LinkQueue* pQ) { assert(pQ); int size = 0; QueueNode* cur = pQ->phead; while (cur) //遍历链表 { size++; cur = cur->next; } return size; } 7）获取队头元素队列为空是获取不了元素的哦，记得检查一下 //获取队头元素 QDataType QueueFront(LinkQueue* pQ) { assert(pQ); assert(!QueueEmpty(pQ)); //队列不能为空 return pQ->phead->data; } 8）获取队尾元素队列为空是获取不了元素的哦，记得检查一下 //获取队尾元素 QDataType QueueBack(LinkQueue* pQ) { assert(pQ); assert(!QueueEmpty(pQ)); //队列不能为空 return pQ->ptail->data; } 9）检查队列是否为空 //检查队列是否为空，若为空返回true，否则返回false bool QueueEmpty(LinkQueue* pQ) { assert(pQ); return pQ->phead == NULL && pQ->ptail == NULL; } （3）测试队列的功能 void TestQueue() { LinkQueue Q; QueueInit(&Q); QueuePush(&Q, 1); QueuePush(&Q, 2); QueuePush(&Q, 3); QueuePush(&Q, 4); //打印队列 while (!QueueEmpty(&Q)) { printf("%d ", QueueFront(&Q)); //获取队头元素 QueuePop(&Q); //出队 } printf("\n"); } 运行结果
大家快去动手实现一下吧！ |
【本文地址】
今日新闻 |
推荐新闻 |