深圳幻海软件技术有限公司 欢迎您！
更多

【数据结构】带你深度理解队列

2023-04-12

next 队列 pq
目录一.队列的基本概念💫二.队列实现方法的选择👉2.1引入2.2选择三.接口的实现✈3.1队列的声明3.2初始化和销毁3.3入队3.4出队3.5求队头元素3.6求队尾元素3.7判空3.8求队列的元素个数3.9总结四.完整代码及效果展示🌠一.队列的基本概念💫队列和我们之前学习的栈一样，它也是一

目录

一. 队列的基本概念💫

二. 队列实现方法的选择👉

2.1 引入

2.2 选择

三. 接口的实现✈

3.1 队列的声明

3.2 初始化和销毁

3.3 入队

3.4 出队

3.5 求队头元素

3.6 求队尾元素

3.7 判空

3.8 求队列的元素个数

3.9 总结

四. 完整代码及效果展示🌠

一. 队列的基本概念💫

队列和我们之前学习的栈一样，它也是一种特殊的线性表。它只允许在一端插入数据，在另一端删除数据，不允许对中间的元素进行操作，因而也不支持随机访问。队列具有先进先出的特性FIFO（(First In First Out）。

入队： 队列 的插入操作叫做入队，插入数据的一端称作队头
出队： 队列 的删除操作叫做出队，删除数据的一端称作队尾

我们结合动图来理解队列的先进先出：

二. 队列实现方法的选择👉

2.1 引入

    在上次栈的实现中，我们说到可以用顺序存储结构和链式存储结构来表示栈。经过之前我们的分析，我们选择了使用顺序表来实现栈，这是由于栈的插入删除操作完美适配顺序表尾插尾删效率高的特性。

有关两种方式的优缺点及比较，详细请参照往期文章：

【数据结构】带你深度理解栈

2.2 选择

    由于队列需要在两端进行操作，而顺序表在头部的操作效率很低，需要移动大量数据，直接pass掉。我们本期将采用单链表的形式来实现队列。特别的，为了提高单链表尾插的效率，除了必要的头指针我们又定义了一个尾指针指向链表的尾部，大幅提高了单链表尾插的效率。当然，实现队列的方式多种多样，并不是只能用单链表来实现队列。

三. 接口的实现✈

3.1 队列的声明

本文我们采用带有头尾指针的 单链表来实现队列，队列的结构体的声明如下： 
  1. //单链表的结点
  2. typedef int QueueDataType;
  3. typedef struct QueueNode
  4. {
  5. QueueDataType data;
  6. struct QueueNode* next;
  7. }QueueNode;
  8.  
  9. //队列结构体
  10. typedef struct Queue
  11. {
  12. QueueNode* first;   //队列头
  13. QueueNode* tail;    //队列尾
  14. }Queue;

老样子，我们不直接指定数据的类型，而是将类型重定义为STDataType，这样做有利于提高代码的可维护性。

3.2 初始化和销毁

在我们使用队列结构进行操作之前需要对其进行初始化，当我们不再使用它是要对它进行销毁，具体代码如下：

  1. //初始化队列
  2. void QueueInit(Queue* pq)
  3. {
  4. assert(pq);
  5. pq->first = pq->tail = NULL;//空队列，队头队尾指向空
  6. }
  7.  
  8. //销毁队列
  9. void QueueDestroy(Queue* pq)
  10. {
  11. assert(pq);
  12. QueueNode* cur = pq->first;
  13. //销毁每个结点
  14. while (cur)
  15. {
  16. QueueNode* next = cur->next;//先把下一个结点的位置保存起来，避免销毁后找不到
  17. free(cur);
  18. cur = next;
  19. }
  20. pq->first = pq->tail = NULL;//队头队尾置空
  21. }

3.3 入队

由于队列只允许在固定的一端插入，我们又将链表尾当做队尾，因此入队就是尾插。在没有尾指针之前，我们还要先找到链表尾，但我们现在有了尾指针，一切都方便起来了。效果和代码如下：  

  1. //创建结点
  2. static QueueNode* CreatNode(QueueDataType x)
  3. {
  4. QueueNode* ret=(QueueNode*)malloc(sizeof(QueueNode));
  5. if (ret == NULL)
  6. {
  7. printf("%s", strerror(errno));
  8. exit(-1);
  9. }
  10. ret->data = x;
  11. ret->next = NULL;
  12. return ret;
  13. }
  14.  
  15. //入队
  16. void QueueInsert(Queue* pq, QueueDataType x)
  17. {
  18. assert(pq);
  19. QueueNode* newnode = CreatNode(x);
  20. //为空队列
  21. if (pq->tail == NULL)
  22. {
  23. pq->first = pq->tail = newnode;
  24. }
  25. else
  26. {
  27. //在队尾插入
  28. pq->tail->next = newnode;
  29. pq->tail = newnode;
  30. }
  31. }

插入前我们先创建结点，封装成一个函数并用static修饰，取消其外部链接属性使得只能在本文件中使用，不允许外部调用。之前我们说过，单链表的尾插要考虑链表是不是为空的情况，避免对空指针进行解引用导致出错。这里也是，要判断队列是否为空，分情况处理。

3.4 出队

入队在链表尾，那么出队就是在链表头了；入队对应着链表的尾插，则出队就是头删。链表的头删很简单，只需要释放结点，将头指针指向下一个结点即可。效果如下：

但是，如果只是这样还不够！试想一下，当队列只剩下一个元素时，如果我们再进行出队，头指针没问题指向空，那尾指针呢？由于我们没有去修改，它指向了已经释放空间，显然是不合理的。因此在这种情况下我们还需将尾指针置为NULL。

  1. //出队
  2. void QueueErase(Queue* pq)
  3. {
  4. assert(pq&&pq->first);
  5. //需注意，当队列只有一个元素时，删除后除了要修改first指针，还要修改tail指针
  6.  
  7. QueueNode* next = pq->first->next;
  8. //只有一个元素
  9. if (next == NULL)
  10. {
  11. free(pq->first);
  12. pq->first = pq->tail=NULL;
  13. }
  14. else
  15. {
  16. //释放结点，修改头指针指向
  17. free(pq->first);
  18. pq->first = next;
  19. }
  20.  
  21. }

3.5 求队头元素

很简单，我们可以直接根据头指针得到队头的元素，如下：

  1. //求队头元素
  2. QueueDataType QueueFront(Queue* pq)
  3. {
  4. assert(pq);
  5. assert(pq->first);//队列不为空
  6. return pq->first->data;
  7. }

3.6 求队尾元素

一样的，通过尾指针可以快速定位队尾的位置，得到队尾的元素，如下：

  1. //求队尾元素
  2. QueueDataType QueueBack(Queue* pq)
  3. {
  4. assert(pq);
  5. assert(pq->tail);//队列不为空
  6. return pq->tail->data;
  7. }

3.7 判空

当队列为空时，队头指针和队尾指针都为NULL，我们选其一判断即可。代码如下：

  1. //判空
  2. //使用bool类型需包含stdbool.h头文件
  3. bool QueueEmpty(Queue* pq)
  4. {
  5. assert(pq);
  6. return pq->first == NULL;//如果为空返回true，不为空返回false
  7. }

3.8 求队列的元素个数

定义一个变量作为计数器，遍历链表并记录遍历过程中的结点个数：

  1. //求队列元素个数
  2. int QueueSize(Queue* pq)
  3. {
  4. assert(pq);
  5. int count = 0;
  6. QueueNode* cur = pq->first;
  7. //进行遍历直到为空
  8. while (cur)
  9. {
  10. count++;//计数器加1
  11. cur = cur->next;//指向下一结点
  12. }
  13. return count;
  14. }

3.9 总结

  • 与栈同理，队列也是一种限制型的数据结构，不支持随机访问。其只允许在固定的两端进行操作。因此也不存在查找，打印，修改等需要对其他位置进行操作的接口，否则会破坏队列的特性。
  • 数据结构的实现方式多种多样，为了在隐藏设计细节的情况下使用方依旧能够很方便的使用，尽管有一些操作仅仅只有一两行代码，我们还是封装成函数作为对外的接口供使用方调用。

四. 完整代码及效果展示🌠

老样子，我们采用多文件编写的形式，将上述接口的定义实现放在Queue.c文件中，然后将接口的声明和结构体的定义放于Queue.h头文件中，以达到封装的效果。这样我们如果需要使用队列，就只需要在文件中包含对应的头文件Queue.h就可以使用我们上面定义的各种接口。以下为本文实现的队列完整代码以及效果展示：

  1. //Queue.h文件，用于声明接口函数，定义结构体
  2. #pragma once
  3. #include<stdio.h>
  4. #include<stdlib.h>
  5. #include<stdbool.h>
  6. #include<string.h>
  7. #include<errno.h>
  8. #include<assert.h>
  9.  
  10. //单链表的结点
  11. typedef int QueueDataType;
  12. typedef struct QueueNode
  13. {
  14. QueueDataType data;
  15. struct QueueNode* next;
  16. }QueueNode;
  17.  
  18. //队列结构体
  19. typedef struct Queue
  20. {
  21. QueueNode* first;   //队列头
  22. QueueNode* tail;    //队列尾
  23. }Queue;
  24.  
  25. //初始化
  26. void QueueInit(Queue* pq);
  27.  
  28. //销毁
  29. void QueueDestroy(Queue* pq);
  30.  
  31. //插入
  32. void QueueInsert(Queue* pq, QueueDataType x);
  33.  
  34. //删除
  35. void QueueErase(Queue* pq);
  36.  
  37. //求队头元素
  38. QueueDataType QueueFront(Queue* pq);
  39.  
  40. //求队尾元素
  41. QueueDataType QueueBack(Queue* pq);
  42.  
  43. //求队列元素个数
  44. int QueueSize(Queue* pq);
  45.  
  46. //判空
  47. bool QueueEmpty(Queue* pq);
  1. //Queue.c文件，用于定义接口函数
  2. #include"Queue.h"
  3.  
  4. //初始化队列
  5. void QueueInit(Queue* pq)
  6. {
  7. assert(pq);
  8. pq->first = pq->tail = NULL;//空队列，队头队尾指向空
  9. }
  10.  
  11.  
  12. //销毁队列
  13. void QueueDestroy(Queue* pq)
  14. {
  15. assert(pq);
  16. QueueNode* cur = pq->first;
  17. //销毁每个结点
  18. while (cur)
  19. {
  20. QueueNode* next = cur->next;//先把下一个结点的位置保存起来，避免销毁后找不到
  21. free(cur);
  22. cur = next;
  23. }
  24. pq->first = pq->tail = NULL;//队头队尾置空
  25. }
  26.  
  27.  
  28. //创建结点
  29. static QueueNode* CreatNode(QueueDataType x)
  30. {
  31. QueueNode* ret=(QueueNode*)malloc(sizeof(QueueNode));
  32. if (ret == NULL)
  33. {
  34. printf("%s", strerror(errno));
  35. exit(-1);
  36. }
  37. ret->data = x;
  38. ret->next = NULL;
  39. return ret;
  40. }
  41.  
  42. //入队
  43. void QueueInsert(Queue* pq, QueueDataType x)
  44. {
  45. assert(pq);
  46. QueueNode* newnode = CreatNode(x);
  47. //为空队列
  48. if (pq->tail == NULL)
  49. {
  50. pq->first = pq->tail = newnode;
  51. }
  52. else
  53. {
  54. //在队尾插入
  55. pq->tail->next = newnode;
  56. pq->tail = newnode;
  57. }
  58.  
  59. }
  60.  
  61.  
  62. //出队
  63. void QueueErase(Queue* pq)
  64. {
  65. assert(pq&&pq->first);
  66. //需注意，当队列只有一个元素时，删除后除了要修改first指针，还要修改tail指针
  67.  
  68. QueueNode* next = pq->first->next;
  69. //只有一个元素
  70. if (next == NULL)
  71. {
  72. free(pq->first);
  73. pq->first = pq->tail=NULL;
  74. }
  75. else
  76. {
  77. //释放结点，修改头指针指向
  78. free(pq->first);
  79. pq->first = next;
  80. }
  81.  
  82. }
  83.  
  84. //求队头元素
  85. QueueDataType QueueFront(Queue* pq)
  86. {
  87. assert(pq);
  88. assert(pq->first);//队列不为空
  89. return pq->first->data;
  90. }
  91.  
  92. //求队尾元素
  93. QueueDataType QueueBack(Queue* pq)
  94. {
  95. assert(pq);
  96. assert(pq->tail);//队列不为空
  97. return pq->tail->data;
  98. }
  99.  
  100. //求队列元素个数
  101. int QueueSize(Queue* pq)
  102. {
  103. assert(pq);
  104. int count = 0;
  105. QueueNode* cur = pq->first;
  106. //进行遍历直到为空
  107. while (cur)
  108. {
  109. count++;//计数器加1
  110. cur = cur->next;//指向下一结点
  111. }
  112. return count;
  113. }
  114.  
  115. //判空
  116. bool QueueEmpty(Queue* pq)
  117. {
  118. assert(pq);
  119. return pq->first == NULL;//如果为空返回true，不为空返回false
  120. }

最后， 我们在test.c文件调用队列各个接口进行测试，如下：

  1. //test.c文件，用于测试
  2. #include"Queue.h"
  3.  
  4. void test01()
  5. {
  6. Queue que;
  7. //初始化
  8. QueueInit(&que);
  9. //求元素个数
  10. printf("入队前队列的元素个数为:%d\n", QueueSize(&que));
  11. //入队，插入5个元素
  12. for (int i = 1; i <= 5; i++)
  13. {
  14. QueueInsert(&que, i);
  15. }
  16. printf("入队后队列的元素个数为:%d\n", QueueSize(&que));
  17. //由于无法遍历打印，我们就交替使用 求队头元素-出队 来显示队中元素
  18. printf("队中元素:> ");
  19. while (!QueueEmpty(&que))
  20. {
  21. //求队头元素
  22. printf("%d ", QueueFront(&que));
  23. //出队
  24. QueueErase(&que);
  25. }
  26. //全部出队
  27. printf("\n全部出队后队列的元素个数为:%d\n", QueueSize(&que));
  28. //销毁
  29. QueueDestroy(&que);
  30. }
  31.  
  32. int main()
  33. {
  34. test01();
  35. return 0;
  36. }

以下是测试的最终效果：

 以上，就是本期的全部内容啦🌸

制作不易，能否点个赞再走呢🙏

文章知识点与官方知识档案匹配，可进一步学习相关知识
算法技能树首页概览43883 人正在系统学习中
【算法系列篇】滑动窗口
走进人工智能|深度学习 算法的创世纪