• [C语言数据结构]队列

    目录

    1.队列

    1.1队列的概念及结构

    2.队列的实现

    2.1队列的实现

    2.1.1声明

    2.1.2初始化

    2.1.3队列的销毁

    2.1.4入队列

    2.1.5出队列

    2.1.6返回队列的首元素

    2.1.7判断队列是否为空

    2.1.8计算队列中元素的数量

    int QueueSize(Queue* pq);

    完整代码：

    Quene.h：

    Quene.c：

    1.队列

    1.1队列的概念及结构

    只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out) 入队列：进行插入操作的一端称为队尾 出队列：进行删除操作的一端称为队头。即：先进先出

    2.队列的实现

    首先我们可以讨论一下，用数组实现好还是用队列实现好一些；

    对于队列我们要进行入队和出队的操作，如果是使用数组来实现的话，那么我们所需要的时间开销就很大，需要不停的挪动数据。

    但是反过来看链表的话，就方便了许多，不需要频繁的挪动数据，入队出队时的操作都显得相对容易和快速。

    所以接下来我们将采用单链表的方式来实现队列。

    2.1队列的实现

    2.1.1声明

    对于队列来说，我们采用单链表的形式来实现队列所以我们声明结构的形式和单链表几乎一样。一个区别队列这个为了方便入列出列，用了两个指针，一个用来指向头节点，另一个来指向尾节点。还有一个正整型变量用来记录队列的大小；

    代码：

    1. typedef int QdataType;
    2.  
    3. typedef struct QueueNode
    4. {
    5. 	QdataType data;
    6. 	struct QueueNode* next;
    7.  
    8. }QueueNode;
    9.  
    10. typedef struct Queue
    11. {
    12. 	QueueNode* head;
    13. 	QueueNode* tail;
    14. 	size_t size;
    15. }Queue;

    2.1.2初始化

    void QueueInit(Queue* pq);

    初始化也是非常的简单，就是将头指针和尾指针来置空，防止野指针的问题；

    代码：

    1. //队列的初始化
    2. void QueueInit(Queue* pq)
    3. {
    4. 	assert(pq);
    5. 	pq->head = NULL;
    6. 	pq->tail = NULL;
    7. 	pq->size = 0;
    8. }

    2.1.3队列的销毁

    void QueueDestroy(Queue* pq);

    对于队列的销毁，和单链表的销毁大同小异，都是从头开始一次进行free，代码实现不难；

    代码：

    1. //队列的销毁
    2. void QueueDestroy(Queue* pq)
    3. {
    4. 	assert(pq);
    5. 	QueueNode* cur = pq->head;
    6. 	while (cur != NULL)
    7. 	{
    8. 		QueueNode* next = cur->next;
    9. 		free(cur);
    10. 		cur = next;
    11. 	}
    12. 	pq->head = pq->tail = NULL;
    13. }

    2.1.4入队列

    入队列的话我们直接时进行一个尾插，但是我们这里采用的是无头的单链表，所以在这里我们要先判断一下，队列中是否有元素，如果有元素的话我们将头和尾都指向新插入的节点；

    如果不是的话那就直接进行一个尾插

    void QueuePush(Queue* pq, QdataType x);
    代码：

    1. //入队列
    2. void QueuePush(Queue* pq, QdataType x)
    3. {
    4. 	assert(pq);
    5. 	QueueNode* NewNode = (QueueNode*)malloc(sizeof(QueueNode));
    6. 	NewNode->next = NULL;
    7. 	NewNode->data = x;
    8. 	if (pq->head == NULL)
    9. 	{
    10. 		pq->head = NewNode;
    11. 		pq->tail = NewNode;
    12. 	}
    13. 	else
    14. 	{
    15. 		pq->tail->next = NewNode;
    16. 		pq->tail = NewNode;
    17. 	}
    18. }

    2.1.5出队列

    出队列的时候我们要注意一种情况就是是当队列中只剩一个节点的情况需要进行特殊的处理；因为剩余一个节点的时候我们和多个节点同样处理的话，就会产生尾节点是野指针的情况；

    void QueuePop(Queue* pq);

    代码：

    1. //出队列
    2. void QueuePop(Queue* pq)
    3. {
    4. 	assert(pq);
    5. 	assert(!QueueEmpty(pq));
    6. 	//剩余一个节点的情况
    7. 	if (pq->head->next == NULL)
    8. 	{
    9. 		free(pq->head);
    10. 		pq->head = pq->tail = NULL;
    11. 	}
    12. 	else
    13. 	{
    14. 		QueueNode* del = pq->head;
    15. 		pq->head = pq->head->next;
    16. 		free(del);
    17. 	}
    18. }

    2.1.6返回队列的首元素

    这个函数没什么说的，唯一要注意的就是就要判断队列中是否还存在元素的情况，这个也可以非常的简单因为采用assert来判断就好了；

    QdataType QueueFront(Queue* pq);

    代码：

    1. //返回队列的首元素
    2. QdataType QueueFront(Queue* pq)
    3. {
    4. 	assert(pq);
    5. 	assert(!QueueEmpty(pq));
    6. 	return pq->head->data;
    7. }

    2.1.7判断队列是否为空

    bool QueueEmpty(Queue* pq);

    1. //判断队列是否为空
    2. bool QueueEmpty(Queue* pq)
    3. {
    4. 	assert(pq);
    5. 	return pq->head == NULL && pq->tail == NULL;
    6. }

    2.1.8计算队列中元素的数量

    直接返回队列的size即可；相对于遍历整个队列的方法来说，效率更高；

    int QueueSize(Queue* pq);

    代码：

    1. //队列的大小
    2. int QueueSize(Queue* pq) 
    3. {
    4.  
    5. 	return pq->size;
    6. }

    完整代码：

    Quene.h：

    1. #define _CRT_SECURE_NO_WARNINGS 1
    2. #include
    3. #include
    4. #include
    5. #include
    6.  
    7.  
    8. typedef int QdataType;
    9.  
    10. typedef struct QueueNode
    11. {
    12. 	QdataType data;
    13. 	struct QueueNode* next;
    14.  
    15. }QueueNode;
    16.  
    17. typedef struct Queue
    18. {
    19. 	QueueNode* head;
    20. 	QueueNode* tail;
    21. 	size_t size;
    22. }Queue;
    23.  
    24.  
    25. //队列的初始化
    26. void QueueInit(Queue* pq);
    27.  
    28. //队列的销毁
    29. void QueueDestroy(Queue* pq);
    30.  
    31. //入队列
    32. void QueuePush(Queue* pq, QdataType x);
    33.  
    34. //出队列
    35. void QueuePop(Queue* pq);
    36.  
    37. //返回队列的首元素
    38. QdataType QueueFront(Queue* pq);
    39.  
    40. //返回队列的尾部元素
    41. QdataType QueueBack(Queue* pq);
    42.  
    43. //队列的大小
    44. int QueueSize(Queue* pq);
    45.  
    46. //判断队列是否为空
    47. bool QueueEmpty(Queue* pq);

    Quene.c：

    代码：

    1. #define _CRT_SECURE_NO_WARNINGS 1
    2. #include"Queue.h"
    3.  
    4. //队列的初始化
    5. void QueueInit(Queue* pq)
    6. {
    7. 	assert(pq);
    8. 	pq->head = NULL;
    9. 	pq->tail = NULL;
    10. 	pq->size = 0;
    11. }
    12.  
    13. //队列的销毁
    14. void QueueDestroy(Queue* pq)
    15. {
    16. 	assert(pq);
    17. 	QueueNode* cur = pq->head;
    18. 	while (cur != NULL)
    19. 	{
    20. 		QueueNode* next = cur->next;
    21. 		free(cur);
    22. 		cur = next;
    23. 	}
    24. 	pq->head = pq->tail = NULL;
    25. }
    26.  
    27. //入队列
    28. void QueuePush(Queue* pq, QdataType x)
    29. {
    30. 	assert(pq);
    31. 	QueueNode* NewNode = (QueueNode*)malloc(sizeof(QueueNode));
    32. 	NewNode->next = NULL;
    33. 	NewNode->data = x;
    34. 	if (pq->head == NULL)
    35. 	{
    36. 		pq->head = NewNode;
    37. 		pq->tail = NewNode;
    38. 	}
    39. 	else
    40. 	{
    41. 		pq->tail->next = NewNode;
    42. 		pq->tail = NewNode;
    43. 	}
    44. 	pq->size++;
    45. }
    46.  
    47. //出队列
    48. void QueuePop(Queue* pq)
    49. {
    50. 	assert(pq);
    51. 	assert(!QueueEmpty(pq));
    52. 	//剩余一个节点的情况
    53. 	if (pq->head->next == NULL)
    54. 	{
    55. 		free(pq->head);
    56. 		pq->head = pq->tail = NULL;
    57. 	}
    58. 	else
    59. 	{
    60. 		QueueNode* del = pq->head;
    61. 		pq->head = pq->head->next;
    62. 		free(del);
    63. 	}
    64. 	pq->size--;
    65. }
    66.  
    67. //返回队列的首元素
    68. QdataType QueueFront(Queue* pq)
    69. {
    70. 	assert(pq);
    71. 	assert(!QueueEmpty(pq));
    72. 	return pq->head->data;
    73. }
    74.  
    75. //返回队列的尾部元素
    76. QdataType QueueBack(Queue* pq)
    77. {
    78. 	assert(pq);
    79. 	assert(!QueueEmpty(pq));
    80. 	return pq->tail->data;
    81. }
    82.  
    83. //队列的大小
    84. int QueueSize(Queue* pq) 
    85. {
    86. 	//assert(pq);
    87. 	//int n = 0;
    88. 	//QueueNode* cur = pq->head;
    89. 	//while (cur)
    90. 	//{
    91. 	//	n++;
    92. 	//	cur = cur->next;
    93. 	//}
    94. 	//return n;
    95. 	return pq->size;
    96. }
    97.  
    98. //判断队列是否为空
    99. bool QueueEmpty(Queue* pq)
    100. {
    101. 	assert(pq);
    102. 	return pq->head == NULL && pq->tail == NULL;
    103. }

    以上就是队列的实现的所有内容了，希望可以帮到你！

  • 相关阅读:
    人工智能与光伏发电：携手共创智能能源未来
    一文搞懂临床预测模型的评价
    单链表头插法和尾插法
    【毕业设计】基于YOLO实现的口罩佩戴检测 - python opemcv 深度学习
    Redis基础特性及应用练习-php
    互联网数据管理平台
    基于php+mysql的房屋销售管理系统
    这测试谁爱做谁做，我反正不做了，4年工作经验去面试10分钟就结束了，现在大环境卷成这样了吗？
    【leetcode】2530.执行k次操作后的最大分数
    JAVA计算机毕业设计小型企业员工工资管理系统（附源码、数据库）
  • 原文地址：https://blog.csdn.net/weixin_61766635/article/details/127910408