devbox
繁依Fanyi0
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

＜ 数据结构 ＞ 队列的实现_队列的实现csdn

作者：繁依Fanyi0 | 2024-05-08 06:23:41

赞

踩

队列的实现csdn

目录

前言

        队列的概念

        队列的结构

        队列的应用场景

队列的实现

        创建队列结构

        队列初始化

        队列销毁

        入队列

        出队列

        队列判空

        获取队列元素个数

        获取队列头部元素

        获取队列尾部元素

总代码

        Queue.h 文件

        Queue.c 文件

        Test.c 文件

前言

队列的概念

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

队列和前文所学的栈还是有一定区别的，队列明确指出先进先出。假如说一个队列的入队顺序为A B C D，那么出队顺序一定为A B C D，因为无论你是在A进去再出来，然后B进去再出来接着CD进去再出来或者类似的，都不会影响它最终的出队顺序A B C D。这点和栈还是有区别的，毕竟栈是后进先出。

队列的结构

队列的应用场景

队列：

  1. 公平排队
  2. 广度优先遍历 ……

栈：

  1. 解决括号匹配
  2. 逆波兰表达式求解
  3. 递归改非递归 ……

队列的实现

  • 在实现之前，首先得考虑用哪种结构好，是用数组结构还是链式结构呢？上文的栈我们使用的是数组结构，难道队列也要用吗？
  • 其实不然。应该使用链式结构。前文栈删除数据不需要挪动数据，使用数组结构即可满足需求，而队列在删除数据时需要把后面的数据挪到前面，使用链式结构非常容易实现，只需改变节点指向即可，而数组结构想要实现挪动数据则非常麻烦。综上，使用链式结构是最优的。此外，单链表即可满足需求，不需要使用其余较为复杂的链式结构。

创建队列结构

  •  思路：

这里要定义两个结构体，除了要定义1个链式结构来记录各个节点外，还要定义一个结构来记录队头和队尾。以此方便后续的队尾入数据，队头出数据。

  • Queue.h 文件：
  1. //创建队列结构
  2. typedef int QDataType; //方便后续更改存储数据类型，本文以int为例
  3.  //创建队列节点
  4. typedef struct QueueNode
  5. {
  6. 	QDataType data; //存储数据
  7. 	struct QueueNode* next; //记录下一个节点
  8. }QNode;
  9.  //保存队头和队尾
  10. typedef struct Queue
  11. {
  12. 	QNode* head; //头指针
  13. 	QNode* tail; //尾指针
  14. }Queue;

队列初始化

  •  思路：

队列可以为空，但是管理头指针和尾指针的结构体不能为空，所以一开始就要断言。其次，在插入数据前，队列肯定是空的，所以直接把头指针和尾指针置空即可。

  • Queue.h 文件：
  1. //初始化队列
  2. void QueueInit(Queue* pq);
  • Queue.c 文件：
  1. //初始化队列
  2. void QueueInit(Queue* pq)
  3. {
  4. 	assert(pq);
  5. 	pq->head = pq->tail = NULL;
  6. }

队列销毁

  •  思路：

销毁队列就是把队列的每个数据都销毁掉，那么需要遍历链表进行挨个销毁free。首先定义一个cur指针为pq->head，用来保存第一个数据，遍历cur，如果不为空，就free。最后把tail和head置空即可。

  • Queue.h 文件：
  1. //销毁队列
  2. void QueueDestory(Queue* pq);
  • Queue.c 文件：
  1. //销毁队列
  2. void QueueDestory(Queue* pq)
  3. {
  4. 	assert(pq);
  5. 	QNode* cur = pq->head;
  6. 	while (cur)
  7. 	{
  8. 		QNode* next = cur->next;
  9. 		free(cur);
  10. 		cur = next;
  11. 	}
  12. 	pq->head = pq->tail = NULL;
  13. }

入队列

  •  思路：

入队列其实很简单，只需要尾插即可，首先要新创建一个节点来保存新插入的数据。但是在尾插之前要考虑如果一开始队列没有数据，为空，那么只需要把head和tail节点指向新节点newnode节点即可。相反的，如果一开始就有数据，那么只需正常尾插把tail的next指向新节点newnode，再把newnode赋给tail即可。

  • Queue.h 文件：
  1. //入队列
  2. void QueuePush(Queue* pq, QDataType x);
  •  Queue.c 文件：
  1. //入队列
  2. void QueuePush(Queue* pq, QDataType x)
  3. {
  4. 	assert(pq);
  5. 	//创建一个新节点保存数据
  6. 	QNode* newnode = (QNode*)malloc(sizeof(QNode));
  7. 	//暴力检测newnode，因为malloc的都要检测
  8. 	assert(newnode);
  9. 	newnode->next = NULL;
  10. 	newnode->data = x;
  11. 	//如果一开始没有数据，为空的情况
  12. 	if (pq->tail == NULL)
  13. 	{
  14. 		assert(pq->head == NULL);
  15. 		pq->head = pq->tail = newnode;
  16. 	}
  17. 	else
  18. 	{
  19. 		pq->tail->next = newnode;
  20. 		pq->tail = newnode;
  21. 	}
  22. }

出队列

  •  思路：

特殊情况：

这里在删除数据时，首先要考虑特殊情况，当删到只剩一个数据时，再删一次，此时数据是没了，不过head为空了，而tail变成野指针了，为了避免此现象的产生，单独讨论并置空head和tail即可。

一般情况：

此时只需要定义一个next指针保存head的下一个节点，将head移动到next即可，并把旧的head置空。

  •  Queue.h 文件：
  1. //出队列
  2. void QueuePop(Queue* pq);
  • Queue.c 文件：
  1. //出队列
  2. void QueuePop(Queue* pq)
  3. {
  4. 	assert(pq);
  5. 	assert(pq->head && pq->tail); //tail和head均不能为空
  6. 	//特殊：当删到head=tail的位置时
  7. 	if (pq->head->next == NULL)
  8. 	{
  9. 		free(pq->head);
  10. 		pq->head = pq->tail = NULL;
  11. 	}
  12. 	//一般情况
  13. 	else
  14. 	{
  15. 		//保存head的下一个节点
  16. 		QNode* next = pq->head->next;
  17. 		free(pq->head);
  18. 		pq->head = next;
  19. 	}
  20. }

队列判空

  •  思路：

如果head为空或者tail为空都是判空的条件，直接返回即可。

  • Queue.h 文件：
  1. //判空
  2. bool QueueEmpty(Queue* pq);
  • Queue.c 文件：
  1. //判空
  2. bool QueueEmpty(Queue* pq)
  3. {
  4. 	assert(pq);
  5. 	return pq->head == NULL;
  6. }

获取队列元素个数

  •  思路：

求元素个数其实不难，只需要定义一个cur指针为第一个数据pq->head，定义变量size来记录个数。依次遍历cur，不为空，size就++。这种遍历的思想不复杂，但时间复杂度达到O(N)，不是太好，想要O(1)的话可以直接在当初定义结构体时多定义一个size变量，专门用来记录有效元素个数，每次入队列size++，出队列size--。这样实现是比较好的，不过为了封装成一个独立模块，还是采用遍历的方式。如下：

  • Queue.h 文件：
  1. //获取有效元素个数
  2. size_t QueueSize(Queue* pq);
  • Queue.c 文件：
  1. //获取有效元素个数
  2. size_t QueueSize(Queue* pq)
  3. {
  4. 	assert(pq);
  5. 	QNode* cur = pq->head;
  6. 	size_t size = 0;
  7. 	while (cur)
  8. 	{
  9. 		size++;
  10. 		cur = cur->next;
  11. 	}
  12. 	return size;
  13. }

获取队列头部元素

  •  思路：

首先要断言头部不能为空，如果头部都为空了，那还怎么能获得头部元素，其次直接返回头部head的数据即可。

  • Queue.h 文件：
  1. //获取队头元素
  2. QDataType QueueFront(Queue* pq);
  • Queue.c 文件：
  1. //获取队头元素
  2. QDataType QueueFront(Queue* pq)
  3. {
  4. 	assert(pq);
  5. 	assert(pq->head); //头部不能为空
  6. 	return pq->head->data;
  7. }

获取队列尾部元素

  •  思路：

有了获取队头元素的经验，队尾就更简单了，把head换位tail即可，结构与上文一样。

  • Queue.h 文件：
  1. //获取队尾元素
  2. QDataType QueueBack(Queue* pq);
  • Queue.c 文件：
  1. //获取队尾元素
  2. QDataType QueueBack(Queue* pq)
  3. {
  4. 	assert(pq);
  5. 	assert(pq->tail); //尾部不能为空
  6. 	return pq->tail->data;
  7. }

总代码

Queue.h 文件

  1. #pragma once
  2. #include<stdio.h>
  3. #include<stdlib.h>
  4. #include<assert.h>
  5. #include<stdbool.h>
  6.  
  7. //创建队列结构
  8. typedef int QDataType; //方便后续更改存储数据类型，本文以int为例
  9.  //创建队列节点
  10. typedef struct QueueNode
  11. {
  12. 	QDataType data; //存储数据
  13. 	struct QueueNode* next; //记录下一个节点
  14. }QNode;
  15.  //保存队头和队尾
  16. typedef struct Queue
  17. {
  18. 	QNode* head; //头指针
  19. 	QNode* tail; //尾指针
  20. }Queue;
  21.  
  22. //初始化队列
  23. void QueueInit(Queue* pq);
  24.  
  25. //销毁队列
  26. void QueueDestory(Queue* pq);
  27.  
  28. //入队列
  29. void QueuePush(Queue* pq, QDataType x);
  30.  
  31. //出队列
  32. void QueuePop(Queue* pq);
  33.  
  34. //判空
  35. bool QueueEmpty(Queue* pq);
  36.  
  37. //获取有效元素个数
  38. size_t QueueSize(Queue* pq);
  39.  
  40. //获取队头元素
  41. QDataType QueueFront(Queue* pq);
  42.  
  43. //获取队尾元素
  44. QDataType QueueBack(Queue* pq);

Queue.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 = pq->tail = NULL;
  9. }
  10.  
  11. //销毁队列
  12. void QueueDestory(Queue* pq)
  13. {
  14. 	assert(pq);
  15. 	QNode* cur = pq->head;
  16. 	while (cur)
  17. 	{
  18. 		QNode* next = cur->next;
  19. 		free(cur);
  20. 		cur = next;
  21. 	}
  22. 	pq->head = pq->tail = NULL;
  23. }
  24.  
  25. //入队列
  26. void QueuePush(Queue* pq, QDataType x)
  27. {
  28. 	assert(pq);
  29. 	//创建一个新节点保存数据
  30. 	QNode* newnode = (QNode*)malloc(sizeof(QNode));
  31. 	//暴力检测newnode，因为malloc的都要检测
  32. 	assert(newnode);
  33. 	newnode->next = NULL;
  34. 	newnode->data = x;
  35. 	//如果一开始没有数据，为空的情况
  36. 	if (pq->tail == NULL)
  37. 	{
  38. 		assert(pq->head == NULL);
  39. 		pq->head = pq->tail = newnode;
  40. 	}
  41. 	else
  42. 	{
  43. 		pq->tail->next = newnode;
  44. 		pq->tail = newnode;
  45. 	}
  46. }
  47.  
  48. //出队列
  49. void QueuePop(Queue* pq)
  50. {
  51. 	assert(pq);
  52. 	assert(pq->head && pq->tail); //tail和head均不能为空
  53. 	//特殊：当删到head=tail的位置时
  54. 	if (pq->head->next == NULL)
  55. 	{
  56. 		free(pq->head);
  57. 		pq->head = pq->tail = NULL;
  58. 	}
  59. 	//一般情况
  60. 	else
  61. 	{
  62. 		//保存head的下一个节点
  63. 		QNode* next = pq->head->next;
  64. 		free(pq->head);
  65. 		pq->head = next;
  66. 	}
  67. }
  68.  
  69. //判空
  70. bool QueueEmpty(Queue* pq)
  71. {
  72. 	assert(pq);
  73. 	return pq->head == NULL;
  74. }
  75.  
  76. //获取有效元素个数
  77. size_t QueueSize(Queue* pq)
  78. {
  79. 	assert(pq);
  80. 	QNode* cur = pq->head;
  81. 	size_t size = 0;
  82. 	while (cur)
  83. 	{
  84. 		size++;
  85. 		cur = cur->next;
  86. 	}
  87. 	return size;
  88. }
  89.  
  90. //获取队头元素
  91. QDataType QueueFront(Queue* pq)
  92. {
  93. 	assert(pq);
  94. 	assert(pq->head); //头部不能为空
  95. 	return pq->head->data;
  96. }
  97.  
  98. //获取队尾元素
  99. QDataType QueueBack(Queue* pq)
  100. {
  101. 	assert(pq);
  102. 	assert(pq->tail); //尾部不能为空
  103. 	return pq->tail->data;
  104. }

Test.c 文件

  1. #define _CRT_SECURE_NO_WARNINGS 1
  2. #include"Queue.h"
  3. void TestQueue()
  4. {
  5. 	Queue q;
  6. 	QueueInit(&q);
  7. 	//插入数据
  8. 	QueuePush(&q, 1);
  9. 	QueuePush(&q, 2);
  10. 	QueuePush(&q, 3);
  11. 	QueuePush(&q, 4);
  12. 	//打印
  13. 	while (!QueueEmpty(&q))
  14. 	{
  15. 		printf("%d ", QueueFront(&q));
  16. 		QueuePop(&q);
  17. 	}
  18. 	printf("\n");
  19. }
  20. int main()
  21. {
  22. 	TestQueue();
  23. 	return 0;
  24. }
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/繁依Fanyi0/article/detail/553242
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号