当前位置：首页 > article >正文

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

article 2024/11/17 13:38:26

循环队列

1.循环队列的结构
- 1).逻辑模式
2.实现接口
- 1).初始化
- 2).判断空和满
- 3).增加
- 4).删除
- 5).找头
- 6).找尾
3.循环队列的特点

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 的末尾的值。
在这里插入图片描述