设计循环队列

admin2024-05-15  0

 622. 设计循环队列 - 力扣(LeetCode)

设计循环队列,第1张

实现逻辑

空间大小是固定的

这一道题用链表实现看起来是特别有优势

我们可以搞成循环链表

设计循环队列,第2张

循环队列想可以重复使用这些空间

也就是到尾部,就绕回去了,也就是有限空间的无限利,保证先进先出,重复使用

就像图书馆,就四个座位,走一个人补一个人

什么时候是空,什么时候是满(此时我们怎么区分空和满)

方法1,增加size记录空还是满

size==0 也就是空

size==k也就是满

方法2:额外多开一个空间(永远空一个空间,也就是不存在满的时候,相等)

也就是五个空间放四个数据,多开一个空间解决空和满

设计循环队列,第3张

当最后一个是空的时候,又不满足了

设计循环队列,第4张

所以我们得到(什么用取模来解决回绕)

设计循环队列,第5张

图解设计循环队列,第6张

设计循环队列,第7张

设计循环队列,第8张设计循环队列,第9张

代码

typedef struct 
{
    int* a;//首元素的地址
    int phead;//头
    int ptile;//尾
    int size;//空间的实际个数(不是开辟个数)
} MyCircularQueue;

// 构造器,设置队列长度为 k (初始化)
MyCircularQueue* myCircularQueueCreate(int k) 
{
    //开辟空间的时候 多开辟一个空间
    MyCircularQueue* obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    obj->a = malloc(sizeof(int)*(k+1));
    obj->phead=0;
    obj->ptile=0;
    obj->size=k;
    return obj;
}
//进行插入
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) 
{   
    if((obj->ptile+1)%(obj->size+1) == obj->phead)
    {
        return false;//队列已满
    }
    //插入
    obj->a[obj->ptile] = value;
    obj->ptile = (obj->ptile+1)%(obj->size+1);
    return true;
}
//删除一个元素
bool myCircularQueueDeQueue(MyCircularQueue* obj) 
{
    if(obj->phead == obj->ptile)
    {
        return false;
    }
    //删除元素只需要头部减少一个就好、
    obj->phead = (obj->phead+1)%(obj->size+1);
    
    return true; 
}
//获取首元素
int myCircularQueueFront(MyCircularQueue* obj) 
{
    if(obj->phead == obj->ptile)
    {
        return -1;
    }
    return obj->a[(obj->phead)%(obj->size+1)];    
}
//获取队尾元素
int myCircularQueueRear(MyCircularQueue* obj) 
{
    if(obj->phead == obj->ptile)
    {
        return -1;
    }
    return obj->ptile == 0 ? obj->a[obj->size]:obj->a[obj->ptile-1];   
}
//进行判空
bool myCircularQueueIsEmpty(MyCircularQueue* obj) 
{
    return obj->phead == obj->ptile;
}
//判满
bool myCircularQueueIsFull(MyCircularQueue* obj) 
{
    return (obj->ptile+1)%(obj->size+1) == obj->phead;
}
//释放节点
void myCircularQueueFree(MyCircularQueue* obj) 
{
    free(obj->a);
    free(obj);
}

/**
 * Your MyCircularQueue struct will be instantiated and called as such:
 * MyCircularQueue* obj = myCircularQueueCreate(k);
 * bool param_1 = myCircularQueueEnQueue(obj, value);
 
 * bool param_2 = myCircularQueueDeQueue(obj);
 
 * int param_3 = myCircularQueueFront(obj);
 
 * int param_4 = myCircularQueueRear(obj);
 
 * bool param_5 = myCircularQueueIsEmpty(obj);
 
 * bool param_6 = myCircularQueueIsFull(obj);
 
 * myCircularQueueFree(obj);
*/

代码解释

这段代码定义了一个循环队列 MyCircularQueue 的数据结构及其操作函数。循环队列是一种使用固定大小的缓冲区并按循环方式使用它的队列。以下是对每个部分的详细解释:

  1. 循环队列结构体定义

    typedef struct 
    { int* a; // 指向队列元素数组的指针 int phead; // 队列头部的索引 
    int ptail; // 队列尾部的索引 
    int size; // 队列的容量 
    } 
    MyCircularQueue;
  2. 构造器 myCircularQueueCreate

    这个函数用于创建一个新的循环队列,分配一个大小为 k+1 的数组(多一个空间用于处理队列满的逻辑),并初始化队列头尾索引。

  3. 入队操作 myCircularQueueEnQueue

    这个函数用于在队列尾部添加一个新元素。如果队列已满(即 ptail 的下一个位置是 phead 的当前位置),则返回 false;否则,将新值存入尾部,然后按循环方式更新 ptail

  4. 出队操作 myCircularQueueDeQueue

    这个函数用于移除队列头部的元素。如果队列已空(即 phead 等于 ptail),则返回 false;否则,按循环方式更新 phead

  5. 获取队首元素 myCircularQueueFront

    这个函数用于获取队首元素的值。如果队列为空,则返回 -1

  6. 获取队尾元素 myCircularQueueRear

    这个函数用于获取队尾元素的值。如果队列为空,则返回 -1。由于循环队列的尾部可能在数组的开始处,所以需要特殊处理。

  7. 判断队列是否为空 myCircularQueueIsEmpty

    这个函数用于判断队列是否为空,即检查 pheadptail 是否相等。

  8. 判断队列是否为满 myCircularQueueIsFull

    这个函数用于判断队列是否为满,即检查 ptail 的下一个位置是否是 phead 的当前位置。

  9. 释放队列 myCircularQueueFree

    这个函数用于释放循环队列所占用的内存。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明原文出处。如若内容造成侵权/违法违规/事实不符,请联系SD编程学习网:675289112@qq.com进行投诉反馈,一经查实,立即删除!