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

队列的基本操作——常见队列的对比分析（c语言完整代码包含注释）_c语言获取队列长度

作者：小惠珠哦 | 2024-07-26 10:46:33

赞

踩

c语言获取队列长度

目录

一、队列

1.1基本概念

1.2基本操作

1.3 队列分类

1.3.1带头队列

1.3.2不带头队列

1.3.3 循环带头队列

1.3.4 循环不带头队列

1.3.5 总结

二、代码实现

2.1带头队列

2.2不带头队列

2.3循环带头队列

2.4循环不带头队列

一、队列

1.1基本概念

        队列（Queue）是一种常见的数据结构，它遵循先进先出（First In First Out, FIFO）的原则，类似于现实生活中排队等待的概念。在队列中，元素按照其插入的顺序排列，最先插入的元素将最先被移除。

  • 队列元素：队列中的每个元素称为一个队列元素，可以是任意类型的数据。
  • 队列头（front）：队列的头部，即第一个元素所在的位置，通常用于删除元素操作。
  • 队列尾（rear）：队列的尾部，即最后一个元素所在的位置，通常用于插入元素操作。

1.2基本操作

        队列的基本操作主要包括入队和出队两种操作，通过这两种操作可以实现对队列中元素的添加和移除。在使用队列时，需要注意保持操作的顺序，遵循 FIFO 的规则，以确保队列的正确性和有效性。

  • 入队（enqueue）：将元素插入到队列的末尾，即在队尾添加一个新元素。

  • 出队（dequeue）：从队列的头部移除一个元素，并返回该元素的值。

  • 判空（isEmpty）：判断队列是否为空，即队列中是否有元素。

  • 判满（isFull）：判断队列是否已满，即队列中的元素数量是否达到上限。

  • 获取队头元素（peek）：查看队列头部的元素值，但不移除该元素。

  • 清空队列（clear）：移除队列中的所有元素，使队列变为空队列。

  • 获取队列长度（size）：返回队列中元素的数量。

1.3 队列分类

1.3.1带头队列

  • front 和 rear 的初始值：在带头的队列中，front 和 rear 的初始值通常都设置为 0，表示头结点的位置。
  • 插入元素：在带头的队列中，插入元素时，先将 rear 加一，再将元素插入到 rear 所指向的位置。
  • 删除元素：在带头的队列中，删除元素时，先将 front 加一，返回 front 指向的位置的元素。

1.3.2不带头队列

  • front 和 rear 的初始值：通常情况下，不带头的队列中，front 和 rear 的初始值都为 -1，表示队列为空。
  • 插入元素：在不带头的队列中，插入元素时，先将 rear 加一，再将元素插入到 rear 所指向的位置。
  • 删除元素：在不带头的队列中，删除元素时，先将 front 加一，返回 front 指向的位置的元素。

1.3.3 循环带头队列

  • front 和 rear 的初始值：通常情况下，front 和 rear 的初始值都为 0，表示队列为空。
  • 插入元素：先将 rear 加一，再将元素插入到 rear 所指向的位置。如果 rear 达到数组末尾，可以通过取余运算将 rear 置为 0，实现循环利用数组空间。
  • 删除元素：先将 front 加一，返回 front 指向的位置的元素。同样地，如果 front 达到数组末尾，可通过取余运算将 front 置为 0。
  • 判空条件：当 front 和 rear 的值相等时，表示队列为空。
  • 判满条件：当 (rear + 1) % 数组长度 等于 front 的值时，表示队列满。

1.3.4 循环不带头队列

  • front 和 rear 的初始值：通常情况下，front 和 rear 的初始值都为 -1，表示队列为空。
  • 插入元素：先将 rear 加一，再将元素插入到 rear 所指向的位置。如果 rear 达到数组末尾，可以通过取余运算将 rear 置为 0，实现循环利用数组空间。
  • 删除元素：在不带头的队列中，删除元素时，先将 front 加一，返回 front 指向的位置的元素。
  • 判空条件：当 front 和 rear 的值相等且等于 -1 时，表示队列为空。
  • 判满条件：当 (rear + 1) % 数组长度 等于 front 的值时，表示队列满。

1.3.5 总结

        总的来说，循环队列带头和不带头在判满和判空上的逻辑是相同的，都是根据指针的位置关系来判断队列状态；而引入头结点的主要作用是简化队列为空和队列满的判断逻辑，使队列操作更加灵活高效。

二、代码实现

2.1带头队列

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. #define SIZE 5
  5.  
  6.  
  7. // 定义一个Queue结构体表示队列
  8. typedef struct {
  9.     int items[SIZE];
  10.     int front;   // 队列头指针，指向头结点
  11.     int rear;    // 队列尾指针，指向最后一个元素
  12. } Queue;
  13.  
  14. // 创建一个空队列并返回其指针
  15. Queue* createQueue() {
  16.     Queue *queue = (Queue*)malloc(sizeof(Queue)); // 为队列分配内存
  17.     queue->front = 0; // 初始化队列头指针
  18.     queue->rear = 0; // 初始化队列尾指针
  19.     return queue;
  20. }
  21.  
  22. // 判断队列是否满了
  23. int isFull(Queue *queue) {
  24.     return (queue->rear == SIZE); // 如果队列尾指针指向最后一个元素的下一个位置，则队列已满
  25. }
  26.  
  27. // 判断队列是否为空
  28. int isEmpty(Queue *queue) {
  29.     return (queue->front == queue->rear); // 如果队列头指针和尾指针相等，说明队列为空
  30. }
  31.  
  32. // 将元素添加到队列尾部
  33. void enqueue(Queue *queue, int item) {
  34.     if (isFull(queue)) { // 如果队列已满，打印提示信息
  35.         printf("队列已满，无法入队。\n");
  36.     } else {
  37.         queue->rear++; // 队列尾指针加1
  38.         queue->items[queue->rear - 1] = item; // 将元素存储到队列尾部
  39.         printf("%d 入队成功。\n", item); // 打印添加成功信息
  40.     }
  41. }
  42.  
  43. // 从队列头部移除一个元素并返回其值
  44. int dequeue(Queue *queue) {
  45.     int item;
  46.     if (isEmpty(queue)) { // 如果队列为空，打印提示信息并返回-1表示操作失败
  47.         printf("队列为空，无法出队。\n");
  48.         return -1;
  49.     } else {
  50.         item = queue->items[queue->front]; // 获取队列头部元素的值
  51.         queue->front++; // 队列头指针加1
  52.         printf("%d 出队成功。\n", item); // 打印移除成功信息
  53.         return item; // 返回移除的元素值
  54.     }
  55. }
  56.  
  57. int main() {
  58.     Queue *queue = createQueue(); // 创建一个新的队列并获取其指针
  59.  
  60.     // 进行入队列和出队列操作
  61.     enqueue(queue, 10);
  62.     enqueue(queue, 20);
  63.     enqueue(queue, 30);
  64.  
  65.     dequeue(queue);
  66.     dequeue(queue);
  67.     dequeue(queue);
  68.     dequeue(queue); // 尝试从空队列中出队列
  69.  
  70.     free(queue); // 释放队列内存空间
  71.  
  72.     return 0;
  73. }

2.2不带头队列

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. #define SIZE 5
  5.  
  6.  
  7. // 定义一个Queue结构体表示队列
  8. typedef struct {
  9.     int items[SIZE]; // 存储队列元素的数组
  10.     int front; // 队列头指针
  11.     int rear; // 队列尾指针
  12. } Queue;
  13.  
  14.  
  15. // 创建一个空队列并返回其指针
  16. Queue* createQueue() {
  17.     Queue *queue = (Queue*)malloc(sizeof(Queue)); // 为队列分配内存
  18.     queue->front = -1; // 初始化队列头指针
  19.     queue->rear = -1; // 初始化队列尾指针
  20.     return queue;
  21. }
  22.  
  23. // 判断队列是否满了
  24. int isFull(Queue *queue) {
  25.     return (queue->rear == SIZE - 1); // 如果队列尾指针指向最后一个元素，则队列已满
  26. }
  27.  
  28.  
  29. // 判断队列是否为空
  30. int isEmpty(Queue *queue) {
  31.     return (queue->front == -1 || queue->front > queue->rear); // 如果队列头指针指向了最后一个元素（队列为空），或指向的元素已经被出队列了，说明队列为空
  32. }
  33.  
  34.  
  35. // 将元素添加到队列尾部
  36. void enqueue(Queue *queue, int item) {
  37.     if (isFull(queue)) { // 如果队列已满，打印提示信息
  38.         printf("队列已满，无法入队。\n");
  39.     } else {
  40.         if (queue->front == -1) { // 如果队列为空，将队列头指针设置为0
  41.             queue->front = 0;
  42.         }
  43.         queue->rear++; // 队列尾指针加1
  44.         queue->items[queue->rear] = item; // 将元素存储到队列尾部
  45.         printf("%d 入队成功。\n", item); // 打印添加成功信息
  46.     }
  47. }
  48.  
  49.  
  50. // 从队列头部移除一个元素并返回其值
  51. int dequeue(Queue *queue) {
  52.     int item;
  53.     if (isEmpty(queue)) { // 如果队列为空，打印提示信息并返回-1表示操作失败
  54.         printf("队列为空，无法出队。\n");
  55.         return -1;
  56.     } else {
  57.         item = queue->items[queue->front]; // 获取队列头部元素的值
  58.         queue->front++; // 队列头指针加1
  59.         printf("%d 出队成功。\n", item); // 打印移除成功信息
  60.         return item; // 返回移除的元素值
  61.     }
  62. }
  63.  
  64.  
  65. int main() {
  66.     Queue *queue = createQueue(); // 创建一个新的队列并获取其指针
  67.  
  68.     // 进行入队列和出队列操作
  69.     enqueue(queue, 10);
  70.     enqueue(queue, 20);
  71.     enqueue(queue, 30);
  72.  
  73.     dequeue(queue);
  74.     dequeue(queue);
  75.     dequeue(queue);
  76.     dequeue(queue); // 尝试从空队列中出队列
  77.  
  78.     free(queue); // 释放队列内存空间
  79.  
  80.     return 0;
  81. }

2.3循环带头队列

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. #define MAX_SIZE 4     // 队列的最大容量，带头
  5.  
  6. // 循环队列结构体
  7. typedef struct {
  8.     int data[MAX_SIZE];  // 用数组存储队列元素
  9.     int front;           // 队头指针
  10.     int rear;            // 队尾指针
  11. } CircularQueue;
  12.  
  13. // 初始化循环队列
  14. void initQueue(CircularQueue *queue) {
  15.     queue->front = 0;    // 初始时队头指针指向第一个元素
  16.     queue->rear = 0;     // 初始时队尾指针指向第一个元素
  17. }
  18.  
  19. // 判断队列是否为空
  20. int isEmpty(CircularQueue *queue) {
  21.     return queue->front == queue->rear;  // 队列为空时，队头指针与队尾指针相等
  22. }
  23.  
  24. // 判断队列是否已满
  25. int isFull(CircularQueue *queue) {
  26.     return (queue->rear + 1) % MAX_SIZE == queue->front;  // 队列已满时，队尾指针的下一个位置为队头指针
  27. }
  28.  
  29. // 入队操作
  30. void enqueue(CircularQueue *queue, int item) {
  31.     if (isFull(queue)) {  // 判断队列是否已满
  32.         printf("队列已满，无法插入新元素\n");
  33.     } else {
  34.         queue->data[queue->rear] = item;  // 将新元素插入队尾
  35.         queue->rear = (queue->rear + 1) % MAX_SIZE;  // 移动队尾指针的位置
  36.         printf("入队成功: %d\n", item);
  37.     }
  38. }
  39.  
  40. // 出队操作
  41. int dequeue(CircularQueue *queue) {
  42.     int item;
  43.     if (isEmpty(queue)) {  // 判断队列是否为空
  44.         printf("队列为空，无法出队\n");
  45.         return -1;
  46.     } else {
  47.         item = queue->data[queue->front];  // 取出队头元素
  48.         queue->front = (queue->front + 1) % MAX_SIZE;  // 移动队头指针的位置
  49.         printf("出队元素: %d\n", item);
  50.         return item;
  51.     }
  52. }
  53.  
  54. // 主函数
  55. int main() {
  56.     CircularQueue queue;
  57.     initQueue(&queue);  // 初始化循环队列
  58.  
  59.     enqueue(&queue, 1);  // 入队操作
  60.     enqueue(&queue, 2);
  61.     enqueue(&queue, 3);
  62.     enqueue(&queue, 3);
  63.  
  64.     dequeue(&queue);  // 出队操作
  65.     dequeue(&queue);
  66.     dequeue(&queue);
  67.     dequeue(&queue);
  68.  
  69.     return 0;
  70. }

2.4循环不带头队列

  1. #include <stdio.h>
  2.  
  3. #define MAX_SIZE 5
  4.  
  5. // 定义循环队列结构体，不带头
  6. typedef struct {
  7.     int data[MAX_SIZE];  // 用数组存储队列元素
  8.     int front;           // 队头指针
  9.     int rear;            // 队尾指针
  10. } CircularQueue;
  11.  
  12. // 初始化循环队列
  13. void initQueue(CircularQueue *queue) {
  14.     queue->front = -1;
  15.     queue->rear = -1;
  16. }
  17.  
  18. // 判断队列是否为空
  19. int isEmpty(CircularQueue *queue) {
  20.     return (queue->front == -1 && queue->rear == -1);
  21. }
  22.  
  23. // 判断队列是否已满
  24. int isFull(CircularQueue *queue) {
  25.     return ((queue->rear + 1) % MAX_SIZE == queue->front);
  26. }
  27.  
  28. // 入队操作
  29. void enqueue(CircularQueue *queue, int value) {
  30.     if (isFull(queue)) {
  31.         printf("队列已满，无法入队。\n");
  32.     } else if (isEmpty(queue)) {
  33.         queue->front = 0;
  34.         queue->rear = 0;
  35.         queue->data[queue->rear] = value;
  36.         printf("%d 入队成功。\n", value);
  37.     } else {
  38.         queue->rear = (queue->rear + 1) % MAX_SIZE;
  39.         queue->data[queue->rear] = value;
  40.         printf("%d 入队成功。\n", value);
  41.     }
  42. }
  43.  
  44. // 出队操作
  45. int dequeue(CircularQueue *queue) {
  46.     if (isEmpty(queue)) {
  47.         printf("队列为空，无法出队。\n");
  48.         return -1;
  49.     } else {
  50.         int value = queue->data[queue->front];
  51.         if (queue->front == queue->rear) {
  52.             queue->front = -1;
  53.             queue->rear = -1;
  54.         } else {
  55.             queue->front = (queue->front + 1) % MAX_SIZE;
  56.         }
  57.         printf("%d 出队成功。\n", value);
  58.         return value;
  59.     }
  60. }
  61.  
  62. int main() {
  63.     CircularQueue queue;
  64.     initQueue(&queue);
  65.  
  66.     // 入队操作
  67.     enqueue(&queue, 10);
  68.     enqueue(&queue, 20);
  69.     enqueue(&queue, 30);
  70.     enqueue(&queue, 40);
  71.     enqueue(&queue, 50);
  72.     enqueue(&queue, 60);  // 队列已满，无法入队
  73.  
  74.     // 出队操作
  75.     dequeue(&queue);
  76.     dequeue(&queue);
  77.     dequeue(&queue);
  78.     dequeue(&queue);
  79.     dequeue(&queue);
  80.     dequeue(&queue);  // 队列已空，无法出队
  81.  
  82.     return 0;
  83. }

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

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

  

闽ICP备14008679号