设计循环队列-阿里云开发者社区

另外扩展了解一下，实际中我们有时还会使用一种队列叫【循环队列】。如操作系统讲解【生产者消费者模型】时可以就会使用循环队列。环形队列可以使用【数组】实现，也可以使用循环【链表】实现。我们今天来实现一下。

设计循环队列

设计你的循环队列实现。循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。

循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。

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

MyCircularQueue(k): 构造器，设置队列长度为 k 。

Front: 从队首获取元素。如果队列为空，返回 -1 。

Rear: 获取队尾元素。如果队列为空，返回 -1 。

enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。

deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。

isEmpty(): 检查循环队列是否为空。

isFull(): 检查循环队列是否已满。

🙂【1】数组循环队列

这个【数组循环队列】在逻辑上是如上图所示，但是在物理上，不是循环的。所以特别注意：关于数组循环的这个点，我们必须手动控制。

思路分析

❓1

空和放一个元素怎么区分？

方法1：back初始化为0，指向队尾元素的下一个位置。

方法2：back初始化为-1，指向队尾元素。

特别提醒！：用方法1比较好控制

❓2

空和满怎样去区分（用方法1区分空和一个元素）？

方法1：设置size。

方法2：malloc多一个空间，不放置元素。（k+1)

以上两者方法都可以。

❓3

怎么处理数组物理上不循环（改成逻辑上循环）？

(back+1)%(k+1) = fron

obj->back %= obj->k+1

return obj->a[(obj->back-1+obj->k+1)%(obj->k+1)]

这里是以判空和满的来讲解，其他的插入和取尾元素是同理的！！

易错总结

临时变量出了函数就销毁了，必须malloc
A%B（A>B对A来说是没有任何影响，A<=B对A来说模去多余的B）---用来处理数组回绕地方
操作符优先级所以最好都加上括号
处理的表达式的左边不能为计算式（❌obj->front+1%=obj->k+1;）
判空和满直接下标运算即可，不用用数组（为什么不能用数组❓）
释放空间先释放数组空间，在释放myCircularQueue

创建MyCircularQueue

//用数组实现+多开辟一个空间不放元素
typedef struct {
    int*a;
    int front;
    int back;//数组下标
    int k;//循环队列的最多放置数据
} MyCircularQueue;

初始化myCircularQueueCreate

MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue*obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    int*tmp=(int*)malloc(sizeof(int)*(k+1));//多开辟一个空间
    obj->a=tmp;
    obj->front=0;
    obj->back=0;//指向最后一个元素的下一个
    obj->k=k;
    return obj;
}

为空否myCircularQueueIsEmpty

//判断循环队列是否为空
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    return obj->front == obj->back;//==0 
}

为满否myCircularQueueIsFull

//判断是否为满
bool myCircularQueueIsFull(MyCircularQueue* obj) {
    return (obj->back+1) % (obj->k+1) == obj->front;//back+1=front
    //操作符优先级问题
}

插入元素myCircularQueueEnQueue

考虑下这个特殊情况！

//插入元素
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    if(myCircularQueueIsFull(obj))//true 满了
    {
        return false;
    }
        obj->a[obj->back] = value;
        obj->back++;
        obj->back %= obj->k+1;//处理
        //obj->front+1%=obj->k+1;//处理左边不能为计算表达式
       return true;
}

删除元素myCircularQueueDeQueue

考虑下这个特殊情况！

//删除元素
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
    {
        return false;
    }
    else
    {
        obj->front++;
        obj->front%=obj->k+1;//处理
        return true;
    }
}

获取首元素myCircularQueueFront

//获取首元素
int myCircularQueueFront(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
    {
        return -1;
    }
    else
    return obj->a[obj->front];
}

获取尾元素myCircularQueueRear

考虑下这个特殊情况！

//获取尾元素
int myCircularQueueRear(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
    {
        return -1;
    }
    else
    //return obj->a[(obj->back-1+obj->k+1)%(obj->k+1)];
    return obj->a[(obj->back+obj->k)%(obj->k+1)];
}

释放空间myCircularQueueFree

//释放空间
void myCircularQueueFree(MyCircularQueue* obj) {
    free(obj->a);
    free(obj);
    obj=NULL;
}

🆗【1】总代码

//用数组实现+多开辟一个空间不放元素
typedef struct {
    int*a;
    int front;
    int back;//数组下标
    int k;//循环队列的最多放置数据
} MyCircularQueue;
MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue*obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    int*tmp=(int*)malloc(sizeof(int)*(k+1));//多开辟一个空间
    obj->a=tmp;
    obj->front=0;
    obj->back=0;//指向最后一个元素的下一个
    obj->k=k;
    return obj;
}
//判断循环队列是否为空
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    return obj->front == obj->back;//==0 
}
//判断是否为满
bool myCircularQueueIsFull(MyCircularQueue* obj) {
    return (obj->back+1) % (obj->k+1) == obj->front;//back+1=front
    //操作符优先级问题
}
//插入元素
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    if(myCircularQueueIsFull(obj))//true 满了
    {
        return false;
    }
        obj->a[obj->back] = value;
        obj->back++;
        obj->back %= obj->k+1;//处理
        //obj->front+1%=obj->k+1;//处理左边不能为计算表达式
       return true;
}
//删除元素
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
    {
        return false;
    }
    else
    {
        obj->front++;
        obj->front%=obj->k+1;//处理
        return true;
    }
}
//获取首元素
int myCircularQueueFront(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
    {
        return -1;
    }
    else
    return obj->a[obj->front];
}
//获取尾元素
int myCircularQueueRear(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
    {
        return -1;
    }
    else
    //return obj->a[(obj->back-1+obj->k+1)%(obj->k+1)];
    return obj->a[(obj->back+obj->k)%(obj->k+1)];
}
//释放空间
void myCircularQueueFree(MyCircularQueue* obj) {
    free(obj->a);
    free(obj);
    obj=NULL;
}

🙂【2】链表循环队列

链表很简单对于处理循环的问题，只要实现单项循环链表即可。这里的难点就是：（1）创建单项循环链表。（2）找到back的前一个元素

思路分析

关于判【空/一个元素】& 判【空/满】都是和上面数组是一样的。这里不过多阐述。

❓

怎么去找到back的前一个元素？

其实这个问题在我们前面博文实现链表也详细讲解，相信大家可以轻松掌握！！

Node*prev=obj->front;
        while(prev->next != obj->back)
        {
            prev=prev->next;
        }

易错总结

初始化一定要把back置回开头
找back前一个元素：要么用三个指针，要么遍历一遍链表。
释放空间不能遍历去释放，会造成野指针。
释放空间先把循环链表改变成单向链表，才能循环遍历释放。

创建MyCircularQueue

typedef struct Node
{
    int val;
    struct Node*next;
}Node;//节点
typedef struct {
    Node*front;
    Node*back;    
    int size;//计算放入队列的元素个数
} MyCircularQueue;//循环队列

初始化myCircularQueueCreate

MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue*obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    obj->front=NULL;
    obj->back=NULL;
    while(k--)
    {
            Node*newnode=(Node*)malloc(sizeof(Node));
            if(obj->front == NULL)
            {
                obj->front=obj->back=newnode;
                obj->front->val=0;
            }
            else
            {
                obj->back->next=newnode;
                obj->back=newnode;
                obj->back->val=0;
            }
    }
    //循环
    obj->back->next=obj->front;
    //back
    obj->back=obj->front;
    //
    obj->size=0;
    return obj;
}

为空否myCircularQueueIsEmpty

//判断循环队列是否为空
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    if(obj->size == 0 && obj->front == obj->back)
    return true;
    else
    return false;
}

为满否myCircularQueueIsFull

//判断是否为满
bool myCircularQueueIsFull(MyCircularQueue* obj) {
    if(obj->size != 0 && obj->front == obj->back)
    return true;
    else
    return false;
}

插入元素myCircularQueueEnQueue

//插入元素
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    if(myCircularQueueIsFull(obj))//true 满了
    {
        return false;
    }
    else
    {
        obj->back->val=value;
        obj->back=obj->back->next;
        obj->size++;
        return true;
    }
}

删除元素myCircularQueueDeQueue

//删除元素
bool myCircularQueueDeQueue(MyCircularQueue* obj)
{
    if(myCircularQueueIsEmpty(obj))
    {
        return false;
    }
    else
    {
        obj->front=obj->front->next;//❌易错
        obj->size--;
        return true;
    }
}

获取首元素myCircularQueueFront

//获取首元素
int myCircularQueueFront(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
    {
        return -1;
    }
    return obj->front->val;
}

获取尾元素myCircularQueueRear

//获取尾元素
int myCircularQueueRear(MyCircularQueue* obj) 
{
    if(myCircularQueueIsEmpty(obj))
    {
        return -1;
    }
    //❌易错
    else
    {
        Node*prev=obj->front;
        while(prev->next != obj->back)
        {
            prev=prev->next;
        }
        return prev->val;
    }
}

释放空间myCircularQueueFree

//释放空间
//❌易错
void myCircularQueueFree(MyCircularQueue* obj) {
    Node*prev=obj->front;
    while(prev->next != obj->front)
    {
        prev=prev->next;
    }
    //prev是最后一个
    prev->next=NULL;
    //
    while(obj->front->next != NULL)
    {
        Node*tmp=obj->front;
        obj->front=obj->front->next;
        free(tmp);
        tmp=NULL;
    }
    free(obj->front);
    obj->front=NULL;
    free(obj);
    obj=NULL;
}

🆗【2】总代码

typedef struct Node
{
    int val;
    struct Node*next;
}Node;//节点
typedef struct {
    Node*front;
    Node*back;    
    int size;//计算放入队列的元素个数
} MyCircularQueue;//循环队列
MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue*obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    obj->front=NULL;
    obj->back=NULL;
    while(k--)
    {
            Node*newnode=(Node*)malloc(sizeof(Node));
            if(obj->front == NULL)
            {
                obj->front=obj->back=newnode;
                obj->front->val=0;
            }
            else
            {
                obj->back->next=newnode;
                obj->back=newnode;
                obj->back->val=0;
            }
    }
    //循环
    obj->back->next=obj->front;
    //back
    obj->back=obj->front;
    //
    obj->size=0;
    return obj;
}
//判断循环队列是否为空
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    if(obj->size == 0 && obj->front == obj->back)
    return true;
    else
    return false;
}
//判断是否为满
bool myCircularQueueIsFull(MyCircularQueue* obj) {
    if(obj->size != 0 && obj->front == obj->back)
    return true;
    else
    return false;
}
//插入元素
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    if(myCircularQueueIsFull(obj))//true 满了
    {
        return false;
    }
    else
    {
        obj->back->val=value;
        obj->back=obj->back->next;
        obj->size++;
        return true;
    }
}
//删除元素
bool myCircularQueueDeQueue(MyCircularQueue* obj)
{
    if(myCircularQueueIsEmpty(obj))
    {
        return false;
    }
    else
    {
        obj->front=obj->front->next;
        obj->size--;
        return true;
    }
}
//获取首元素
int myCircularQueueFront(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
    {
        return -1;
    }
    return obj->front->val;
}
//获取尾元素
int myCircularQueueRear(MyCircularQueue* obj) 
{
    if(myCircularQueueIsEmpty(obj))
    {
        return -1;
    }
    else
    {
        Node*prev=obj->front;
        while(prev->next != obj->back)
        {
            prev=prev->next;
        }
        return prev->val;
    }
}
//释放空间
void myCircularQueueFree(MyCircularQueue* obj) {
    Node*prev=obj->front;
    while(prev->next != obj->front)
    {
        prev=prev->next;
    }
    //prev是最后一个
    prev->next=NULL;
    //
    while(obj->front->next != NULL)
    {
        Node*tmp=obj->front;
        obj->front=obj->front->next;
        free(tmp);
        tmp=NULL;
    }
    free(obj->front);
    obj->front=NULL;
    free(obj);
    obj=NULL;
}

还有数据结构的【栈】和操作系统的【栈】是不一样的。数据结构的【栈】是一种线性表。操作系统的【栈】是内存的区域，会发生栈溢出和内存泄露的问题（递归程序/返回条件有问题），但是数据结构【栈】不会。

✔✔✔✔✔最后，感谢大家的阅读，若有错误和不足，欢迎指正！

设计循环队列