网站 建设方案,报价单表格怎么制作,公众号用什么软件制作最好,河南最新任命12个厅级笔者在之前的一篇文章#xff0c;详细的介绍了#xff1a;队列之单向链表与双向链表的模拟实现#xff1a;https://blog.csdn.net/weixin_64308540/article/details/128742090?spm1001.2014.3001.5502 感兴趣的各位老铁#xff0c;可以参考一下啦#xff01;下面进入循环…笔者在之前的一篇文章详细的介绍了队列之单向链表与双向链表的模拟实现https://blog.csdn.net/weixin_64308540/article/details/128742090?spm1001.2014.3001.5502 感兴趣的各位老铁可以参考一下啦下面进入循环队列的讲解部分对于队列在这个之前我们就已经知道需要用数组来实现数组实际中我们有时还会使用一种队列叫循环队列。如操作系统课程讲解生产者消费者模型时可以就会使用循环队列。 环形队列通常使用数组实现。 当我们给其下标的时候假设我们在里面存储数据的时候每次存储一个数据那么rear就往后走一步当这个情况下rear从7下标如何到0下标怎么过去假设rear从7下标已经到0下标那么此时到底是满了还是没满这也是一个值得思考的问题需要注意以下的这种情况在这种情况下当我们一边存储一边删除那么就会出现不是在0下标相遇的情况因此我们需要注意这种情况下如何判断循环列表是否已经存储满了呢解决方案对于问题1我们可以用rear(rear1)%lengthlength表示数组长度这样就可以实现数组下标的跨越对于问题2我们可以定义usedSize记录存储的有效数据通过usedSize与数组的长度相比那么我们就可以清晰的得出循环列表是否存储满的结论对于如何判断循环列表满的情况我们可以用牺牲一个空间来表示满在这个思路过程中我们可以让rear先走一步看看是否与front相遇若相遇上图的情况则为满在上图中我们牺牲rear所对应的空间来表示满经过上述的讲解那么我们已经知道了循环列表的操作及其思路接下来我们就可以设计循环队列了622. 设计循环队列 - 力扣LeetCode622. 设计循环队列难度中等440收藏分享切换为英文接收动态反馈设计你的循环队列实现。 循环队列是一种线性数据结构其操作表现基于 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 提示所有的值都在 0 至 1000 的范围内操作数将在 1 至 1000 的范围内请不要使用内置的队列库。经过上述 的题目分析我们可以写出一下的简单代码首先根据题目中的代码我们定义了一个MyCircularQueue的类然后我们开始进行代码的准备阶段 private int[] elem;//数组private int front;//表示列表的头private int rear;//表示列表的尾在之前的分析中我们知道循环队列的底层是一个数组因此我们第一了一个数组一个front表示列表的头rear表示列表的尾根据构造器来定义数组的长度为k但是由于我们所用的是浪费一个空间来表示满的情况因此我们需要多定义一个数组的长度k1 //构造器设置队列的长度为kpublic MyCircularQueue(int k){//如果是浪费空间这里必须多加一个this.elemnew int[k1];}入队列向循环列表中插入一个元素如果插入成功则返回true //入队列向循环列表中插入一个元素如果插入成功则返回truepublic boolean enQueue(int value){//检查队列是否为满if (isFull()){return false;//在不扩容的情况下满了就不能入}//在队列不满的情况下elem[rear]value;//存放数据rear(rear1)%elem.length;//确保循环return true;}在这个里面我们用了一个检查队列是否为满的判断所以…… //检查循环队列是否为满public boolean isFull(){//第一种写法if ((rear1)%elem.lengthfront){return true;}return false;//第二种写法//return (rear1)%elem.lengthfront;}
其实这个第二种的写法很简单很简单从循环队列中删除一个元素如果成功删除则返回true //从循环队列中删除一个元素如果成功删除则返回truepublic boolean deQueue(){if (isFull()){return false;}front(front1)% elem.length;return true;}对于上述的这个代码通过front往后走了一步此时数据还在循环队列里面但是由于没有记录下来所以便就相当于删除了从队列的队首获取元素如果队列为空则返回-1 //从队列的队首获取元素如果队列为空则返回-1public int Front(){if (isFull()) {return -1;}//得到对头元素return elem[front];}这个代码很简单笔者就不再详细的介绍了获取队列的队尾元素如果队列为空则返回-1 //获取队列的队尾元素如果队列为空则返回-1public int Rear(){if (isEmpty()){return -1;}//得到队尾元素int index(rear0)?elem.length-1 :rear-1;return elem[index];}对于这个问题我们需要思考的是rear在0下标的时候若直接返回elem[rear-1]可能会造成越界因此我们才有着上述的 int index(rear0)?elem.length-1 :rear-1; return elem[index];在上述的过程中我们使用了检查数组是否为空的情况isEmpty() //检查数组是否为空public boolean isEmpty(){return frontrear;//相遇}上述便是我们的全部思路因此我们的整体代码为public class MyCircularQueue {private int[] elem;//数组private int front;//表示列表的头private int rear;//表示列表的尾//构造器设置队列的长度为kpublic MyCircularQueue(int k) {//如果是浪费空间这里必须多加一个this.elem new int[k 1];}//入队列向循环列表中插入一个元素如果插入成功则返回truepublic boolean enQueue(int value) {//检查队列是否为满if (isFull()) {return false;//在不扩容的情况下满了就不能入}//在队列不满的情况下elem[rear] value;rear (rear 1) % elem.length;return true;}//检查循环队列是否为满public boolean isFull() {//第一种写法if ((rear 1) % elem.length front) {return true;}return false;//第二种写法//return (rear1)%elem.lengthfront;}//从循环队列中删除一个元素如果成功删除则返回truepublic boolean deQueue(){if (isFull()){return false;}front(front1)% elem.length;return true;}//从队列的队首获取元素如果队列为空则返回-1public int Front(){if (isFull()) {return -1;}//得到对头元素return elem[front];}//获取队列的队尾元素如果队列为空则返回-1public int Rear(){if (isEmpty()){return -1;}//得到队尾元素int index(rear0)?elem.length-1 :rear-1;return elem[index];}//检查数组是否为空public boolean isEmpty(){return frontrear;//相遇}
}
若有不懂得地方可以私聊我一下
