数据结构(初阶4)---循环队列详解

1.循环队列的结构

  1).逻辑模式

与队列是大同小异的，
其中还是有一个指向队列头的head指针，
也有一个指向尾巴的tail指针

  不同之处在于它是一个环状的结构,通过增删的操作,
  head 与 tail的相对位置与实际位置都在时刻发生改变

2.实现接口

  1).初始化

typedef struct {
    int *_queue;
    int _size;
    int _tail;
    int _head;
    
} MyCircularQueue;
MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue *ret=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    ret->_queue=(int*)malloc(sizeof(int)*(k+1));
    ret->_size=k+1;
    ret->_tail=0;
    ret->_head=0;
    return ret;
}

 初始设置tail和head都是int类型的偏移量，而非指针
(非常关键,对于后续实现循环结构有重大作用)
queue就是我们的队列，k就是我们的初始化大小。
ps：我们这边不去使用动态增加

  2).判断空和满

接下来我们来理解一下其中的逻辑:>

如果我们的tail和head 都在移动，那是不是只要head == tail就代表我们的循环队列装满了。

  答案是错错错！！！！！！！！！！！！！！！！！！！！！

我们来举一个反例：

那么我们该怎样去实现呢:>
我们可以建立一个空的区域不存放任何东西，让它成为一个间隔点
理解如下：

为什么我们要%(obj->_size)呢
因为如果我们的tail大于了size时会进入循环，此时我们%(obji->_size)就让tail的偏移量回到了前面，不会造成溢出。

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    return obj->_tail==obj->_head;
}
//若空则返回真

bool myCircularQueueIsFull(MyCircularQueue* obj) {
    return (obj->_tail+1)%(obj->_size)==obj->_head;
}
//若满则返回真

  3).增加

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    if(myCircularQueueIsFull(obj))
    {
        return false;
    }
    *(obj->_queue+((obj->_tail)%(obj->_size)))=value;
    (obj->_tail)++;
    obj->_tail%=obj->_size;
    return true;
}

同理，我们这边使用%(obj->_size),也是为了纠正偏移量

  4).删除

bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
    {
        return false;
    }
    (obj->_head)++;
    obj->_head%=obj->_size;
    return true;
}

  5).找头

int myCircularQueueFront(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
    {
        return -1;
    }
    return *(obj->_queue+((obj->_head)%(obj->_size)));
}

  6).找尾

int myCircularQueueRear(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
    {
        return -1;
    }
    if(obj->_tail!=0)
    {
        return *(obj->_queue+((obj->_tail-1)%(obj->_size)));
    }
    else
    {
        return *(obj->_queue+obj->_size-1);
    }
}

找尾这里有一个陷阱，如果我们的 tail0。
那么我们还能用 *(obj->_queue+((obj->_tail-1)%(obj->_size))); 去寻尾吗，显然不行，因为会造成溢出。
所以：
我们先判断，再然后如果0，我们就直接返回相对 _queue 的末尾的值。

3.循环队列的特点

1.充分的利用了空间，不会产生普通队列频繁增删导致前面空间的浪费
2.循环复用空间提升了空间利用率。
3.需要固定大小的缓冲区场景(生产者消费者问题…)
4.操作的复杂度仅仅只有O(1)!!!

创作不易恳请留一个赞吧qwq

原文地址：https://blog.csdn.net/Mr_vantasy/article/details/143722557

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