东营网站建设公司 网络易,唐山专门做网站,一般通过手机号加微信的好友,做网站怎么选空间什么是假溢出#xff1f; 当我们使用队列这种基本的数据结构时#xff0c;很容易发现#xff0c;随着入队和出队操作的不断进行#xff0c;队列的数据区域不断地偏向队尾方向移动。当我们的队尾指针指向了队列之外的区域时#xff0c;我们就不能再进行入队操作了#xff…什么是假溢出 当我们使用队列这种基本的数据结构时很容易发现随着入队和出队操作的不断进行队列的数据区域不断地偏向队尾方向移动。当我们的队尾指针指向了队列之外的区域时我们就不能再进行入队操作了而此时由于队头已经偏离原来位置也就意味着实际上队列并没有满。这种实际上还有空间但是却发生了溢出的现象就称为假溢出现象。 假设有以下队列初始元素为1、2、3、4、5队头元素是1队尾元素是5. 当我们弹出队头元素两次得到队列 这个时候top指针向右边偏移如果再进行入队操作我们会发现rear指针已经不能向后移动了而此时队列并没有满top前面还有空间。
这就是假溢出。
如何解决假溢出问题
为了避免假溢出问题我们需要对队列进行优化--循环队列。 对于前面的问题我们发现导致假溢出的主要问题就是尾指针rear不能指向可以存放空间的地址换句话来说就是不能指向前面已经出队了元素的地址。针对这一问题我们整个队列看成一个可以循环的环状结构指向队头队尾的指针往后走还能回到原来的位置。 这样一来前面已经出队元素的空间我们依旧可以存放元素也就解决了假溢出的问题。这里rear指向队尾元素的下一个元素。
模拟循环队列
首先假设我们队列的最大存储数据个数为k。 用一个数组来模拟循环队列并且初始化容量为k1,队头队尾指针都指向下标为0的元素地址 为什么容量要多一个呢 为了更好的区分队列为空和队列已满。 如何判断循环队列是否为空
if(toprear)为真则队列为空
如何判断循环队列是否为满 由于我们多开辟了一个元素的空间且这个空间不存放元素也就意味着如果已经存了k个元素此时的rear指向这个空的区域rear指向空间的下一个空间的元素被top指针指向。 if((rear1)%(k1)top)//真则队列为满
如何求得循环队列的元素个数
num(reark-top)%(k1)//num为循环队列元素个数
由于rear指针可能在top指针的前面所以我们不能直接使用rear-top. 那么我们可以这么想之所以rear会出现在top前面是因为rear已经走了一圈了假设只多走了一圈那么rear移动的总距离就是当前元素位置加队列长度top移动的距离就是当前下标。 力扣面试题
622. 设计循环队列https://leetcode.cn/problems/design-circular-queue/
代码
typedef struct {int *val;int front;int back;int k;int size;
} MyCircularQueue;MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue *obj(MyCircularQueue *)malloc(sizeof(MyCircularQueue));obj-val(int*)malloc(sizeof(int)*(k1));obj-front0;obj-back0;obj-kk;obj-size0;return obj;
}bool myCircularQueueIsEmpty(MyCircularQueue* obj) {return ((obj-back)(obj-front));
}bool myCircularQueueIsFull(MyCircularQueue* obj) {return (((obj-back1)%(obj-k1))obj-front);
}
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {if(myCircularQueueIsFull(obj))return false;obj-val[obj-back]value;obj-back(obj-back1)%(obj-k1);return true;
}bool myCircularQueueDeQueue(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj))return false;obj-front(obj-front1)%(obj-k1);return true;
}int myCircularQueueFront(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj))return -1;return obj-val[obj-front];
}int myCircularQueueRear(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj))return -1;int kobj-k;return obj-val[(obj-backk)%(k1)];
}void myCircularQueueFree(MyCircularQueue* obj) {free(obj-val);obj-valNULL;free(obj);}
