设计循环队列

链接：（622. 设计循环队列 - 力扣（LeetCode））

分析问题：

既然循环，什么时候是满的，什么时候是空的？用什么实现，数组还是链表？

这里选择用数组，个人习惯吧，因为是循环的问题，链表循环比较麻烦，需要频繁的改变指针域。

思路：

一个指向头，一个指向尾。

问题一：队列满和队列空的判断冲突了（空：front==back，满：front==back）。

问题二：只有一个节点和没有节点的时候，这两个指向都相同，需要处理一下。

解决思路：问题一：多开一个数组空间。（也可以用size标记有效数据个数，push时，size就+1。这样队列满的时候，size==k，队列空，size==0）问题二：if条件特殊判断一下。

重要代码逻辑：在入数据和出数据时，就需要考虑越界的问题。这是数组必须要考虑的问题。

只要是数组，就容易发生越界问题；只要是指针，就容易发生越界和空指针的问题，老生常谈的问题了。

这里用了一个取模的小技巧。为了解决数组头到数组尾或者数组尾到数组头的问题。

eg：（2+k）% k = 2。(k+k) % k = k % k= 0 不管k是多少，前面两者都成立。

参考代码

typedef struct {
    int* a;    //数组
    int front; //头
    int rear;  //尾
    int k;     //有效数据个数
} MyCircularQueue;

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    return obj->front==obj->rear;
}
bool myCircularQueueIsFull(MyCircularQueue* obj) {
    return (obj->rear+1)%(obj->k+1)==obj->front;
}
MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue* obj=(MyCircularQueue* )malloc(sizeof(MyCircularQueue));
   
    obj->a=malloc(sizeof(int)*(k+1));
    obj->front=obj->rear=0;
    obj->k=k;
    return obj;
}

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    //插入。成功返回true
    if(myCircularQueueIsFull(obj)){
        return false;
    }
    else{
        obj->a[obj->rear]=value;
        obj->rear++;
        obj->rear = obj->rear % (obj->k+1);
        return true;
    }
}

bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj)){
        return false;
    }
    obj->front++;
    //最坏情况，front+1==k+1,
    //回到数组a[0]
    obj->front %= obj->k+1;
    return true;
}

int myCircularQueueFront(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj)){
        return -1;
    }
    int front=obj->a[obj->front];
    return front;
}

int myCircularQueueRear(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj)){
        return -1;
    }
    //eg: 2+5=7 7%5=2
    int tail = (obj->rear-1 +(obj->k+1) ) % (obj->k+1);
    return obj->a[tail];
}


void myCircularQueueFree(MyCircularQueue* obj) {
    free(obj->a);
    free(obj);
}

原文地址：https://blog.csdn.net/2301_79202899/article/details/143839797

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！