622.设计循环队列(LeetCode)

简介: 622.设计循环队列(LeetCode)

image.png

思路

先确定什么情况为空,什么情况为满

这里有两种解决方案

1.留一个空间空置,当rear+1 == front时 ,则队列为满 (这里我们选用方案一)

2.增加一个size变量记录数据个数,size == 0则为空,size == k则为满


第一部分,确定为空的情况,我们规定:当front == rear时,队列为空(此时rear表示的是尾部元素的下一位,和栈中的top有异曲同工之妙)。

第二部分,确定为满的情况,当rear+1 == front时 ,则队列为满

实现一(用链表实现)

我们先来分析一下链表实现的场景,先给一个单向循环链表

push 1 2 3 4 5,此时达到了满的条件:rear->next == front

pop 2次 ,front只用往后两个节点即可,并不用修改数据(因为后面继续push会覆盖)

此时不满,又可以继续push 6 7,rear接着向后移动,并且插入新数据

这样看起来,是不是链表实现还挺简单的?但是,这里有一个接口就很难受了——获取队尾数据

有没有解决方法呢?肯定有,只是比较麻烦。 有三种解决方案,第一种双向链表,第二种增加一个rearPrev指针,每次rear往后移时,rearPrev要记录前一个位置,第三种遍历获取队尾数据

那有人可能会说,我可以让rear指向队尾元素,那开头rear就必须指向NULL,又多出了对空指针的判断。所以牵一发而动全身,这里用链表实现可以,但比较麻烦。

实现二 (用数组实现 )

那么链表实现比较麻烦,数组实现就简单吗?确实!这里用数组实现队列,代码会简洁不少,所以这里详细讲解用数组实现,有兴趣的小伙伴也可以去实现链表。

同样,先给一个空数组,满足front == rear的条件

push 1 2 3 4 5,此时rear+1 == front,达到满的条件。可是,rear+1 ==front是我们假想它是循环的,现实中应该怎么书写判满的条件呢?

假设循环队列存储k个有效数据,此时k == 5,开辟6个空间。  标出下标,那么此时我们可以利用取模,得出(rear+1)%(k+1)== front 的条件,其中k+1是空间个数,此时rear==5,+1为6,取模6,就变为0,就与front相等了(是不是很神奇?)

让我们再来看看其他情况 ,我们先pop 3次,让队列可以插入

push 6 7 8 9,最后一个失败,此时又为满,再来分析一下:rear==2,+1为3,取模6,还是3,正好是front(是不是又验证了一遍我们的判断条件?)

分析了这么久,我们终于要开始写代码了。


先创建MyCircularQueue结构体,并对其初始化 (这里就省略申请失败的条件,因为oj题基本不会申请失败),注意这里记得数组a开辟k+1个空间

和分析一样,先写出判空和判满的函数 ,有了前面的分析,这里是不是就很好理解了?

空:front == rear

满:(rear+1)%(k+1)==  front

向循环队列插入数据,先判断队列是否为满,如果不满,在队尾rear插入数据,rear++(不过注意,rear有可能在边界,++要循环回来,所以最后%=(k+1));如果为满,则返回false,表示插入失败。

从循环队列删除数据,同样也先判断队列是否为空,如果不空,则front++,再%=(k+1);如果为空,则表示删除失败,返回false

获取队头元素,这个也超级简单。先判断是否为空,不为空,则直接返回下标为front的元素;如果为空,则返回-1

获取队尾数据关键点来了。我们就是因为链表实现这个功能复杂,才选择了数组,让我们来看看数组是怎样实现这个功能的呢?一般情况,rear如果不在边界,我们就返回下标为rear-1的元素,如果rear刚好在最左边,那就返回下标为k的元素。这里可以用一个条件判断来写代码。


但是,有一种更妙的方法,先判断是否为空,不为空,则返回下标为(rear+k)%(k+1)的元素。这是什么意思呢?其实完整的写是(rear-1+k+1)%(k+1),相当于rear为0是,rear-1为-1,但是此时加上k+1,再取模k+1,就变成了k。(是不是很妙?)

最后,就是简单的释放空间,先释放数组空间,再释放队列空间。

完整代码附上:

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


相关文章
|
6月前
|
存储
手把手设计C语言版循环队列(力扣622:设计循环队列)
手把手设计C语言版循环队列(力扣622:设计循环队列)
54 0
|
6月前
|
存储
「LeetCode」622. 设计循环队列
「LeetCode」622. 设计循环队列
47 0
LeetCode | 622. 设计循环队列
LeetCode | 622. 设计循环队列
|
12月前
|
存储
Leetcode622.设计循环队列
Leetcode622.设计循环队列
28 0
|
6月前
|
存储
LeetCode——622设计循环队列
LeetCode——622设计循环队列
|
索引
LeetCode:设计循环队列
LeetCode:设计循环队列
45 0
|
6月前
|
存储
leetcode-622:设计循环队列
leetcode-622:设计循环队列
35 1
|
6月前
|
机器学习/深度学习 存储
leetcode:循环队列
leetcode:循环队列
|
11月前
|
存储 算法 索引
【LeetCode刷题日志】622.设计循环队列
【LeetCode刷题日志】622.设计循环队列
|
12月前
|
存储
Leetcode循环队列(数组实现及链表实现)
Leetcode循环队列(数组实现及链表实现)
78 0