对于循环队列的浅析

bosthhe1 commented 1 year ago

循环队列是为了空间反复利用，其原理是：在逻辑结构上收尾相连，形成一个循环，可以用链表，也可以用队列，这里面到核心思想就是判空和判满的问题，如果需要循环k个数字，我们开k个空间，那么我们怎么判空呢，很好理解，判空就是头和尾相等的时候判空，但是什么时候判满呢，也是头和尾相等吗？这时候就出现二义性性了，在k个空间下，判空和判满是无法满足k个数字的判空和判满的(需要注意的是tail是永远指向当前插入数据的下一个位置) @K`%6CX3CSRVI5PN5VT2MNI TMNWW WFOT72) Q3K8IVU$P 所以为了解决这个问题，我们就需要开辟k+1个空间，多的一个空间不存入数据，当头和尾相等的时候就为空，当尾在头的后面一格的时候就为满 34LNM@FS0EA)C5UH1UO}%_N )GR3F$TYQJ7VM97RRSIEN64

bosthhe1 commented 1 year ago

思路有了之后，就需要开始选择一种方式来模拟，虽然叫做循环队列，听起来也感觉是使用队列来完成循环，但是这个感觉是错误的，也不是说用队列来完成不行，只是用队列来完成相对麻烦，需要记录位置，要增加很多的工作量，但是使用数组来完成就很方便，数组的优势就在于可以通过下标来控制个数，也可以得到当前循环队列的状态，但是要想完成数组的循环，我们就必须要将数组走到最后一个元素的时候，走下一步就链接回去，这一步可以通过取模来完成，当tail走到下标为k的位置时候(相当于走到数组的结尾)，在走一步就需要回到数组第0个位置，k=(k+1)%(k+1),前一个位置是tail走的第k+1个位置，后面的k+1,为整体数组的长度(开辟了k+1个空间)，这时候算出来k为0，就可以实现循环。(这里不好理解建议画图)

bosthhe1 commented 1 year ago

循环队列的实现
typedef struct {
    int head;
    int tail;
    int *a;//用于开辟数组
    int k;//记录数组的长度
} MyCircularQueue;

MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue* obj =(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    int* tmp = (int *)malloc(sizeof(int)*(k+1));//需要多开辟一个空间
    obj->a=tmp;
    tmp =NULL;
    obj->k = k+1;//将数组的长度初始化为k+1
    obj->head =0;
    obj->tail =0;
    return obj;
}
//进入循环队列
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    int k = obj->k;
    //判满
    if((obj->tail+1)%k==obj->head)//判断tail的下一个位置是否和head重合，如果重合则为满，如果不重合就可以继续插入数据
    {
        return false;
    }
    //不满
    else
    {
        obj->a[obj->tail]=value;
        obj->tail = (obj->tail+1)%k;//当tail走到k+1的位置的时候，就需要回到对头
        return true;
    }
}
//出循环队列
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    //判不为空
    int k = obj->k;
    if((obj->head!=obj->tail))
    {
        obj->head = (obj->head+1)%k;
        return true;
    }
    //判空
    else
    {
        return false;
    }
}
//取对头的元素
int myCircularQueueFront(MyCircularQueue* obj) {
    int k = obj->k;
    if((obj->head==obj->tail))
    {
        return -1;
    }
    else
    {
        return obj->a[obj->head];
    }
}
//取队尾的元素
int myCircularQueueRear(MyCircularQueue* obj) {
    int k = obj->k;
    if((obj->head==obj->tail))
    {
        return -1;
    }
    else{
        return obj->a[(obj->tail-1+k)%k];
    }
}
//判断是否为空
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    int k = obj->k;
    if((obj->head==obj->tail))
    {
        return true;
    }
    return false;
}
//判断是否为满
bool myCircularQueueIsFull(MyCircularQueue* obj) {
    int k = obj->k;
    if((obj->tail+1)%k==obj->head)
    {
        return true;
    }
    return false;
}
//释放空间
void myCircularQueueFree(MyCircularQueue* obj) {
    free(obj->a);
    free(obj);
}

bosthhe1 / -

对于循环队列的浅析 #21