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

【数据结构】数组实现队列（详细版）

作者：你好赵伟 | 2024-05-17 08:08:05

赞

踩

数组实现队列

目录

队列的定义

普通顺序队列的劣势——与链队列相比 

顺序队列实现方法：

一、动态增长队列

 1、初始化队列

 2、元素入队

 3、判断队列是否为空

 4、元素出队

 5、获取队首元素

6、获取队尾元素

 7、获取队列元素个数

8、销毁队列

 总结：

动态增长队列完整测试代码：

二、固定长度队列 

1、与动态增长队列的差异

2、判断是否队满 

固定长度队列完整测试代码：

本节我们采用数组（顺序表）形式实现队列，学习单链表实现请点击下方链接：

队列—单链表实现（C语言版）-CSDN博客

为了减少数组初始长度过大对内存空间的浪费，本节我们采用动态内存管理，相关函数请的介绍点击下方链接：

动态内存函数（malloc，free，calloc，realloc）-CSDN博客

循环队列的实现：

循环队列（数组实现）-CSDN博客


 

队列的定义

队列是一种基本的数据结构，它是一种先进先出（First In First Out，FIFO）的线性结构。队列只允许在表的一端进行插入，而在另一端进行删除操作。这就相当于把数据排成一排，先插入的排在前面，后插入的排在后面，之后进行删除操作时也只能从前面依次删除。这种数据结构一般用于需要按照先后顺序进行处理的问题，如模拟系统、计算机网络中的缓存、操作系统中的进程调度等。队列的基本操作包括入队（插入元素到队尾）和出队（从队头删除元素），队列还有一个重要的特性就是队列的长度是动态变化的，随着入队和出队的操作进行不断变化。

 ​​

普通顺序队列的劣势——与链队列相比 

  1. 长度固定：普通数组队列的长度是固定的，一旦数组被分配，其长度无法改变。当队列元素数量超过数组长度时，需要进行数组的扩容操作，这会导致性能上的开销。

  2. 内存的浪费：因为普通数组队列的长度固定，可能会出现队列中存在空闲的位置，导致内存的浪费。

为了解决上述 问题1，我们在本节中对顺序表采取动态内存管理，在必要时更新数组的长度，以保证顺序队列的长度足够使用。

 （补充：问题2 的解决需要使用循环队列，本节内容先为大家介绍一般队列的实现，等同学们对队列有了充分的理解之后，我们下节再进行循环队列的学习。）

顺序队列实现方法：

一、我们首先定义一个数组，数组的头部为队首，尾部为队尾。每当插入一个元素时，就将元素放在队尾，当删除一个元素时，将队首的元素删除。当队列为空时，不能再删除元素。

二、我们采用双指针法时刻记录队列的队首和队尾：

  1. 定义一个固定大小的数组作为队列的存储空间，并定义两个指针front和rear分别指向队列的队首和队尾。

  2. 初始化队列时，将front和rear都设置为0，表示队列为空。

  3. 插入元素时，将元素放入rear指针指向的位置，并将rear指针后移一位。

  4. 删除元素时，将front指针后移一位。

  5. 判断队列是否为空，只需要判断front和rear是否相等即可。

一、动态增长队列

 1、初始化队列

初始化队列时，将front和rear都设置为0，表示队列为空。

  1. typedef int DataType;
  2.  
  3. typedef struct Queue
  4. {
  5.     DataType* a; // 队列的数组
  6.     int front, rear; // 队列的头部和尾部位置索引
  7.     int size; // 队列中元素的数量
  8.     int capacity; // 队列的容量
  9. } Queue;
  10.  
  11. // 初始化队列
  12. void InitQueue(Queue* q)
  13. {
  14.     q->a = NULL; // 数组指针初始化为NULL
  15.     q->front = q->rear = 0; // 头部和尾部位置索引初始化为0
  16.     q->size = q->capacity = 0; // 元素数量和容量都初始化为0
  17. }

 2、元素入队

  1. // 入队
  2. void QueuePush(Queue* q, DataType x)
  3. {
  4.     assert(q); // 断言q不为NULL
  5.     if (q->capacity == q->rear)
  6.     {
  7.         // 如果队列已满，进行扩容操作
  8.         int new_capacity = q->capacity == 0 ? 10 : q->capacity * 2; // 扩容的大小为原容量的2倍
  9.         DataType* temp = (DataType*)realloc(q->a, new_capacity * sizeof(DataType)); // 重新分配内存空间
  10.         if (temp == NULL)
  11.         {
  12.             perror("realloc fail"); // 扩容失败，则输出错误信息
  13.             exit(-1); // 退出程序
  14.         }
  15.         q->capacity = new_capacity; // 更新队列的容量
  16.         q->a = temp; // 更新数组指针
  17.     }
  18.     q->a[q->rear++] = x; // 在尾部插入新元素，并更新尾部位置索引
  19.     q->size++; // 元素数量加1
  20. }

 3、判断队列是否为空

判断队列是否为空，只需要判断front和rear是否相等即可。

  1. // 判断队列是否为空
  2. bool QueueEmpty(Queue* q)
  3. {
  4.     assert(q); // 断言q不为NULL
  5.     if (q->front == q->rear)
  6.     {
  7.         return true; // 头部和尾部位置索引相等，队列为空
  8.     }
  9.     return false; // 队列不为空
  10. }

 4、元素出队

 删除元素时，将front指针后移一位。

  1. void QueuePop(Queue* q)
  2. {
  3.     assert(q); // 断言q不为NULL
  4.     if (!QueueEmpty(q))
  5.     {
  6.         q->front++; // 更新头部位置索引
  7.         q->size--; // 元素数量减1
  8.     }
  9.     else
  10.     {
  11.         printf("队列已空，删除失败！\n"); // 队列为空，无法出队
  12.     }
  13. }

5、获取队首元素

  1. // 获取队首元素
  2. DataType QueueTop(Queue* q)
  3. {
  4.     assert(q); // 断言q不为NULL
  5.     if (!QueueEmpty(q))
  6.     {
  7.         return q->a[q->front]; // 返回队首元素的值
  8.     }
  9.     else
  10.     {
  11.         printf("队列已空，获取队头元素失败！\n"); // 队列为空，无法获取队首元素
  12.         exit(-1); // 退出程序
  13.     }
  14. }

6、获取队尾元素

队尾指针q->rear在最后一个元素的下一位，所以我们返回队尾元素时需要返回队尾坐标的前一个坐标所指向的元素。

  1. // 获取队尾元素
  2. DataType QueueTail(Queue* q)
  3. {
  4.     assert(q); // 断言q不为NULL
  5.     if (!QueueEmpty(q))
  6.     {
  7.         return q->a[q->rear - 1]; // 返回队尾元素的值
  8.     }
  9.     else
  10.     {
  11.         printf("队列已空，获取队尾元素失败！\n"); // 队列为空，无法获取队尾元素
  12.         exit(-1); // 退出程序
  13.     }
  14. }

7、获取队列元素个数

  1. // 获取队列中元素的数量
  2. int QueueSize(Queue* q)
  3. {
  4.     assert(q); // 断言q不为NULL
  5.     return q->size; // 返回元素数量
  6. }

8、销毁队列

  1. // 销毁队列
  2. void QueueDestory(Queue* q)
  3. {
  4.     assert(q); // 断言q不为NULL
  5.     free(q->a); // 释放队列的数组空间
  6.     q->a = NULL; // 数组指针置为NULL
  7. }

总结：

 通过对顺序队列的学习我们可以明显看到顺序队列的缺点。当我们删除队首元素后，由于队列只能从队尾进行增加元素的操作，所以front指针之前的空间不能再进行使用。

如果是在队列长度是固定长度的情况下，当队尾指针rear到达最大时，队列已满，数组内已经没有空间进行插入操作，但由于此时front指针前可能还有空余空间，这时我们就造成了空间的浪费。

我们把这种现象称为“假溢出”现象。那么通过数组的循环队列或者链队列我们可以很好的解决此类现象。

下节我们将对如何用数组实现循环队列进行介绍：循环队列（数组实现）-CSDN博客

动态增长队列完整测试代码：

  1. #define _CRT_SECURE_NO_WARNINGS 1
  2. #include<stdio.h>
  3. #include<stdlib.h>
  4. #include<assert.h>
  5. #include<stdbool.h>
  6.  
  7. typedef int DataType;
  8.  
  9. typedef struct Queue
  10. {
  11.     DataType* a; // 队列的数组
  12.     int front, rear; // 队列的头部和尾部位置索引
  13.     int size; // 队列中元素的数量
  14.     int capacity; // 队列的容量
  15. } Queue;
  16.  
  17. // 初始化队列
  18. void InitQueue(Queue* q)
  19. {
  20.     q->a = NULL; // 数组指针初始化为NULL
  21.     q->front = q->rear = 0; // 头部和尾部位置索引初始化为0
  22.     q->size = q->capacity = 0; // 元素数量和容量都初始化为0
  23. }
  24.  
  25. // 判断队列是否为空
  26. bool QueueEmpty(Queue* q)
  27. {
  28.     assert(q); // 断言q不为NULL
  29.     if (q->front == q->rear)
  30.     {
  31.         return true; // 头部和尾部位置索引相等，队列为空
  32.     }
  33.     return false; // 队列不为空
  34. }
  35.  
  36. // 入队
  37. void QueuePush(Queue* q, DataType x)
  38. {
  39.     assert(q); // 断言q不为NULL
  40.     if (q->capacity == q->rear)
  41.     {
  42.         // 如果队列已满，进行扩容操作
  43.         int new_capacity = q->capacity == 0 ? 10 : q->capacity * 2; // 扩容的大小为原容量的2倍
  44.         DataType* temp = (DataType*)realloc(q->a, new_capacity * sizeof(DataType)); // 重新分配内存空间
  45.         if (temp == NULL)
  46.         {
  47.             perror("realloc fail"); // 扩容失败，则输出错误信息
  48.             exit(-1); // 退出程序
  49.         }
  50.         q->capacity = new_capacity; // 更新队列的容量
  51.         q->a = temp; // 更新数组指针
  52.     }
  53.     q->a[q->rear++] = x; // 在尾部插入新元素，并更新尾部位置索引
  54.     q->size++; // 元素数量加1
  55. }
  56.  
  57. // 出队
  58. void QueuePop(Queue* q)
  59. {
  60.     assert(q); // 断言q不为NULL
  61.     if (!QueueEmpty(q))
  62.     {
  63.         q->front++; // 更新头部位置索引
  64.         q->size--; // 元素数量减1
  65.     }
  66.     else
  67.     {
  68.         printf("队列已空，删除失败！\n"); // 队列为空，无法出队
  69.     }
  70. }
  71.  
  72. // 获取队首元素
  73. DataType QueueTop(Queue* q)
  74. {
  75.     assert(q); // 断言q不为NULL
  76.     if (!QueueEmpty(q))
  77.     {
  78.         return q->a[q->front]; // 返回队首元素的值
  79.     }
  80.     else
  81.     {
  82.         printf("队列已空，获取队头元素失败！\n"); // 队列为空，无法获取队首元素
  83.         exit(-1); // 退出程序
  84.     }
  85. }
  86.  
  87. // 获取队尾元素
  88. DataType QueueTail(Queue* q)
  89. {
  90.     assert(q); // 断言q不为NULL
  91.     if (!QueueEmpty(q))
  92.     {
  93.         return q->a[q->rear - 1]; // 返回队尾元素的值
  94.     }
  95.     else
  96.     {
  97.         printf("队列已空，获取队尾元素失败！\n"); // 队列为空，无法获取队尾元素
  98.         exit(-1); // 退出程序
  99.     }
  100. }
  101.  
  102. // 获取队列中元素的数量
  103. int QueueSize(Queue* q)
  104. {
  105.     assert(q); // 断言q不为NULL
  106.     return q->size; // 返回元素数量
  107. }
  108.  
  109. // 销毁队列
  110. void QueueDestory(Queue* q)
  111. {
  112.     assert(q); // 断言q不为NULL
  113.     free(q->a); // 释放队列的数组空间
  114.     q->a = NULL; // 数组指针置为NULL
  115. }
  116.  
  117. int main()
  118. {
  119. 	Queue q;
  120. 	InitQueue(&q);
  121. 	QueuePush(&q, 5);
  122. 	QueuePush(&q, 6);
  123. 	QueuePush(&q, 7);
  124. 	QueuePush(&q, 8);
  125. 	QueuePush(&q, 9);
  126. 	QueuePush(&q, 10);
  127. 	DataType x;
  128. 	x = QueueTop(&q);
  129. 	printf("%d\n", x);
  130. 	x = QueueTail(&q);
  131. 	printf("%d\n", x);
  132. 	QueuePop(&q);
  133. 	QueuePop(&q);
  134. 	QueuePop(&q);
  135. 	QueuePop(&q);
  136. 	QueuePop(&q);
  137. 	x = QueueTop(&q);
  138. 	printf("%d\n", x);
  139.     x = QueueSize(&q);
  140.     printf("%d\n", x);
  141.     QueueDestory(&q);
  142.     return 0;
  143. }

二、固定长度队列 

1、与动态增长队列的差异

由于固定长度队列无需扩容，所以不需要进行动态内存的分配，也不需要进行销毁队列的操作。

同时相对于动态增长的队列，固定长度的队列需要判断队内元素数量是否达到了队列的最大容量。由于我们在代码中是先对队尾指针rear指向的位置添加元素，再对rear进行自增，更新队尾索引，所以在本代码中队满的判断条件是rear==MAXLEN。

2、判断是否队满 

当对固定长度队列添加元素时，如果当前队列队尾指针已达到数组长度，由于队列只能从队尾添加元素，此时我们不能再为队列添加新的元素。所以在我们为队尾添加元素时，我们首先要判断队列是否已满——即队尾指针是否达到数组容量的最大值。

  1. //判断队列是否为满
  2. bool QueueFull(Queue* q)
  3. {
  4.     assert(q); // 断言q不为NULL
  5.     if (q->rear == MAXLEN)
  6.     {
  7.         return true; // 尾部位置达到数组长度最大值，队列为满
  8.     }
  9.     return false; // 队列不为满
  10. }

明白了以上几点，我们对动态增长队列的代码稍作修改，添加判断队列是否已满的函数并对增加队列元素作出限制，就可得到固定长度队列的代码。

固定长度队列完整测试代码：

  1. #define _CRT_SECURE_NO_WARNINGS 1
  2. #include<stdio.h>
  3. #include<stdlib.h>
  4. #include<assert.h>
  5. #include<stdbool.h>
  6.  
  7. #define MAXLEN 10
  8. typedef int DataType;
  9.  
  10. typedef struct Queue
  11. {
  12.     DataType a[MAXLEN]; // 队列的数组
  13.     int front, rear; // 队列的头部和尾部位置索引
  14.     int size; // 队列中元素的数量
  15. } Queue;
  16.  
  17. // 初始化队列
  18. void InitQueue(Queue* q)
  19. {
  20.     assert(q);
  21.     q->front = q->rear = 0; // 头部和尾部位置索引初始化为0
  22.     q->size = 0; // 元素数量初始化为0
  23. }
  24.  
  25. // 判断队列是否为空
  26. bool QueueEmpty(Queue* q)
  27. {
  28.     assert(q); // 断言q不为NULL
  29.     if (q->front == q->rear)
  30.     {
  31.         return true; // 头部和尾部位置索引相等，队列为空
  32.     }
  33.     return false; // 队列不为空
  34. }
  35.  
  36. //判断队列是否为满
  37. bool QueueFull(Queue* q)
  38. {
  39.     assert(q); // 断言q不为NULL
  40.     if (q->rear == MAXLEN)
  41.     {
  42.         return true; // 尾部位置达到数组长度最大值，队列为满
  43.     }
  44.     return false; // 队列不为满
  45. }
  46.  
  47. // 入队
  48. void QueuePush(Queue* q, DataType x)
  49. {
  50.     assert(q); // 断言q不为NULL
  51.     if (!QueueFull(q))//判断队列是否为满
  52.     {
  53.         q->a[q->rear++] = x; // 在尾部插入新元素，并更新尾部位置索引
  54.         q->size++; // 元素数量加1
  55.     }
  56.     else
  57.     {
  58.         printf("队列已满\n");
  59.         exit(-1);
  60.     }
  61. }
  62.  
  63. // 出队
  64. void QueuePop(Queue* q)
  65. {
  66.     assert(q); // 断言q不为NULL
  67.     if (!QueueEmpty(q))
  68.     {
  69.         q->front++; // 更新头部位置索引
  70.         q->size--; // 元素数量减1
  71.     }
  72.     else
  73.     {
  74.         printf("队列已空，删除失败！\n"); // 队列为空，无法出队
  75.     }
  76. }
  77.  
  78. // 获取队首元素
  79. DataType QueueTop(Queue* q)
  80. {
  81.     assert(q); // 断言q不为NULL
  82.     if (!QueueEmpty(q))
  83.     {
  84.         return q->a[q->front]; // 返回队首元素的值
  85.     }
  86.     else
  87.     {
  88.         printf("队列已空，获取队头元素失败！\n"); // 队列为空，无法获取队首元素
  89.         exit(-1); // 退出程序
  90.     }
  91. }
  92.  
  93. // 获取队尾元素
  94. DataType QueueTail(Queue* q)
  95. {
  96.     assert(q); // 断言q不为NULL
  97.     if (!QueueEmpty(q))
  98.     {
  99.         return q->a[q->rear - 1]; // 返回队尾元素的值
  100.     }
  101.     else
  102.     {
  103.         printf("队列已空，获取队尾元素失败！\n"); // 队列为空，无法获取队尾元素
  104.         exit(-1); // 退出程序
  105.     }
  106. }
  107.  
  108. // 获取队列中元素的数量
  109. int QueueSize(Queue* q)
  110. {
  111.     assert(q); // 断言q不为NULL
  112.     return q->size; // 返回元素数量
  113. }
  114.  
  115.  
  116. int main()
  117. {
  118.     Queue q;
  119.     InitQueue(&q);
  120.     QueuePush(&q, 5);
  121.     QueuePush(&q, 6);
  122.     QueuePush(&q, 7);
  123.     QueuePush(&q, 8);
  124.     QueuePush(&q, 9);
  125.     QueuePush(&q, 10);
  126.     QueuePush(&q, 5);
  127.     QueuePush(&q, 6);
  128.     QueuePush(&q, 7);
  129.     QueuePush(&q, 8);
  130.     //QueuePush(&q, 9);
  131.     //QueuePush(&q, 10);
  132.     DataType x;
  133.     x = QueueTop(&q);
  134.     printf("%d\n", x);
  135.     x = QueueTail(&q);
  136.     printf("%d\n", x);
  137.     QueuePop(&q);
  138.     QueuePop(&q);
  139.     QueuePop(&q);
  140.     QueuePop(&q);
  141.     QueuePop(&q);
  142.     x = QueueTop(&q);
  143.     printf("%d\n", x);
  144.     x = QueueSize(&q);
  145.     printf("%d\n", x);
  146.     return 0;
  147. }

如果有同学在部分地方有疑惑，欢迎评论区讨论。

本节内容告一段落，我们下节博客见。

循环队列（数组实现）-CSDN博客

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/你好赵伟/article/detail/582676
推荐阅读
相关标签

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

  

闽ICP备14008679号