• 【数据结构初阶】六、线性表中的队列（C语言 -- 链式结构实现队列）

    =========================================================================

    相关代码gitee自取：

    C语言学习日记: 加油努力 (gitee.com)

     =========================================================================

    接上期：

    【数据结构初阶】五、线性表中的栈（C语言 -- 顺序表实现栈）_高高的胖子的博客-CSDN博客

     =========================================================================

                         

    1 . 队列（Queue）

    队列的概念和结构：

    队列的概念

    • 队列是一种只允许在一端执行插入数据操作，在另一端进行删除数据操作的特殊线性表
                        
    • 入队列 -- 进行插入操作的一端称为队尾
      出队列 -- 进行删除操作的一端称为队头
                  
    • 队列中的数据元素遵守
      先进先出（FIFO -- First In First Out）的原则 -- 先进入的元素会先出来
      所以可以应用在公平性排队(抽号机)、BFS(广度优先遍历)
                          

    队列的结构

             

    ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

                 

    2 . 队列的实现

                    

    使用 顺序表(数组) 或 链表(链式结构) 都可以实现队列，

    使用顺序表的话，入队列比较简单，但在出队列时需要删除和挪动数据，效率较低，

    所以下面用链表(链式结构)实现队列  --  单向 + 无头 + 非循环 链表

    入队 -- 单链表尾部插入(尾插)         ；      出队 -- 单链表头部删除(头删)

                   

    （详细解释在图片的注释中，代码分文件放下一标题处）

                   

    实现具体功能前的准备工作

    • 定义队列(链式结构)中数据域存储的数据类型
                                 
    • 定义队列(链式结构)结点类型
      包含 队列指针域 和 队列数据域
                   
    • 定义队列类型
      包含 头结点指针 、尾结点指针 和 队列结点(元素)个数
    图示

                

                

    ---------------------------------------------------------------------------------------------

                

    QueueInit函数 -- 将队列进行初始化

    • assert断言队列类型指针不为空
                                 
    • 将队头结点置为空
      将队尾结点置为空
      队列结点(元素)个数置为0
    图示

                

                

    ---------------------------------------------------------------------------------------------

                

    QueueDestroy函数 -- 将队列销毁

    • assert断言队列类型指针不为空
                                 
    • 创建一个在队列进行遍历的指针cur
      使用while循环进行遍历释放队列结点
                   
    • 结点都释放后，把队头队尾指针都置空
                     
    • 再把队列结点(元素)个数置为0
    图示

                

                

    ---------------------------------------------------------------------------------------------

                

    QueuePush函数 -- 用链表的尾插操作实现入队

    • assert断言队列类型指针不为空
                                 
    • 为队列结点开辟动态空间并检查空间开辟情况
                   
    • 结点开辟成功后
      将尾插值(x)赋给队列结点的数据域并将指针域置为空
                     
    • 空间开辟后进行尾插
      如果队列刚初始化队列为空，将刚开辟的结点newnode地址赋给头尾结点指针
      队列不为空，正常进行尾插操作
                  
    • 插入数据后队列结点(元素)个数++
    图示

                

                

    ---------------------------------------------------------------------------------------------

                

    QueuePop函数 -- 用链表的头删操作实现出队

    • assert断言队列类型指针不为空和队列不为空
                                 
    • 出队(头删)分两种情况：
      队列中只剩一个结点 -- 头删后头指针移动，尾指针也要移动
      队列不止一个结点 -- 头删后只需移动队头结点
                   
    • “删除”后队列结点(元素)个数--
    图示

                

                

    ---------------------------------------------------------------------------------------------

                

    QueueFront函数 -- 返回队头结点的数据域数据

    • assert断言队列类型指针不为空和队列不为空
                                 
    • 队列有数据，则直接返回队头结点数据域数据
    图示

                

                

    ---------------------------------------------------------------------------------------------

                

    QueueBack函数 -- 返回队尾结点的数据域数据

    • assert断言队列类型指针不为空和队列不为空
                                 
    • 队列有数据，则直接返回队尾结点数据域数据
    图示​​​​​​​

                

                

    ---------------------------------------------------------------------------------------------

                

    QueueEmpty函数 -- 判断队列是否为空

    • assert断言队列类型指针不为空
                                 
    • 直接判断队头结点指向的下个结点是否为空，直接返回判断结果
    图示

                

                

    ---------------------------------------------------------------------------------------------

                

    QueueSize函数 -- 判断队列结点(元素)个数

    • assert断言队列类型指针不为空
                                 
    • 直接返回size队列结点(元素)个数
    图示

                

                

    ---------------------------------------------------------------------------------------------

                

    总体测试：

             

    ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

                 

    3 . 对应代码

    Queue.h -- 队列头文件

    1. #pragma once
    2.  
    3. //包含之后需要的头文件：
    4. #include 
    5. #include 
    6. #include 
    7. #include 
    8.  
    9. //以链表（链式结构）实现队列：
    10. //双向+循环 的链表可以解决找尾结点的问题，
    11. //定义一个尾指针也可以解决该问题，
    12. //哨兵位 可以解决二级指针的问题，
    13. //且尾插时可以少一层判断，但还有方法可以解决
    14.  
    15.  
    16. //定义队列(链式结构)中数据域存储的数据类型：
    17. typedef int QDataType;
    18.  
    19. //定义队列(链式结构)结点类型：
    20. typedef struct QueueNode
    21. {
    22. 	//队列指针域：
    23. 	struct QueueNode* next;
    24.  
    25. 	//队列数据域：
    26. 	QDataType data;
    27.  
    28. }QNode; //将类型重命名为Qnode
    29.  
    30.  
    31. //定义队列类型：
    32. typedef struct Queue
    33. {
    34. 	//因为用链表尾插实现入队，
    35. 	//用链表头删实现出队，
    36. 	//那么就需要头结点和尾结点的指针，
    37. 	//所以可以直接将这两个指针封装为一个类型，
    38. 	//队列类型：
    39.  
    40. 	//头结点指针：
    41. 	QNode* head;
    42.  
    43. 	//尾结点指针：
    44. 	QNode* tail;
    45.  
    46. 	//记录队列结点(元素)个数：
    47. 	int size; 
    48.  
    49. 	//这样之后在出队和入队操作时，
    50. 	//就不需要用到二级指针，
    51. 	//直接接收这个结构体指针，
    52. 	//通过结构体指针运用结构体里的头尾结点指针，
    53. 	//再用头尾结点指针定义头尾结点
    54. 	//来实现 二级指针、带哨兵位头结点 和 返回值 的作用
    55. 	//所以现在已知的通过指针定义结点的方法就有4种：
    56. 	//		1. 结构体包含结点指针
    57. 	//		2. 二级指针调用结点指针
    58. 	//		3. 哨兵位头结点指针域next指向结点地址
    59. 	//		4. 返回值返回改变的结点指针
    60.  
    61. }Que; //重命名为Que
    62.  
    63.  
    64. //队列初始化函数 -- 将队列进行初始化
    65. //接收队列类型指针(包含链表头尾结点) 
    66. void QueueInit(Que* pq);
    67.  
    68. //队列销毁函数 -- 将队列销毁
    69. //接收队列类型指针(包含链表头尾结点) 
    70. void QueueDestroy(Que* pq);
    71.  
    72. //队列入队函数 -- 用链表的尾插操作实现入队
    73. //接收队列类型指针(包含链表头尾结点) 、尾插值
    74. void QueuePush(Que* pq, QDataType x);
    75.  
    76. //队列出队函数 -- 用链表的头删操作实现出队
    77. //接收队列类型指针(包含链表头尾结点) 
    78. void QueuePop(Que* pq);
    79.  
    80. //队头函数 -- 返回队头结点的数据域数据
    81. //接收队列类型指针(包含链表头尾结点) 
    82. QDataType QueueFront(Que* pq);
    83.  
    84. //队尾函数 -- 返回队尾结点的数据域数据
    85. //接收队列类型指针(包含链表头尾结点) 
    86. QDataType QueueBack(Que* pq);
    87.  
    88. //判空函数 -- 判断队列是否为空
    89. //接收队列类型指针(包含链表头尾结点) 
    90. bool QueueEmpty(Que* pq);
    91.  
    92. //队列大小函数 -- 判断队列结点(元素)个数
    93. //接收队列类型指针(包含链表头尾结点) 
    94. int QueueSize(Que* pq);

                

                

    ---------------------------------------------------------------------------------------------

                    

    Queue.c -- 队列函数实现文件

    1. #define _CRT_SECURE_NO_WARNINGS 1
    2.  
    3. //包含队列头文件：
    4. #include "Queue.h"
    5.  
    6. //队列初始化函数 -- 将队列进行初始化
    7. //接收队列类型指针(包含链表头尾结点) 
    8. void QueueInit(Que* pq)
    9. {
    10. 	//assert断言队列类型指针不为空：
    11. 	assert(pq != NULL);
    12.  
    13. 	//将队头结点置为空：
    14. 	pq->head = NULL;
    15.  
    16. 	//将队尾结点置为空：
    17. 	pq->tail = NULL;
    18.  
    19. 	//队列结点(元素)个数置为0：
    20. 	pq->size = 0;
    21. }
    22.  
    23.  
    24.  
    25. //队列销毁函数 -- 将队列销毁
    26. //接收队列类型指针(包含链表头尾结点) 
    27. void QueueDestroy(Que* pq)
    28. {
    29. 	//assert断言队列类型指针不为空：
    30. 	assert(pq != NULL);
    31.  
    32. 	//释放队列跟单链表的释放一样
    33. 	//先创建一个在队列进行遍历的指针：
    34. 	QNode* cur = pq->head; //从队头结点开始
    35.  
    36. 	//使用while循环进行遍历释放队列结点：
    37. 	while (cur != NULL)	
    38. 	{
    39. 		//先保存下个结点：
    40. 		QNode* next = cur->next;
    41.  
    42. 		//再释放当前结点：
    43. 		free(cur);
    44.  
    45. 		//再指向下个结点：
    46. 		cur = next;
    47. 	}
    48.  
    49. 	//结点都释放后，把队头队尾指针都置空：
    50. 	pq->head = NULL;
    51. 	pq->tail = NULL;
    52.  
    53. 	//再把队列结点(元素)个数置为0：
    54. 	pq->size = 0;
    55. }
    56.  
    57.  
    58.  
    59. //队列入队函数 -- 用链表的尾插操作实现入队
    60. //接收队列类型指针(包含链表头尾结点) 、尾插值
    61. void QueuePush(Que* pq, QDataType x)
    62. {
    63. 	//assert断言队列类型指针不为空：
    64. 	assert(pq != NULL);
    65.  
    66. 	//入队放入元素需要空间，
    67. 	//所以要先为队列结点开辟动态空间：
    68. 	QNode* newnode = (QNode*)malloc(sizeof(QNode));
    69. 	//检查是否开辟成功：
    70. 	if (newnode == NULL)
    71. 	{
    72. 		//开辟失败则打印错误信息：
    73. 		perror("malloc fail");
    74. 		//终止程序：
    75. 		exit(-1);
    76. 	}
    77.  
    78. 	//队列结点完成后将尾插值(x)
    79. 	//赋给队列结点数据域：
    80. 	newnode->data = x;
    81. 	//指针域指向空：
    82. 	newnode->next = NULL;
    83.  
    84. 	//空间开辟后进行尾插：
    85. 	if (pq->tail == NULL)
    86. 		//如果队列刚初始化，队列为空，
    87. 		//头结点指针和尾结点指针都为空：
    88. 	{
    89. 		//那么将刚开辟的结点newnode地址
    90. 		//赋给头结点指针和尾结点指针
    91. 		pq->head = newnode;
    92. 		pq->tail = newnode;
    93. 	}
    94. 	else
    95. 		//队列不为空，进行尾插：
    96. 	{
    97. 		//将目前队尾结点指针域next指向尾插结点：
    98. 		pq->tail->next = newnode;
    99. 		//然后再指向尾插结点，成为新队尾结点：
    100. 		pq->tail = newnode;
    101. 	}
    102.  
    103. 	//插入数据后队列结点(元素)个数++：
    104. 	pq->size++;
    105. }
    106.  
    107.  
    108.  
    109. //队列出队函数 -- 用链表的头删操作实现出队
    110. //接收队列类型指针(包含链表头尾结点) 
    111. void QueuePop(Que* pq)
    112. {
    113. 	//assert断言队列类型指针不为空：
    114. 	assert(pq != NULL);
    115. 	//assert断言队列不为空，没数据不能删除：  
    116. 	assert(QueueEmpty(pq) != true); //不为空就继续程序
    117.  
    118. 	//如果队列中只剩一个结点：
    119. 	if (pq->head->next == NULL)
    120. 		//队头指针指向空，说明只剩一个结点，
    121. 		//只剩一个结点说明队头队尾指针都指向这一个结点，
    122. 		//所以这时头删后头指针移动，尾指针也要移动
    123. 	{
    124. 		//先释放("删除")队列目前头结点：
    125. 		free(pq->head);
    126.  
    127. 		//删除后将队头队尾指针都置为空：
    128. 		pq->head = NULL;
    129. 		pq->tail = NULL;
    130. 	}
    131. 	else
    132. 		//队列不止一个结点，则头删后只需移动队头结点：
    133. 	{
    134. 		//用链表的头删操作实现出队,
    135. 		//先保存第二个结点地址：
    136. 		QNode* next = pq->head->next;
    137.  
    138. 		//释放("删除")队列目前头结点：
    139. 		free(pq->head);
    140.  
    141. 		//再将队头结点指针指向原本第二个结点next，
    142. 		//让其成为新的队头结点：
    143. 		pq->head = next;
    144. 	}
    145.  
    146. 	//“删除”后队列结点(元素)个数--：
    147. 	pq->size--; 
    148. }
    149.  
    150.  
    151.  
    152. //队头函数 -- 返回队头结点的数据域数据
    153. //接收队列类型指针(包含链表头尾结点) 
    154. QDataType QueueFront(Que* pq)
    155. {
    156. 	//assert断言队列类型指针不为空：
    157. 	assert(pq != NULL);
    158. 	//assert断言队列不为空，没数据不能查找：  
    159. 	assert(QueueEmpty(pq) != true); //不为空就继续程序
    160.  
    161. 	//队列有数据，则直接返回队头结点数据域数据：
    162. 	return pq->head->data;
    163. }
    164.  
    165.  
    166.  
    167. //队尾函数 -- 返回队尾结点的数据域数据
    168. //接收队列类型指针(包含链表头尾结点) 
    169. QDataType QueueBack(Que* pq)
    170. {
    171. 	//assert断言队列类型指针不为空：
    172. 	assert(pq != NULL);
    173. 	//assert断言队列不为空，没数据不能查找：  
    174. 	assert(QueueEmpty(pq) != true); //不为空就继续程序
    175.  
    176. 	//队列有数据，则直接返回队尾结点数据域数据：
    177. 	return pq->tail->data;
    178. }
    179.  
    180.  
    181.  
    182. //判空函数 -- 判断队列是否为空
    183. //接收队列类型指针(包含链表头尾结点) 
    184. bool QueueEmpty(Que* pq)
    185. {
    186. 	//assert断言队列类型指针不为空：
    187. 	assert(pq != NULL);
    188.  
    189. 	//直接判断队头结点指向的下个结点是否为空：
    190. 	return pq->head == NULL; 
    191. 	//是则返回true -- 队列为空
    192. 	//是则返回false -- 队列不为空
    193. }
    194.  
    195.  
    196. //队列大小函数 -- 判断队列结点(元素)个数
    197. //接收队列类型指针(包含链表头尾结点) 
    198. int QueueSize(Que* pq)
    199. {
    200. 	//assert断言队列类型指针不为空：
    201. 	assert(pq != NULL);
    202.  
    203. 	//直接返回size队列结点(元素)个数：
    204. 	return pq->size;
    205. }

                

                

    ---------------------------------------------------------------------------------------------

                    

    Test.c -- 队列测试文件

    1. #define _CRT_SECURE_NO_WARNINGS 1
    2.  
    3. //包含队列头文件：
    4. #include "Queue.h"
    5.  
    6. //队列测试函数：
    7. void TestQueue()
    8. {
    9. 	//创建队列类型：
    10. 	Que q;
    11.  
    12. 	//对队列类型进行初始化：
    13. 	QueueInit(&q);
    14.  
    15. 	//进行入队操作：
    16. 	QueuePush(&q, 1);
    17. 	QueuePush(&q, 2);
    18. 	QueuePush(&q, 3);
    19. 	QueuePush(&q, 4);
    20. 	QueuePush(&q, 5);
    21.  
    22. 	//当前队尾值：
    23. 	printf("当前队尾值：%d\n", QueueBack(&q));
    24.  
    25. 	//当前队列元素个数：
    26. 	printf("当前队列元素个数：%d\n", QueueSize(&q));
    27.  
    28. 	//换行：
    29. 	printf("\n");
    30.  
    31. 	//使用while循环遍历进行出队：
    32. 	//（类似抽号机，当前号抽完就到下个号）
    33. 	while (!QueueEmpty(&q))
    34. 		//队列不为空就继续出队：
    35. 	{
    36. 		//打印出队值：
    37. 		printf("当前出队值为：%d\n", QueueFront(&q));
    38. 		//进行出队：
    39. 		QueuePop(&q); //出队后打印下个出队值
    40. 	}
    41.  
    42. 	//换行：
    43. 	printf("\n");
    44.  
    45. 	//当前队列元素个数：
    46. 	printf("当前队列元素个数：%d", QueueSize(&q));
    47.  
    48. 	//销毁队列：
    49. 	QueueDestroy(&q);
    50. }
    51.  
    52. //主函数：
    53. int main()
    54. {
    55. 	//调用队列测试函数：
    56. 	TestQueue();
    57.  
    58. 	return 0;
    59. }
  • 相关阅读:
    前端开发面试题—Vue的生命周期
    docker安装nginx并挂载
    zookeeper集群部署
    第一章：开始【C++Primer 第五版】
    Windows安装MongoDB及配置
    【AI原理解析】— GPT-4o模型
    DBever SQL编辑器的高级应用：如何用变量快速查询
    【qml】QML | 创建自定义组件（02）
    c++编译使用log4cplus
    【汇编语言02】第2章 寄存器——理论知识
  • 原文地址：https://blog.csdn.net/weixin_63176266/article/details/133191346