题目要求
设计你的循环队列实现。 循环队列是一种线性数据结构,其操作表现基于 FIFO(先进先出)原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。
循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里,一旦一个队列满了,我们就不能插入下一个元素,即使在队列前面仍有空间。但是使用循环队列,我们能使用这些空间去存储新的值。
你的实现应该支持如下操作:
MyCircularQueue(k): 构造器,设置队列长度为 k 。
Front: 从队首获取元素。如果队列为空,返回 -1 。
Rear: 获取队尾元素。如果队列为空,返回 -1 。
enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。
deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。
isEmpty(): 检查循环队列是否为空。
isFull(): 检查循环队列是否已满。
来源:力扣(LeetCode)
代码模板:
typedef struct { } MyCircularQueue; MyCircularQueue* myCircularQueueCreate(int k) { } bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) { } bool myCircularQueueDeQueue(MyCircularQueue* obj) { } int myCircularQueueFront(MyCircularQueue* obj) { } int myCircularQueueRear(MyCircularQueue* obj) { } bool myCircularQueueIsEmpty(MyCircularQueue* obj) { } bool myCircularQueueIsFull(MyCircularQueue* obj) { } void myCircularQueueFree(MyCircularQueue* 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); */
分析
tail为队尾,head为队头,如果想出队head就顺时针走,入队tail也是顺时针走,出队的时候不用管里面的数据是什么,因为我们只看head和tail(包括head和tail指向的地方)这段距离中的数据。
我们也不需要考虑扩容的问题。
这里有两种方法,一个是用链表,一个是用顺序表,这里我们用顺序表。
顺序表因为是数组的原因,所以不会有链表那种循环。
一开始head和tail是在同一个点,因为队里没有任何的数据,如果想入队,那么tail往后走一步,head不动:
出队列就是head走一步。
那么,这是个循环队列,head和tail走到末尾之后,再走一步就回到了最开始的地方。
最重要的就是判断队列是否为空,是否满队列,空队列就是head和tail指向了同一个位置,但是如果一直入队,等到满队,条件也是head和tail指向了同一个地方
这样我们就没办法判断倒是是满队还是空队,所以我们需要加一个新的空间,新开出来的空间是缓冲满队列的。
现在tail指向的位置就是多余出来的地方,这7个格子中任何一个地方可能都会是多余的那个,这样判断满队的条件就是tail的下一个是head了。
代码实现
队列的结构体
typedef struct { int* a;//数组的起始位置 int head;//队头 int tail;//队尾 int N;//数组的长度 } MyCircularQueue;
初始化
MyCircularQueue* myCircularQueueCreate(int k) { MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue)); obj->a=(int*)malloc(sizeof(int)*(k+1));//开辟数组的空间,多开辟一个int长度 obj->head=obj->tail=0;//起始位置为下标0 obj->N=k+1; return obj; }
这里开辟的是结构体的空间,因为用malloc开辟不会因为函数的消失而销毁。
判断是否满队,是否空队
空队
bool myCircularQueueIsEmpty(MyCircularQueue* obj) { return obj->head==obj->tail; }
满队
bool myCircularQueueIsFull(MyCircularQueue* obj) { return (obj->tail+1)%obj->N==obj->head; }
满队的判断依据是tail的下一个是haed就为满,但是这里会有边界的问题
紫色的是下标,因为head和tail都是靠下标定位,所以让(tail+1)%7(这里的7是队列长度,只是在假设长度是7)就能让tail指向下标为0的地方,也就是head指向的位置,如果是7以下的数%7,就不会变动。
获取队尾队首元素
队空返回-1.
队首
int myCircularQueueFront(MyCircularQueue* obj) { if(myCircularQueueIsEmpty(obj)) { return -1; } return obj->a[obj->head]; }
队尾
int myCircularQueueRear(MyCircularQueue* obj) { if(myCircularQueueIsEmpty(obj)) { return -1; } return obj->a[(obj->tail-1 + obj->N)%obj->N]; }
我们知道tail-1才是队尾元素的下标,但如果tail等于0,就等于-1了。
这里我们只要让tail加上一个队列长度,在%队列长度就好了。
插入,删除
插入,删除成功返回真,否咋返回假
插入
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) { if(myCircularQueueIsFull(obj)) { return false; } else { obj->a[obj->tail]=value; obj->tail++; obj->tail%=obj->N;//这里也要注意tail不能超过队列长度。 } return true; }
删除
bool myCircularQueueDeQueue(MyCircularQueue* obj) { if(myCircularQueueIsEmpty(obj)) { return false; } else { obj->head++; obj->head%=obj->N;//这里也要注意head不能超过队列长度。 } return true; }
删除直接让head++即可,后面的不会被读取,就算有新的插入也是覆盖掉原来的元素。
销毁队列
void myCircularQueueFree(MyCircularQueue* obj) { free(obj->a); free(obj); }