我们使用多开一个空间的方法来进行空和满的判断 , 如果我们不多开一个空间在rear 添加完最后一个元素时向后走此时front和rear一样和判断满的条件是一样的此时我们就没办法判断是空还是满所以，我们的 rear 永远是指向 最后一个元素的下一个位置。
重点:循环队列，无论使用数组实现还是链表实现，都要多开一个空间，也就意味着，要是一个存k个数据的循环队列，要开k+1个空间，否则无法实现判空和满

设计循环队列

622. 设计循环队列 - 力扣（LeetCode）

设计你的循环队列实现。循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。

循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。

MyCircularQueue(k): 构造器，设置队列长度为 k 。
Front: 从队首获取元素。如果队列为空，返回 -1 。
Rear: 获取队尾元素。如果队列为空，返回 -1 。
enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。
deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。
isEmpty(): 检查循环队列是否为空。
isFull(): 检查循环队列是否已满。

数组实现思路

既然我们要用数组实现这个循环队列那我们先创建一个数组elem 和头尾指向front和rear

isEmpty(): 检查循环队列是否为空

front==rear是为空

isFull(): 检查循环队列是否已满

我们利用下面取余的方法可以判断rear的下一个位置是否为front

如果是则满 (rear+1)%elem.length == front

MyCircularQueue(k): 构造器，设置队列长度为 k 。

enQueue(value): 向循环队列插入一个元素。

如果成功插入则返回真. 我们需要判断这个数组是否已经满了所以用isFull方法判断如果已经满了返回false 如果没满则在 rear尾位置将value添加进去, 重点是rear向后移动的过程,如果我们写成rear++,那么将在数组最后尾位置出现错误在下标7的时候加1是无法回到0下标的,所以我们可以用取余的方法令rear = (rear+1)%elem.length;

deQueue(): 从循环队列中删除一个元素。

如果成功删除则返回真先进行是否为空的判断

如果为空则直接返回false 如果不为空则让front向后移动便可实现删除操作依旧是利用取余的方法进行移动

Front: 从队首获取元素。如果队列为空，返回 -1 。

Rear: 获取队尾元素。如果队列为空，返回 -1 。

此时需要注意的是当我们的rear=0 的时候循环队列中，因为rear永远指向 最后一个元素的下一个位置。所以我们需要往前走一个位置但是如何从0下标走回前一个下标7,如果是0-1的话那就是负数了所以我们分情况处理一下 rear为0时和不为0时.

总代码如下


 class MyCircularQueue {
        int[] elem;
        int front;
        int rear;
 
        public MyCircularQueue(int k) {
            this.elem = new int[k];
        }
 
        public boolean enQueue(int value) {
            if (isFull()){
                return false;
            }
                elem[rear] = value;
            rear = (rear+1)%elem.length;
            return true;
        }
 
        public boolean deQueue() {
            if (isEmpty()){
                return false;
            }
            front = (front+1)%elem.length;
            return true;
        }
 
        public int Front() {
            if (isEmpty()){
                return -1;
            }
            return elem[front];
        }
 
        public int Rear() {
            if (isEmpty()){
                return -1;
            }
            int dex = (rear == 0)?elem.length-1:rear-1;
            return elem[dex];
        }
 
        public boolean isEmpty() {
            return front == rear;
        }
 
        public boolean isFull() {
            if ((rear+1)%elem.length == front){
                return true;
            }
            return false;
        }
    }

小结

循环队列中，rear永远指向 最后一个元素的下一个位置。

循环队列中，永远要 多开一个空间，假设需要存储的元素有 7 个，那么需要开辟 8 个空间。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/IT小白/article/detail/582706