手把手设计C语言版循环队列(力扣622:设计循环队列)

简介: 手把手设计C语言版循环队列(力扣622:设计循环队列)

力扣: 622.设计循环队列


前言


队列会出现“假溢出”现象,即队列的空间有限,队列是在头和尾进行操作的,当元素个数已经达到最大个数时,队尾已经在空间的最后面了,但是对头前面的不一定是满的。针对这一现象,引入了循环队列。循环队列也是一种数据结构,小编在本篇文章中,是以力扣的一道题目为例来设计循环队列。


此时队尾rear已经到最后面了,但是队头front前面没有填满元素,因此并没有满

循环队列就是将队尾rear再次回到数组的前面,解决“假溢出”的现象

继续在队尾rear插入元素,直到真的满了


描述


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


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

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


  • MyCircularQueue(k): 构造器,设置队列长度为 k 。
  • Front: 从队首获取元素。如果队列为空,返回 -1 。
  • Rear: 获取队尾元素。如果队列为空,返回 -1 。
  • enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。
  • deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。
  • isEmpty(): 检查循环队列是否为空。
  • isFull(): 检查循环队列是否已满。


示例:


MyCircularQueue circularQueue = new MyCircularQueue(3); // 设置长度为 3 circularQueue.enQueue(1); // 返回 true circularQueue.enQueue(2); // 返回 true circularQueue.enQueue(3); // 返回 true circularQueue.enQueue(4); // 返回 false,队列已满 circularQueue.Rear(); // 返回 3 circularQueue.isFull(); // 返回 true circularQueue.deQueue(); // 返回 true circularQueue.enQueue(4); // 返回 true circularQueue.Rear(); // 返回 4


分析


在普通的队列中,队满的条件是rear==front,那么在循环队列中怎么判断队列已经满了?

常用的一个解决方法是,多开一个空间。也就是说,当队列满的时候,还是有一个空间没有被使用。


rear可能比front大,也可能比front所以尽管它们只相差一个位置时就是满的情,但也可能是相差整整一圈,所以若队列长度为k,那么需要多开辟一个空间,即k+1。因此,队满的额条件为(rear+1)%(k+1)==front。取模“%”的目的就是为了整合frontrear大小的问题,解决多绕了一圈的问题。

什么时候队列为空呢?

rear==front时队列为空。


总结一下就是:

  • rear==front时队列为空;
  • rear的下一个和front相等,则队列满


分析完队满、对空问题,回到本道题目就很好解决了。


构造器:

MyCircularQueue* obj是一个结构体指针,需要给obj开辟一个空间,其次开辟一个数组a,初始化frontback 以及k

MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue* obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    obj->a=(int *)malloc((k+1)*sizeof(int));
    obj->front=0;
    obj->back=0;
    obj->k=k;
    return obj;
}

判断队空、队满:

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    return obj->front==obj->back;
}
bool myCircularQueueIsFull(MyCircularQueue* obj) {
    return (obj->back+1)%(obj->k+1)==obj->front;
}

队尾插入:

首先需要判断队列是否已经满了,如果满了返回false,如果没有,执行插入操作。先插入,再将队尾obj->back++


需要注意的是,这里是一个循环队列,如果此时已经在最后一个单元里面插入元素,那么obj->back应该是回到前面,而不是继续往后。此时有需要用到取模“%”操作,使得 obj->back=(obj->back)%(obj->k+1)

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    if(myCircularQueueIsFull(obj))
        return false;
    obj->a[obj->back]=value;
    obj->back++;
    obj->back=(obj->back)%(obj->k+1);
    return true;
}

队头删除:


删除只需要将obj->front++即可


但是依然需要注意,这是一个循环队列,当obj-front在最后一片单元时,需要回到前面,obj->front=(obj->front)%(obj->k+1)


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

取队头元素:

先判断队列是否为空,不为空执行取队头操作

int myCircularQueueFront(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
        return -1;
    return obj->a[obj->front];
}

取队尾元素:

首先判断队列是否为空,不为空执行取队尾元素操作

需要注意的是,当obj->back==0时,此时取得应该是最后一个存储单元的元素,这里需要单独判断一下,其余的情况都是obj->back 前面一个单元的元素。

int myCircularQueueRear(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj)){
        return -1;
    }
    else if(obj->back==0)
    {
        return obj->a[obj->k];
   }
   else
    {
        return obj->a[obj->back-1];
    }
}

销毁:

void myCircularQueueFree(MyCircularQueue* obj) {
    free(obj->a);
    free(obj);
}


力扣AC代码

typedef struct {
    int *a;
    int front;
    int back;
    int k;
} MyCircularQueue;
MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue* obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    obj->a=(int *)malloc((k+1)*sizeof(int));
    obj->front=0;
    obj->back=0;
    obj->k=k;
    return obj;
}
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    return obj->front==obj->back;
}
bool myCircularQueueIsFull(MyCircularQueue* obj) {
    return (obj->back+1)%(obj->k+1)==obj->front;
}
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    if(myCircularQueueIsFull(obj))
        return false;
    obj->a[obj->back]=value;
    obj->back++;
    obj->back=(obj->back)%(obj->k+1);
    return true;
}
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
    {
        return false;
    }
    obj->front++;
    obj->front=(obj->front)%(obj->k+1);
    return true;
}
int myCircularQueueFront(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
        return -1;
    return obj->a[obj->front];
}
int myCircularQueueRear(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj)){
        return -1;
    }
   // return obj->a[(obj->back+obj->k)%obj->k+1];
    else if(obj->back==0)
    {
        return obj->a[obj->k];
   }
   else
    {
        return obj->a[obj->back-1];
    }
}
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);
*/


目录
相关文章
|
4月前
|
存储
「LeetCode」622. 设计循环队列
「LeetCode」622. 设计循环队列
26 0
LeetCode | 622. 设计循环队列
LeetCode | 622. 设计循环队列
|
5月前
|
存储
Leetcode622.设计循环队列
Leetcode622.设计循环队列
16 0
|
2月前
|
C语言
C语言数据结构(队列、循环队列)
C语言数据结构(队列、循环队列)
12 0
|
3月前
|
存储
leetcode-622:设计循环队列
leetcode-622:设计循环队列
20 1
|
4月前
|
机器学习/深度学习 存储
leetcode:循环队列
leetcode:循环队列
|
4月前
|
存储 算法 索引
【LeetCode刷题日志】622.设计循环队列
【LeetCode刷题日志】622.设计循环队列
|
4月前
|
C语言
C语言实现:设计循环队列(数组实现)
C语言实现:设计循环队列(数组实现)
|
4月前
|
算法 C语言
C语言 每日一题 力扣习题 10.19日 day1
C语言 每日一题 力扣习题 10.19日 day1
21 0
|
5月前
|
存储
Leetcode循环队列(数组实现及链表实现)
Leetcode循环队列(数组实现及链表实现)
38 0