• 【力扣题:循环队列】


    一.题目描述

    设计你的循环队列实现。 循环队列是一种线性数据结构,其操作表现基于 FIFO(先进先出)原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。
    循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里,一旦一个队列满了,我们就不能插入下一个元素,即使在队列前面仍有空间。但是使用循环队列,我们能使用这些空间去存储新的值。

    你的实现应该支持如下操作:

    MyCircularQueue(k): 构造器,设置队列长度为 k 。
    Front: 从队首获取元素。如果队列为空,返回 -1 。
    Rear: 获取队尾元素。如果队列为空,返回 -1 。
    enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。
    deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。
    isEmpty(): 检查循环队列是否为空。
    isFull(): 检查循环队列是否已满。

    二. 思路解析

    1. 循环队列给定了长度,即空间大小固定为k个,但开辟空间为k+1个,原因如下:
      在这里插入图片描述
      当空的时候,front和rear相等,满的时候也相等所以无法判别,增加一个空间不用就可以解决问题。
      例如k=5,只能有五个元素,当(rear+1)%(k+1)==front时,即满。
      在这里插入图片描述
    2. 返回队头元素,直接返回front位置即可,返回队尾元素,因为是rear指向的前一个,就有特殊的当rear指向第一个,队尾元素而是最后一个,此时队尾位置满足(rear+k)%(k+1)。
      在这里插入图片描述
      3.插入元素直接再rear位置上插,然后rear++,但极端情况,当rear++指向最后一个位置后面,此时应该跳到第一个位置,即rear = rear%(k+1);
    3. 删除元素,直接front++,但是当front在最后一个位置,此时++到第一个位置,即front=front%(k+1);
      在这里插入图片描述

    三. 代码实现

    
    typedef struct {
        int* a;
        int front;
        int rear;
        int k;
    } MyCircularQueue;
    
    
    MyCircularQueue* myCircularQueueCreate(int k) {
        MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
        obj->a = (int*)malloc(sizeof(int)*(k+1));
        obj->front = obj->rear = 0;
        obj->k = k;
        return obj;
    }
    
    bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
        if(obj->rear==obj->front)
            return true;
        return false;
    }
    
    bool myCircularQueueIsFull(MyCircularQueue* obj) {
        if((obj->rear+1)%(obj->k+1)==obj->front)
            return true;
        return false;
    }
    bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
        if(myCircularQueueIsFull(obj))
            return false;
        obj->a[obj->rear] = value;
        obj->rear++;
        obj->rear%=(obj->k+1);
        return true;
    }
    
    bool myCircularQueueDeQueue(MyCircularQueue* obj) {
        if(myCircularQueueIsEmpty(obj))
            return false;
        obj->front++;
        obj->front%=(obj->k+1);
        return true;
    }
    
    int myCircularQueueFront(MyCircularQueue* obj) {
        if(myCircularQueueIsEmpty(obj))
            return -1;
        return obj->a[obj->front];
    }
    
    int myCircularQueueRear(MyCircularQueue* obj) {
        if(myCircularQueueIsEmpty(obj))
            return -1;
        (obj->rear+obj->k)%(obj->k+1);
        return obj->a[(obj->rear+obj->k)%(obj->k+1)];
    }
    
    
    void myCircularQueueFree(MyCircularQueue* obj) {
        free(obj->a);
        free(obj);
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
  • 相关阅读:
    跟我学c++高级篇——模板的ADL
    Pytroch 常见问题总结
    Docker 镜像全军覆没后,如何给Ubuntu手动安装 docker 服务
    只问耕耘,不问收获,其实收获却在耕耘中
    js面试题==和===
    request、response、session、application、out对象主要方法
    Java中该如何面向对象以及类的定义、使用和实例化
    Android Studio Giraffe解决gradle reload failed问题
    linux排查木马后门之定时任务计划
    Maven从入门到放弃-坐标和依赖详解
  • 原文地址:https://blog.csdn.net/2301_76560014/article/details/134428792