• 数据结构初阶：队列

    目录

    一、队列的概念和结构

    二、队列的实现

            定义队列结构

            初始化队列

            销毁队列

            检测队列是否为空

            入队列 

            出队列

            获取队列头部元素 

            获取队列队尾元素 

            获取队列中有效元素个数

                    优化

    三、测试

     四、优化后的全部代码

    一、队列的概念和结构

    队列:只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First ln First Out)的特点

    入队列:进行插入操作的一端称为队尾。

    出队列:进行删除操作的一端称为队头。

    就像现实生活中排队做核酸一样，从队的一段排队进入，从队的另一端做完出去：

    二、队列的实现

    队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，无论在数组头上出数据还是在数组头上插入数据，效率都会比较低（要重新移动元素）。

            定义队列结构

    在正式实现队列之前，我们先要确定队列的结构：

    我们基于链表的存储结构来实现队列，所以我们队列中需要一个指向链表头的指针_front（来作为队列的队头）和一个指向链表尾部的指针_rear（来作为队列的队尾）。

    1. //数据
    2. typedef int QDataType;
    3. //链表节点
    4. typedef struct QListNode
    5. {
    6. 	struct QListNode* _next;
    7. 	QDataType _data;
    8. }QNode;
    9. // 队列的结构 
    10. typedef struct Queue
    11. {
    12. 	QNode* _front;//队头
    13. 	QNode* _rear;//队尾
    14. }Queue;

    注：这里的对int类型进行重定义是为了我们更好的看懂QDataType只是一种数据而不仅仅是int类型。所以我们在使用队列时存储的数据并不限制于int类型，这里仅仅是举例。

            初始化队列

    1. void QueueInit(Queue* q)
    2. {
    3. 	assert(q);//传入的指针不能为空
    4. 	//将队头和队尾指针都初始化为空
    5. 	q->_front = NULL;
    6. 	q->_rear = NULL;
    7. }

            销毁队列

    1. void QueueDestroy(Queue* q)
    2. {
    3. 	assert(q);//传入的指针不能为空
    4. 	QNode* cur = q->_front;
    5. 	//释放链表空间
    6. 	while (cur)
    7. 	{
    8. 		QNode* del = cur;
    9. 		cur = cur->_next;
    10. 		free(del);
    11. 	}
    12. 	//将队头和队尾指针置空(防止野指针的产生)
    13. 	q->_front = q->_rear = NULL;
    14. }

            检测队列是否为空

    1. bool QueueEmpty(Queue* q)
    2. {
    3. 	assert(q);//传入的指针不能为空
    4. 	return q->_front == NULL && q->_rear == NULL;//如果队头队尾指针都为空返回的就是真值
    5. }

            入队列 

    1. void QueuePush(Queue* q, QDataType data)
    2. {
    3. 	assert(q);//传入的指针不能为空
    4. 	QNode* newnode = (QNode*)malloc(sizeof(QNode));//为新元素开辟空间
    5. 	if (newnode == NULL)//判断是否开辟成功
    6. 	{
    7. 		perror("malloc");
    8. 		exit(-1);
    9. 	}
    10. 	newnode->_data = data;
    11. 	newnode->_next = NULL;
    12. 	//注意这里尾插时要判断队中是否为空，是空的话需要改变队头和队尾指针的指向
    13. 	if (QueueEmpty(q))
    14. 	{
    15. 		q->_front = q->_rear = newnode;
    16. 	}
    17. 	else
    18. 	{
    19. 		q->_rear->_next = newnode;
    20. 		q->_rear = q->_rear->_next;
    21. 	}
    22. }

            出队列

    1. void QueuePop(Queue* q)
    2. {
    3. 	assert(q);//传入的指针不能为空
    4. 	assert(!QueueEmpty(q));//队列不能为空
    5. 	QNode* del = q->_front;
    6. 	//注意这里尾插时要判断队中是否为空，如果是的话需要将队头队尾指针置为空
    7. 	if (q->_front == q->_rear)
    8. 	{
    9. 		q->_front = q->_rear = NULL;
    10. 	}
    11. 	else
    12. 	{
    13. 		q->_front = q->_front->_next;
    14. 	}
    15. 	free(del);//释放节点空间
    16. }

            获取队列头部元素 

    1. QDataType QueueFront(Queue* q)
    2. {
    3. 	assert(q);//传入的指针不能为空
    4. 	assert(!QueueEmpty(q));//队列不能为空
    5. 	return q->_front->_data;//返回队列头部元素
    6. }

            获取队列队尾元素 

    1. QDataType QueueBack(Queue* q)
    2. {
    3. 	assert(q);//传入的指针不能为空
    4. 	assert(!QueueEmpty(q));//队列不能为空
    5. 	return q->_rear->_data;//返回队列队尾元素
    6. }

            获取队列中有效元素个数

    1. int QueueSize(Queue* q)
    2. {
    3. 	assert(q);//传入的指针不能为空
    4. 	int size = 0;
    5. 	QNode* cur = q->_front;
    6. 	//遍历累计节点总个数
    7. 	while (cur)
    8. 	{
    9. 		cur = cur->_next;
    10. 		size++;
    11. 	}
    12. 	return size;//返回累计的个数
    13. }

    直到这里所以的函数的时间复杂度都是O(1)，只有获取队列中有效元素个数（QueueSize）函数的时间复杂度为O(n)，我们可以稍微改变一下队列的结构来优化一下算法，使QueueSize函数的时间复杂度变为O(1)：

                    优化

    将队列结构加上一个记录节点总数的变量:

    1. //数据
    2. typedef int QDataType;
    3. //链表节点
    4. typedef struct QListNode
    5. {
    6. 	struct QListNode* _next;
    7. 	QDataType _data;
    8. }QNode;
    9. // 队列的结构 
    10. typedef struct Queue
    11. {
    12. 	QNode* _front;//队头
    13. 	QNode* _rear;//队尾
    14.     int size;//记录节点总数
    15. }Queue;

    初始化队列时要将size变量置为0：

    1. void QueueInit(Queue* q)
    2. {
    3. 	assert(q);//传入的指针不能为空
    4. 	//将队头和队尾指针都初始化为空
    5. 	q->_front = NULL;
    6. 	q->_rear = NULL;
    7. 	q->size = 0;//置0
    8. }

    在每次入队列时，将size变量加1：

    1. void QueuePush(Queue* q, QDataType data)
    2. {
    3. 	assert(q);//传入的指针不能为空
    4. 	QNode* newnode = (QNode*)malloc(sizeof(QNode));//为新元素开辟空间
    5. 	if (newnode == NULL)//判断是否开辟成功
    6. 	{
    7. 		perror("malloc");
    8. 		exit(-1);
    9. 	}
    10. 	newnode->_data = data;
    11. 	newnode->_next = NULL;
    12. 	//注意这里尾插时要判断队中是否为空，是空的话需要改变队头和队尾指针的指向
    13. 	if (QueueEmpty(q))
    14. 	{
    15. 		q->_front = q->_rear = newnode;
    16. 	}
    17. 	else
    18. 	{
    19. 		q->_rear->_next = newnode;
    20. 		q->_rear = q->_rear->_next;
    21. 	}
    22. 	q->size++;//加1
    23. }

    在每次出队列时，将size变量减1：

    1. void QueuePop(Queue* q)
    2. {
    3. 	assert(q);//传入的指针不能为空
    4. 	assert(!QueueEmpty(q));//队列不能为空
    5. 	QNode* del = q->_front;
    6. 	//注意这里尾插时要判断队中是否为空，如果是的话需要将队头队尾指针置为空
    7. 	if (q->_front == q->_rear)
    8. 	{
    9. 		q->_front = q->_rear = NULL;
    10. 	}
    11. 	else
    12. 	{
    13. 		q->_front = q->_front->_next;
    14. 	}
    15. 	free(del);//释放节点空间
    16. 	q->size--;//减1
    17. }

    销毁队列时记得将size变量置为0：

    1. void QueueDestroy(Queue* q)
    2. {
    3. 	assert(q);//传入的指针不能为空
    4. 	QNode* cur = q->_front;
    5. 	//释放链表空间
    6. 	while (cur)
    7. 	{
    8. 		QNode* del = cur;
    9. 		cur = cur->_next;
    10. 		free(del);
    11. 	}
    12. 	//将队头和队尾指针置空(防止野指针的产生)
    13. 	q->_front = q->_rear = NULL;
    14. 	q->size = 0;//置0
    15. }

    这样QueueSize函数的时间复杂度就能优化为O(1)了：

    1. int QueueSize(Queue* q)
    2. {
    3. 	assert(q);//传入的指针不能为空
    4. 	return q->size;//返回累计的个数
    5. }

    三、测试

    测试代码：

    1. void Test()
    2. {
    3. 	Queue q;
    4. 	QueueInit(&q);
    5. 	printf("队列中有效元素个数为：%d\n", QueueSize(&q));
    6. 	QueuePush(&q, 1);
    7. 	printf("队列中有效元素个数为：%d 队列头部元素为：%d 队列队尾元素为：%d\n", QueueSize(&q), QueueFront(&q), QueueBack(&q));
    8. 	QueuePush(&q, 2);
    9. 	printf("队列中有效元素个数为：%d 队列头部元素为：%d 队列队尾元素为：%d\n", QueueSize(&q), QueueFront(&q), QueueBack(&q));
    10. 	QueuePush(&q, 3);
    11. 	printf("队列中有效元素个数为：%d 队列头部元素为：%d 队列队尾元素为：%d\n", QueueSize(&q), QueueFront(&q), QueueBack(&q));
    12. 	QueuePush(&q, 4);
    13. 	printf("队列中有效元素个数为：%d 队列头部元素为：%d 队列队尾元素为：%d\n", QueueSize(&q), QueueFront(&q), QueueBack(&q));
    14. 	QueuePop(&q);
    15. 	printf("队列中有效元素个数为：%d 队列头部元素为：%d 队列队尾元素为：%d\n", QueueSize(&q), QueueFront(&q), QueueBack(&q));
    16. 	QueuePop(&q);
    17. 	printf("队列中有效元素个数为：%d 队列头部元素为：%d 队列队尾元素为：%d\n", QueueSize(&q), QueueFront(&q), QueueBack(&q));
    18. 	QueuePush(&q, 5);
    19. 	printf("队列中有效元素个数为：%d 队列头部元素为：%d 队列队尾元素为：%d\n", QueueSize(&q), QueueFront(&q), QueueBack(&q));
    20. 	QueueDestroy(&q);
    21. 	printf("队列中有效元素个数为：%d\n", QueueSize(&q));
    22. }

    测试效果：

     四、优化后的全部代码

    1. #include
    2. #include
    3. #include
    4. #include
    5. //数据
    6. typedef int QDataType;
    7. //链表节点
    8. typedef struct QListNode
    9. {
    10. 	struct QListNode* _next;
    11. 	QDataType _data;
    12. }QNode;
    13. // 队列的结构 
    14. typedef struct Queue
    15. {
    16. 	QNode* _front;//队头
    17. 	QNode* _rear;//队尾
    18. 	int size;//记录节点总数
    19. }Queue;
    20.  
    21. // 初始化队列 
    22. void QueueInit(Queue* q)
    23. {
    24. 	assert(q);//传入的指针不能为空
    25. 	//将队头和队尾指针都初始化为空
    26. 	q->_front = NULL;
    27. 	q->_rear = NULL;
    28. 	q->size = 0;//置0
    29. }
    30. // 检测队列是否为空
    31. bool QueueEmpty(Queue* q)
    32. {
    33. 	assert(q);//传入的指针不能为空
    34. 	return q->_front == NULL && q->_rear == NULL;//如果队头队尾指针都为空返回的就是真值
    35. }
    36. // 队尾入队列 
    37. void QueuePush(Queue* q, QDataType data)
    38. {
    39. 	assert(q);//传入的指针不能为空
    40. 	QNode* newnode = (QNode*)malloc(sizeof(QNode));//为新元素开辟空间
    41. 	if (newnode == NULL)//判断是否开辟成功
    42. 	{
    43. 		perror("malloc");
    44. 		exit(-1);
    45. 	}
    46. 	newnode->_data = data;
    47. 	newnode->_next = NULL;
    48. 	//注意这里尾插时要判断队中是否为空，是空的话需要改变队头和队尾指针的指向
    49. 	if (QueueEmpty(q))
    50. 	{
    51. 		q->_front = q->_rear = newnode;
    52. 	}
    53. 	else
    54. 	{
    55. 		q->_rear->_next = newnode;
    56. 		q->_rear = q->_rear->_next;
    57. 	}
    58. 	q->size++;//加1
    59. }
    60. // 队头出队列 
    61. void QueuePop(Queue* q)
    62. {
    63. 	assert(q);//传入的指针不能为空
    64. 	assert(!QueueEmpty(q));//队列不能为空
    65. 	QNode* del = q->_front;
    66. 	//注意这里尾插时要判断队中是否为空，如果是的话需要将队头队尾指针置为空
    67. 	if (q->_front == q->_rear)
    68. 	{
    69. 		q->_front = q->_rear = NULL;
    70. 	}
    71. 	else
    72. 	{
    73. 		q->_front = q->_front->_next;
    74. 	}
    75. 	free(del);//释放节点空间
    76. 	q->size--;//减1
    77. }
    78. // 获取队列头部元素 
    79. QDataType QueueFront(Queue* q)
    80. {
    81. 	assert(q);//传入的指针不能为空
    82. 	assert(!QueueEmpty(q));//队列不能为空
    83. 	return q->_front->_data;//返回队列头部元素
    84. }
    85. // 获取队列队尾元素 
    86. QDataType QueueBack(Queue* q)
    87. {
    88. 	assert(q);//传入的指针不能为空
    89. 	assert(!QueueEmpty(q));//队列不能为空
    90. 	return q->_rear->_data;//返回队列队尾元素
    91. }
    92. // 获取队列中有效元素个数 
    93. int QueueSize(Queue* q)
    94. {
    95. 	assert(q);//传入的指针不能为空
    96. 	return q->size;//返回累计的个数
    97. }
    98. // 销毁队列 
    99. void QueueDestroy(Queue* q)
    100. {
    101. 	assert(q);//传入的指针不能为空
    102. 	QNode* cur = q->_front;
    103. 	//释放链表空间
    104. 	while (cur)
    105. 	{
    106. 		QNode* del = cur;
    107. 		cur = cur->_next;
    108. 		free(del);
    109. 	}
    110. 	//将队头和队尾指针置空(防止野指针的产生)
    111. 	q->_front = q->_rear = NULL;
    112. 	q->size = 0;//置0
    113. }

    本期博客到这里就结束了，代码量较多如有纰漏还请各位大佬不吝赐教！

    谢谢各位看客的支持，我们下期见~

  • 相关阅读:
    【算法篇-数论】快速幂
    简单个人网页制作 个人介绍网页模板 静态HTML留言表单页面网站模板 大学生个人主页网页
    Ansible初识、提高小记（基于CentOS7.5,附带实验源文件）
    JVM的内存结构
    RestTemplate用法
    人工智能大模型之开源大语言模型汇总（国内外开源项目模型汇总）
    阿里云短信验证项目整合
    今日学习 Mybatis 的关联映射
    4-10构造器
    接口测试框架：Http+Requests（1）
  • 原文地址：https://blog.csdn.net/m0_70811813/article/details/127992859