思路
先确定什么情况为空,什么情况为满。
这里有两种解决方案,
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); */