推荐做网站的话术,去黄山旅游攻略,crm软件哪家好,杰奇网站地图怎么做文章目录 前言描述分析力扣AC代码 力扣#xff1a; 622.设计循环队列
前言
队列会出现“假溢出”现象#xff0c;即队列的空间有限#xff0c;队列是在头和尾进行操作的#xff0c;当元素个数已经达到最大个数时#xff0c;队尾已经在空间的最后面了#xff0c;但是对头… 文章目录 前言描述分析力扣AC代码 力扣 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
分析
在普通的队列中队满的条件是rearfront那么在循环队列中怎么判断队列已经满了
常用的一个解决方法是多开一个空间。也就是说当队列满的时候还是有一个空间没有被使用。 rear可能比front大也可能比front所以尽管它们只相差一个位置时就是满的情但也可能是相差整整一圈所以若队列长度为k那么需要多开辟一个空间即k1。因此队满的额条件为(rear1)%(k1)front。取模“”的目的就是为了整合front和rear大小的问题解决多绕了一圈的问题。
什么时候队列为空呢
rearfront时队列为空。
总结一下就是
当rearfront时队列为空当rear的下一个和front相等则队列满
分析完队满、对空问题回到本道题目就很好解决了。 构造器
MyCircularQueue* obj是一个结构体指针需要给obj开辟一个空间其次开辟一个数组a初始化front 和 back 以及k
MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue* obj(MyCircularQueue*)malloc(sizeof(MyCircularQueue));obj-a(int *)malloc((k1)*sizeof(int));obj-front0;obj-back0;obj-kk;return obj;
}判断队空、队满
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {return obj-frontobj-back;
}bool myCircularQueueIsFull(MyCircularQueue* obj) {return (obj-back1)%(obj-k1)obj-front;
}队尾插入
首先需要判断队列是否已经满了如果满了返回false如果没有执行插入操作。先插入再将队尾obj-back。
需要注意的是这里是一个循环队列如果此时已经在最后一个单元里面插入元素那么obj-back应该是回到前面而不是继续往后。此时有需要用到取模“%”操作使得 obj-back(obj-back)%(obj-k1) bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {if(myCircularQueueIsFull(obj))return false;obj-a[obj-back]value;obj-back;obj-back(obj-back)%(obj-k1);return true;
}队头删除
删除只需要将obj-front即可
但是依然需要注意这是一个循环队列当obj-front在最后一片单元时需要回到前面obj-front(obj-front)%(obj-k1)
bool myCircularQueueDeQueue(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj)){return false;}obj-front;obj-front(obj-front)%(obj-k1);return true;
}取队头元素
先判断队列是否为空不为空执行取队头操作
int myCircularQueueFront(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj))return -1;return obj-a[obj-front];
}取队尾元素
首先判断队列是否为空不为空执行取队尾元素操作
需要注意的是当obj-back0时此时取得应该是最后一个存储单元的元素这里需要单独判断一下其余的情况都是obj-back 前面一个单元的元素。
int myCircularQueueRear(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj)){return -1;}else if(obj-back0){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((k1)*sizeof(int));obj-front0;obj-back0;obj-kk;return obj;
}bool myCircularQueueIsEmpty(MyCircularQueue* obj) {return obj-frontobj-back;
}bool myCircularQueueIsFull(MyCircularQueue* obj) {return (obj-back1)%(obj-k1)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-k1);return true;
}bool myCircularQueueDeQueue(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj)){return false;}obj-front;obj-front(obj-front)%(obj-k1);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-backobj-k)%obj-k1];else if(obj-back0){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);
*/
