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

数据结构：队列的详解_数据结构队列详细讲解

作者：木道寻08 | 2024-08-01 19:17:14

赞

踩

数据结构队列详细讲解

1.概念：

队列是一种先进先出的数据结构，FIFO（first in first out）

逻辑结构：线性结构

2.队列的存储

2.1顺序队列

顺序队列是基于顺序表和两个下标来实现的，一个是队列头front，一个是队列尾rear

入队时，在队列尾入，出队列时，在队列头出。

顺序队列本质就是对顺序表操作的一个约束：只能在一端插入，另一端删除。

一般这种队列我们不直接使用，因为入队时 rear++ 出队列时 front++

每块内存空间只使用了一次，相当于一个一次性的队列了。

2.2循环队列

循环队列只是对顺序队列的一个小优化，目的是让空间能复用起来。

这种结构就可以让空间复用起来了。

入队列时，不要直接执行rear++，而是改成 rear = (rear+1)%N

出队列时，不要直接执行front++，而是改成 front = (front+1)%N

判断队列空 rear == front

判断队列满 (rear+1)%N == front （浪费了一个存储空间用来区分队列满和队列空 方便写代码）

循环队列的操作：

创建队列

清空队列

销毁队列

入队列 push

判断队列满

出队列 pop

判断队列空

打印队列中所有元素----实际不需要

循环队列代码实现：

loop_queue.h

  1. #ifndef __LOOP_QUEUE_H__
  2. #define __LOOP_QUEUE_H__
  3.  
  4. #include <stdio.h>
  5. #include <stdlib.h>
  6. #include <string.h>
  7.  
  8. #define N 5
  9.  
  10. //循环队列的结构体
  11. typedef struct _Queue{
  12.     int s[N];
  13.     int front;
  14.     int rear;
  15. }queue_t;
  16.  
  17. int create_queue(queue_t **my_queue);
  18. int is_full(queue_t *my_queue);
  19. int push_queue(queue_t *my_queue, int data);
  20. int print_queue(queue_t *my_queue);
  21. int is_empty(queue_t *my_queue);
  22. int pop_queue(queue_t *my_queue, int *num);
  23. int clean_queue(queue_t *my_queue);
  24. int destroy_queue(queue_t **my_queue);
  25.  
  26. #endif

loop_queue.c

  1. #include "loop_queue.h"
  2.  
  3. //创建队列
  4. int create_queue(queue_t **my_queue){
  5.     if(NULL == my_queue){
  6.         printf("入参为NULL\n");
  7.         return -1;
  8.     }
  9.     *my_queue = (queue_t *)malloc(sizeof(queue_t));
  10.     if(NULL == *my_queue){
  11.         printf("内存分配失败\n");
  12.         return -1;
  13.     }
  14.     memset(*my_queue, 0, sizeof(queue_t));
  15.     return 0;
  16. }
  17.  
  18. //判断队列满
  19. int is_full(queue_t *my_queue){
  20.     if(NULL == my_queue){
  21.         printf("入参为NULL\n");
  22.         return -1;
  23.     }
  24.     return (my_queue->rear+1) % N == my_queue->front ? 1 : 0;
  25. }
  26.  
  27. //数据入队列
  28. int push_queue(queue_t *my_queue, int data){
  29.     if(NULL == my_queue){
  30.         printf("入参为NULL\n");
  31.         return -1;
  32.     }
  33.     if(is_full(my_queue)){
  34.         printf("队列满 入队列失败\n");
  35.         return -1;
  36.     }
  37.     my_queue->s[my_queue->rear] = data;
  38.     my_queue->rear = (my_queue->rear+1)%N;
  39.     return 0;
  40. }
  41.  
  42. //遍历打印队列中所有元素
  43. int print_queue(queue_t *my_queue){
  44.     if(NULL == my_queue){
  45.         printf("入参为NULL\n");
  46.         return -1;
  47.     }
  48.     int i = 0;
  49. #if 1
  50.     for(i = my_queue->front; i != my_queue->rear; i = (i+1)%N){
  51.         printf("%d  ", my_queue->s[i]);
  52.     }
  53. #else
  54.     for(i = my_queue->front; (i%N) != my_queue->rear; i++){
  55.         printf("%d  ", my_queue->s[i%N]);
  56.     }
  57. #endif
  58.     printf("\n");
  59.     return 0;
  60. }
  61.  
  62. //判断队列空
  63. int is_empty(queue_t *my_queue){
  64.     if(NULL == my_queue){
  65.         printf("入参为NULL\n");
  66.         return -1;
  67.     }
  68.     return my_queue->rear == my_queue->front ? 1 : 0;
  69. }
  70.  
  71. //数据出队列
  72. int pop_queue(queue_t *my_queue, int *num){
  73.     if(NULL == my_queue || NULL == num){
  74.         printf("入参为NULL\n");
  75.         return -1;
  76.     }
  77.     if(is_empty(my_queue)){
  78.         printf("队列空 出队列失败\n");
  79.         return -1;
  80.     }
  81.     *num = my_queue->s[my_queue->front];
  82.     my_queue->front = (my_queue->front+1)%N;
  83.     return 0;
  84. }
  85.  
  86. //清空队列
  87. int clean_queue(queue_t *my_queue){
  88.     if(NULL == my_queue){
  89.         printf("入参为NULL\n");
  90.         return -1;
  91.     }
  92.     //让rear==front即可
  93.     my_queue->rear = my_queue->front = 0;
  94.     return 0;
  95. }
  96.  
  97. //销毁队列
  98. int destroy_queue(queue_t **my_queue){
  99.     if(NULL == my_queue || NULL == *my_queue){
  100.         printf("入参为NULL\n");
  101.         return -1;
  102.     }
  103.     free(*my_queue);
  104.     *my_queue = NULL;
  105.     return 0;
  106. }

main.c

  1. #include "loop_queue.h"
  2.  
  3. int main(int argc, const char *argv[])
  4. {
  5.     queue_t *my_queue = NULL;
  6.     create_queue(&my_queue);
  7.     printf("my_queue = %p\n", my_queue);//非NULL
  8.  
  9.     //测试入队列
  10.     push_queue(my_queue, 10);
  11.     push_queue(my_queue, 20);
  12.     push_queue(my_queue, 30);
  13.     push_queue(my_queue, 40);
  14.     push_queue(my_queue, 50);//满了 失败
  15.     print_queue(my_queue); // 10 20 30 40
  16.  
  17.     //出队列
  18.     int num = 0;
  19.     pop_queue(my_queue, &num);
  20.     printf("num = %d\n", num);//10
  21.     pop_queue(my_queue, &num);
  22.     printf("num = %d\n", num);//20
  23.     print_queue(my_queue); // 30 40
  24.  
  25.     //入队列
  26.     push_queue(my_queue, 50);
  27.     push_queue(my_queue, 60);
  28.     push_queue(my_queue, 70);//满了 失败
  29.     print_queue(my_queue); // 30 40 50 60
  30.  
  31.     //清空
  32.     clean_queue(my_queue);
  33.     if(-1 == pop_queue(my_queue, &num)){
  34.         printf("没有出队列成功\n");
  35.     }
  36.     //销毁
  37.     destroy_queue(&my_queue);
  38.     printf("my_queue = %p\n", my_queue);//NULL
  39.  
  40.     return 0;
  41. }

3.链式队列

链式队列是基于链表配合两个指针实现的 一个是队列头 front 一个是队列尾 rear

链式队列的本质就是对链表操作的一个约束：只能在一端插入，另一端删除。

一般采用尾插头删的方式

一般采用尾插头删的方式实现队列 操作的时间复杂度都是 O(1)

链式队列的操作：

创建队列

清空队列

销毁队列

入队列 push

出队列 pop

判断队列空

打印队列中所有元素----实际不需要

链式队列的代码实现：

link_queue.h

  1. #ifndef __LINK_QUEUE_H__
  2. #define __LINK_QUEUE_H__
  3.  
  4. #include <stdio.h>
  5. #include <stdlib.h>
  6. #include <string.h>
  7.  
  8. //链表节点结构体
  9. typedef struct _Node{
  10.     int data;
  11.     struct _Node *next;
  12. }node_t;
  13.  
  14. //循环队列的结构体
  15. typedef struct _Queue{
  16.     node_t *rear;
  17.     node_t *front;
  18. }queue_t;
  19.  
  20. int create_queue(queue_t **my_queue);
  21. int push_queue(queue_t *my_queue, int data);
  22. int print_queue(queue_t *my_queue);
  23. int is_empty(queue_t *my_queue);
  24. int pop_queue(queue_t *my_queue, int *num);
  25. int clean_queue(queue_t *my_queue);
  26. int destroy_queue(queue_t **my_queue);
  27.  
  28. #endif

link_queue.c

  1. #include "link_queue.h"
  2.  
  3. //创建队列
  4. int create_queue(queue_t **my_queue){
  5.     if(NULL == my_queue){
  6.         printf("入参为NULL\n");
  7.         return -1;
  8.     }
  9.     *my_queue = (queue_t *)malloc(sizeof(queue_t));
  10.     if(NULL == *my_queue){
  11.         printf("内存分配失败\n");
  12.         return -1;
  13.     }
  14.     memset(*my_queue, 0, sizeof(queue_t));
  15.     return 0;
  16. }
  17.  
  18. //数据入队列
  19. int push_queue(queue_t *my_queue, int data){
  20.     if(NULL == my_queue){
  21.         printf("入参为NULL\n");
  22.         return -1;
  23.     }
  24.     //创建新节点
  25.     node_t *pnew = (node_t *)malloc(sizeof(node_t));
  26.     if(NULL == pnew){
  27.         printf("内存分配失败\n");
  28.         return -1;
  29.     }
  30.     pnew->data = data;
  31.     pnew->next = NULL;
  32.     //将新节点插入队列
  33.     if(NULL == my_queue->front && NULL == my_queue->rear){//说明是第一个节点
  34.         my_queue->rear = pnew;
  35.         my_queue->front = pnew;
  36.     }else{
  37.         my_queue->rear->next = pnew;
  38.         my_queue->rear = pnew;
  39.     }
  40.     return 0;
  41. }
  42.  
  43. //遍历所有元素
  44. int print_queue(queue_t *my_queue){
  45.     if(NULL == my_queue){
  46.         printf("入参为NULL\n");
  47.         return -1;
  48.     }
  49.     node_t *ptemp = my_queue->front;
  50.     while(NULL != ptemp){
  51.         printf("%d  ", ptemp->data);
  52.         ptemp = ptemp->next;
  53.     }
  54.     printf("\n");
  55.     return 0;
  56. }
  57.  
  58. //判断队列空
  59. int is_empty(queue_t *my_queue){
  60.     if(NULL == my_queue){
  61.         printf("入参为NULL\n");
  62.         return -1;
  63.     }
  64.     return NULL == my_queue->front && NULL == my_queue->rear ? 1 : 0;
  65. }
  66.  
  67. //数据出队列
  68. int pop_queue(queue_t *my_queue, int *num){
  69.     if(NULL == my_queue || NULL == num){
  70.         printf("入参为NULL\n");
  71.         return -1;
  72.     }
  73.     if(is_empty(my_queue)){
  74.         printf("队列空 出队列失败\n");
  75.         return -1;
  76.     }
  77.     *num = my_queue->front->data;
  78.     node_t *pdel = my_queue->front;
  79.     my_queue->front = pdel->next;
  80.     free(pdel);
  81.     pdel = NULL;
  82.     //如果是最后一个节点 记得把 rear 也置成NULL 
  83.     if(NULL == my_queue->front){
  84.         my_queue->rear = NULL;
  85.     }
  86.     return 0;
  87. }
  88.  
  89. //清空队列
  90. int clean_queue(queue_t *my_queue){
  91.     if(NULL == my_queue ){
  92.         printf("入参为NULL\n");
  93.         return -1;
  94.     }
  95.     node_t *pdel = NULL;
  96.     while(NULL != my_queue->front){
  97.         pdel = my_queue->front;
  98.         my_queue->front = pdel->next;
  99.         free(pdel);
  100.     }
  101.     pdel = NULL;
  102.     my_queue->rear = NULL;
  103.     return 0;
  104. }
  105.  
  106. //销毁队列
  107. int destroy_queue(queue_t **my_queue){
  108.     if(NULL == my_queue || NULL == *my_queue){
  109.         printf("入参为NULL\n");
  110.         return -1;
  111.     }
  112.     //先清空再销毁
  113.     clean_queue(*my_queue);
  114.     free(*my_queue);
  115.     *my_queue = NULL;
  116.     return 0;
  117. }

main.c

  1. #include "link_queue.h"
  2.  
  3. int main(int argc, const char *argv[])
  4. {
  5.     queue_t *my_queue = NULL;
  6.     create_queue(&my_queue);
  7.     printf("my_queue = %p\n", my_queue);//非NULL
  8.  
  9.     //测试入队列
  10.     push_queue(my_queue, 10);
  11.     push_queue(my_queue, 20);
  12.     push_queue(my_queue, 30);
  13.     push_queue(my_queue, 40);
  14.     print_queue(my_queue); // 10 20 30 40
  15.  
  16.     //出队列
  17.     int num = 0;
  18.     pop_queue(my_queue, &num);
  19.     printf("num = %d\n", num);//10
  20.     pop_queue(my_queue, &num);
  21.     printf("num = %d\n", num);//20
  22.     print_queue(my_queue); // 30 40
  23.  
  24.     //入队列
  25.     push_queue(my_queue, 50);
  26.     push_queue(my_queue, 60);
  27.     print_queue(my_queue); // 30 40 50 60
  28.  
  29.     //清空
  30.     clean_queue(my_queue);
  31.     if(-1 == pop_queue(my_queue, &num)){
  32.         printf("没有出队列成功\n");
  33.     }
  34.     
  35.     //销毁
  36.     destroy_queue(&my_queue);
  37.     printf("my_queue = %p\n", my_queue);//NULL
  38.  
  39.     return 0;
  40. }
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/木道寻08/article/detail/915508
推荐阅读
相关标签

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

  

闽ICP备14008679号