• 常用数据结构 ——— 队列(环形队列和顺序队列)


    目录

    一、队列简介

    二、顺序队列

    三、环形队列

    四、环形队列代码

    1、队列结构体

    2、队列初始化

    3、判断队列是否为满

    4、判断队列是否为空

    5、将数据插入到队列中

    6、读取队列中的数据

    7、释放队列空间

    8、功能测试


    一、队列简介

            队列只允许在队列头(front)进行删除操作,在队列尾(rear)进行插入操作,当队列中没有元素时,称为空队列在队列中插入元素称为入队,从队列中删除元素称为出队。因为队列只允许在尾端插入,在头端删除,所以只有最早进入队列的元素才能最先从队列中删除,即队列有先进先出的特点。

    二、顺序队列

            即仅在队头进行删除在队尾进行插入,可用地址连续的存储单元依次存放队列中的数据,比如数组。队头和队尾的位置是变化的,所以要设置头、尾指针。  

            初始化时的头尾指针,均置为 0。 当头尾指针相等时队列为空或者为满,在非空队列里,头指针始终指向队头元素,尾指针始终指向队尾元素的下一位置。

            由队列的原理可以将头指针当做读操作,将尾指针当做写操作,即在尾端插入数据就是写入队列,在头端删除数据就是将队列中的数据读出,这样好理解点。

    刚开始头指针和尾指针都在同一位置

     当队列入队时,尾指针加一,头指针保持不变,a1入队,尾指针rear+1指向下一个地址空间,即尾指针始终指向队尾的下一地址,如a4入队后,尾指针rear+1 。

    队列出队时,尾指针保持不变,头指针依次加1,由先进先出原则,a1先入队,则a1先被读走,然后front+1,指向了 a2,a2删除后,front+1指向了 a3。

    当a5删除后,头指针和尾指针的指向又相同相等了,即说明队列中的数据 已经全部读走

    在顺序队列中,当尾指针已经指向了队列的最后一个位置的下一位置时,如果再有元素入队,就会发生“溢出”此时队列中已经填满了数据,头指针还在开始位置。

    顺序队列的 “假溢出” :即队列的存储空间并未填满,却发生了溢出。

            比如 rear 现在指向了最后一个位置的下一位置,按照上面所说此时队列已经被填满,如果再有元素入队,就会发生“溢出”,但这是在头指针没有移动的前提下,如果之前队列头也删除了一些元素,那么队列头指针经过n次的 +1 之后,会遗留下了很多空地址,但是顺序队列就会认为再有元素入队,就溢出,即出现 “假溢出” 现象,这是不合理的,故出现了环形队列

    三、环形队列

            环形队列的使用场景还是挺多的,比如要将单片机一些模块采集的数据连续上传到PC端,这里就可以用到环形队列,即将采集的数据放到队列中去,再将队列中的数据读出上传到PC端,这里为什么不直接将采集端和上传端直接相连呢?因为采集数据的速度和上传数据的速度是不知道的,如果直接相连会出错。

            环形队列的原理就是将新元素加入到第一个位置上,构成类似于一个环一样的队列,入队和出队还是按照“先进先出”的原则进行,环形队列的空间利用率高。

            环形队列解决了顺序队列 “假溢出” 的现象,但是又出现新的问题,即怎么判断队列是否为空,如果单用 rear = front 判断空或满显然是不行的,比如

             此时两种情况都是 rear = front 的情况,在环形队列中,当队列满了之后 rear + 1会指向第一个地址,即出现了  rear = front 的情况。

            一般判断队列空的条件是 rear = front, 通常少用一个元素的储存空间用来判断队列是否满,即在入队前测试尾指针加 1 后是否等于头指针,若相等则认为队满。

            或者当用数组array[len]来表示队列时,则可用(rear - front)的差和数组长度 len 进行比较,如果相等则说明队列已满,(在下面说明这种方法)。

    四、环形队列代码

     W等于尾指针rear,R等于头指针front,相当于写操作读操作

    1、队列结构体

    1. /*队列结构体*/
    2. typedef struct ring_buff{
    3. int array[len];
    4. int W;
    5. int R;
    6. }*ring;

    2、队列初始化

    1. /*队列初始化*/
    2. struct ring_buff *fifo_init(void)
    3. {
    4. struct ring_buff *p = NULL;
    5. p = (struct ring_buff *)malloc(sizeof(struct ring_buff));
    6. if(p == NULL){
    7. printf("malloc error\n");
    8. return -1;
    9. }else{
    10. p->W = 0;
    11. p->R = 0;
    12. memset(p->array,0,sizeof(p->array));
    13. return p;
    14. }
    15. }

    将队列相应空间清零。

    3、判断队列是否为满

    1. /*判断是否满*/
    2. int get_ring_buff_fullstate(struct ring_buff *P_ring_buff)
    3. {
    4. if((P_ring_buff->W - P_ring_buff->R) == len){
    5. return 1;
    6. }else{
    7. return 0;
    8. }
    9. }

            如上图所示,array[6] 的存储空间为array[0] - array[5],即6个数,当RW等于0时指向array[0],存入数据后W++,指向下一个地址,当W将array[5]存入数据后会自加一,此时W = 6,R = 0,下一次判断队列是否满时条件成立,即W  -   R  =  len,len为数组长度6

    4、判断队列是否为空

    1. /*判断是否为空*/
    2. int get_ring_buff_emptystate(struct ring_buff *P_ring_buff)
    3. {
    4. if(P_ring_buff->W == P_ring_buff->R){
    5. return 1;
    6. }else{
    7. return 0;
    8. }
    9. }

    当头指针和尾指针相等时判断为空

    5、将数据插入到队列中

    1. /*插入数据*/
    2. int ring_buff_insert(struct ring_buff *P_ring_buff,int data)
    3. {
    4. if(P_ring_buff == NULL){
    5. printf("insert P_ring_buff error\n");
    6. return -1;
    7. }
    8. /*判断队列是否满*/
    9. if(get_ring_buff_fullstate(P_ring_buff) == 1){
    10. printf("full\n");
    11. return -1;
    12. }
    13. P_ring_buff->array[P_ring_buff->W%len] = data;
    14. P_ring_buff->W++;
    15. return 0;
    16. }

    W = {0、1、2、3、4、5 },则array[W%len] = {0、1、2、3、4、5},刚好依次对应,当W = 6时,6 % 6 = 0,又从array[0]开始存储数据,这也是环形队列的关键,即形成闭环。

    6、读取队列中的数据

    1. /*读取数据*/
    2. int ring_buff_get(struct ring_buff *P_ring_buff)
    3. {
    4. int data = 0;
    5. if(P_ring_buff == NULL){
    6. printf("get P_ring_buff error\n");
    7. return -1;
    8. }
    9. data = P_ring_buff->array[P_ring_buff->R%len];
    10. P_ring_buff->R++;
    11. return data;
    12. }

    读取数据和写入数据类似,也是当R = 6时,6 % 6 = 0,又从array[0]开始读取数据

    7、释放队列空间

    1. /*销毁*/
    2. int ring_buff_destory(struct ring_buff *P_ring_buff)
    3. {
    4. if(P_ring_buff == NULL){
    5. printf("destory P_ring_buff error\n");
    6. return -1;
    7. }
    8. free(P_ring_buff);
    9. return 0;
    10. }

    8、功能测试

    1. #define len 6
    2. int main()
    3. {
    4. int i;
    5. int getData = 0;
    6. /*初始化队列*/
    7. ring Pt_ring_buff = fifo_init();
    8. /*向队列中写数据,即0 - 5*/
    9. for(i = 0;i < 6;i++){
    10. ring_buff_insert(Pt_ring_buff,i);
    11. }
    12. /*将写入的数据读出三个,由先进先出原则应该读的0 - 2*/
    13. for(i = 0;i < 3;i++){
    14. printf(" %d",ring_buff_get(Pt_ring_buff));
    15. }
    16. printf("\n");
    17. /*再写入三个数据,此时写入的数据应该在上面的数据之后,即在5之后*/
    18. for(i = 8;i < 11;i++){
    19. ring_buff_insert(Pt_ring_buff,i);
    20. }
    21. /*读取队列中的数据,此时再次读取队列中的数据时,0 - 2 已经被读走,所以应该是从3、4、5、8、9、10、3 ...循环读取十个数据*/
    22. for(i = 0;i < 10;i++){
    23. printf(" %d",ring_buff_get(Pt_ring_buff));
    24. }
    25. ring_buff_destory(Pt_ring_buff); //释放空间
    26. printf("\n");
    27. system("pause");
    28. return 0;
    29. }

    输出结果

  • 相关阅读:
    全排列——dfs(剪枝/回溯)
    随机规划——报童模型
    磁场发生器EM1电磁铁的主要技术参数
    学习UI第一天
    [linux] SFTP文件传输基本命令 --- xshell 直接上传文件
    TypeScript开启
    大数据开发语言Scala入门:新手小白学习指南
    【操作系统】线程&进程相关
    【STM32】基于HAL库建立自己的低功耗模式配置库(STM32L4系列低功耗所有配置汇总)
    LeetCode每日一题(44. Wildcard Matching)
  • 原文地址:https://blog.csdn.net/qq_48458789/article/details/128134821