用数组设计循环队列

大家好,我是芒果,一名非科班的在校大学生。对C/C++、数据结构、Linux及MySql、算法等领域感兴趣,喜欢将所学知识写成博客记录下来。 希望该文章对你有所帮助！如果有错误请大佬们指正！共同学习交流
作者简介:
CSDN C/C++领域新星创作者https://blog.csdn.net/chuxinchangcun?type=blog
掘金LV3用户 https://juejin.cn/user/1381426159953960
阿里云社区专家博主,星级博主,技术博主 https://developer.aliyun.com/profile/expert/5lkdbuggiiuhc
华为云云享专家 https://bbs.huaweicloud.com/community/myhomepage

题目

622. 设计循环队列 - 力扣（LeetCode） (leetcode-cn.com)

---

---

循环队列

• 1.符合先进先出
• 2.空间大小是固定的，一开始就要开辟好空间，空间重复利用
  • 若用链表实现，出数据不用释放空间

---

为了方便插入和删除：

定义两个变量：记为front和tail

入数据：tail往后走

出数据：front往后走

当tail/front走到最后一个位置还要往后走：回到第一个位置(循环)

---

分析：

存k个数据，只开辟k个空间的话

• 数组实现

判空和判满产生歧义！

• 链表实现

判空和判满产生歧义！

---

==解决办法：要存放k个数据，就开辟k+1个空间，否则无法实现判空和判满==

• 数组

判空 ：front == tail
判满： (tail + 1)%( k + 1) == front

---

• 链表

判空： front == tail
判满： tail->next == front

---

队列结构

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

typedef struct 
{
    int k ;//存放多少个数据
    int* a;//动态开辟的数组
    int front;//标志队头位置
    int tail;//标志队尾的下一个位置
} MyCircularQueue;

---

创建队列

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

MyCircularQueue* myCircularQueueCreate(int k) 
{
    MyCircularQueue* cq = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    //开辟k+1个空间
    cq->a = (int*)malloc(sizeof(int)*(k+1));
    cq->front = cq->tail = 0;
    //cq->k是存放多少个数据，所以写的是k  不是k+1
    cq-> k = k;
    return cq;
}

---

插入元素

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

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value)
{
    //插入数据-要保证队列没有满
    if(myCircularQueueIsFull(obj))
    {
        return false;
    }
    //插入到tail的位置，然后tail往后走
    obj->a[obj->tail] = value;
    obj->tail ++;
    //注意：如果tail到了最后一个位置的下一个位置
    //即k+1下标位置(第k+2的空间-越界),就要退回到第一个位置    
    if(obj->tail == obj->k+1)
    {
        obj->tail = 0;
    }
    //成功插入则返回真
    return true;
}

写法2：如果tail到了最后一个位置的下一个位置
即k+1下标位置(第k+2的空间-越界),就要退回到第一个位置

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value)
{
    //插入数据-要保证队列没有满
    if(myCircularQueueIsFull(obj))
    {
        return false;
    }
    //插入到tail的位置，然后tail往后走
    obj->a[obj->tail] = value;
    obj->tail ++;
    
    obj ->tail  %= (k+1);  //如果obj->tail == k+1 值就为0 ->回到第一个位置
    //否则则为obj->tail原来的值
     //成功插入则返回真
    return true;
}

---

删除元素

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

bool myCircularQueueDeQueue(MyCircularQueue* obj)
{
    //删除元素-要保证队列不为空
    //队列为空 ->返回false
    if(myCircularQueueIsEmpty(obj))
    {
        return false;
    }
    //删除元素 - front往后走
    obj->front++;
    //注意：如果front到了最后一个位置的下一个位置
    //即k+1下标位置(第k+2的空间-越界),就要退回到第一个位置
    if(obj->front == obj->k + 1)
    {
        obj->front = 0;
    }
    //成功删除则返回真
    return true;
}

和上面一样插入元素相同的 写法2：

bool myCircularQueueDeQueue(MyCircularQueue* obj)
{
    //删除元素-要保证队列不为空
    //队列为空 ->返回false
    if(myCircularQueueIsEmpty(obj))
    {
        return false;
    }
    //删除元素 - front往后走
    obj->front++;
     //如果obj->front == k+1 值就为0->回到第一个位置，否则则为obj->tail原来的值
	obj->front %= (k+1);
    //成功删除则返回真
    return true;
}

---

获取队尾元素

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

int myCircularQueueRear(MyCircularQueue* obj)
{
    //得到队尾数据-要保证队列不为空
    if(myCircularQueueIsEmpty(obj))
    {
        //如果队列为空，返回 -1 
        return -1;
    }
    //因为tail指向的是队尾元素的后一个位置
    //特殊情况：tail回到了第一个位置-此时k下标的(第K+1个空间)才是队尾数据
    if(obj->tail == 0)
    {
        return obj->a[obj->k];
    }
    else
    {
        return obj->a[obj->tail - 1];
    }
}

---

**写法2：**公式

返回(obj->tail + obj->k)%(obj->k+1)下标的值

int myCircularQueueRear(MyCircularQueue* obj)
{
        //得到队尾数据-要保证队列不为空
    if(myCircularQueueIsEmpty(obj))
    {
        //如果队列为空，返回 -1 
        return -1;
    }
    int i = (obj->tail + obj->k)%(obj->k+1);
    return obj->a[i];
}

---

获取队首元素

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

int myCircularQueueFront(MyCircularQueue* obj)
{
    //得到队头数据-要保证队列不为空
    if(myCircularQueueIsEmpty(obj))
    {
        //如果队列为空，返回 -1 
        return -1;
    }
    else
    {
        //front 指向的就说队头数据
        return obj->a[obj->front];
    }
}

---

判断是否为空队列

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

bool myCircularQueueIsEmpty(MyCircularQueue* obj) 
{
    //数组-front == tail就是空
    return obj->front == obj->tail;
}

---

判断队列是否满

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

bool myCircularQueueIsFull(MyCircularQueue* obj)
{
    //数组-(tail + 1) %(k+1) == front 就是满
    //要用括号括起来，防止运算顺序导致出错
    return (obj-> tail + 1 )%(obj->k + 1) == obj->front; 
}

---

释放队列

void myCircularQueueFree(MyCircularQueue* obj)
{
        //先释放动态开辟的数组
        free(obj->a);
        //再释放动态开辟的队列
        free(obj);
}

---

注意事项

要把判空和判满的声明先放在前面，因为我们实现的接口，判空和判满是在我们调用的前面的，如果不先声明，会报错

---

数组实现的代码

typedef struct 
{
    int k ;//存放多少个数据
    int* a;//动态开辟的数组
    int front;//标志队头位置
    int tail;//标志队尾的下一个位置
} MyCircularQueue;
//先声明两个判空和判满的函数
bool myCircularQueueIsEmpty(MyCircularQueue* obj) ;
bool myCircularQueueIsFull(MyCircularQueue* obj);
MyCircularQueue* myCircularQueueCreate(int k) 
{
    MyCircularQueue* cq = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    //开辟k+1个空间
    cq->a = (int*)malloc(sizeof(int)*(k+1));
    cq->front = cq->tail = 0;
    //cq->k是存放多少个数据，所以写的是k  不是k+1
    cq-> k = k;
    return cq;
}

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value)
{
    //插入数据-要保证队列没有满
    if(myCircularQueueIsFull(obj))
    {
        return false;
    }
    //插入到tail的位置，然后tail往后走
    obj->a[obj->tail] = value;
    obj->tail ++;
    //注意：如果tail到了最后一个位置的下一个位置
    //即k+1下标位置(第k+2的空间-越界),就要退回到第一个位置    
    if(obj->tail == obj->k+1)
    {
        obj->tail = 0;
    }
    //成功插入则返回真
    return true;
}

bool myCircularQueueDeQueue(MyCircularQueue* obj)
{
    //删除元素-要保证队列不为空
    //队列为空 ->返回false
    if(myCircularQueueIsEmpty(obj))
    {
        return false;
    }
    //删除元素 - front往后走
    obj->front++;
    //注意：如果front到了最后一个位置的下一个位置
    //即k+1下标位置(第k+2的空间-越界),就要退回到第一个位置
    if(obj->front == obj->k + 1)
    {
        obj->front = 0;
    }
    //成功删除则返回真
    return true;
}

int myCircularQueueFront(MyCircularQueue* obj)
{
    //得到队头数据-要保证队列不为空
    if(myCircularQueueIsEmpty(obj))
    {
        //如果队列为空，返回 -1 
        return -1;
    }
    else
    {
        //front 指向的就说队头数据
        return obj->a[obj->front];
    }
}

int myCircularQueueRear(MyCircularQueue* obj)
{
    //得到队尾数据-要保证队列不为空
    if(myCircularQueueIsEmpty(obj))
    {
        //如果队列为空，返回 -1 
        return -1;
    }
    //因为tail指向的是队尾元素的后一个位置
    //特殊情况：tail回到了第一个位置-此时k下标的(第K+1个空间)才是队尾数据
    if(obj->tail == 0)
    {
        return obj->a[obj->k];
    }
    else
    {
        return obj->a[obj->tail - 1];
    }
}

bool myCircularQueueIsEmpty(MyCircularQueue* obj) 
{
    //数组-front == tail就是空
    return obj->front == obj->tail;
}

bool myCircularQueueIsFull(MyCircularQueue* obj)
{
    //数组-(tail + 1) %(k+1) == front 就是满
    //要用括号括起来，防止运算顺序导致出错
    return (obj-> tail + 1 )%(obj->k + 1) == obj->front; 
}

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);
*/