基于Java数组实现循环队列

Myth丶恋晨 2023-10-11 22:35 65阅读 0赞

**目录**

循环队列概念

数组实现思路

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

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

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

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

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

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

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

小结

--------------------

### 循环队列概念 ###

用数组实现会面临"假溢出"现象，克服"假溢出"现象的方法是：就是将数组的首尾相连，组成的一个特殊结构。我们用两个指针来表示队列的队首和队尾，front表示队首的元素，rear表示队尾的下一个元素。这里的数组“尾部”的下一个元素就是“首部”，这样就可以很好避免了假溢出的问题。

当rear+1 == front时 就是一个**满的循环队列**

![5d1ec4b01b8e4a99a5d737985a788e79.png][]

当 front `== rear` 时，就是一个 **空的循环队列**

![2faa8391292e4bc18f031c2b1879951c.png][]

对此如何判断空和满是非常重要的 可以设置一个usedsize 记录 这种方法比较简单

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

**设计循环队列**

[622. 设计循环队列 - 力扣（LeetCode）][622. _ - _LeetCode]

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

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

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

### 数组实现思路 ###

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

![322c5a7aae684b4eb577b17eda636ddf.png][]

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

front==rear是为空

![cca7f3a07cf44b93a8c4024f7d2ddd59.png][]

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

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

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

![1e1f72985def49bca6565be031e6b406.png][]

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

#### ![59c4ff8432a44480a2d7139dee0f623e.png][]**enQueue(value): 向循环队列插入一个元素**。 ####

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

![3e7f089fe9c34d05be9c92abc03502c0.png][]

![feb5ac6c6adf4aef935094d6c30865de.png][]

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

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

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

![b93c93148af74fbdb05ee9759ec420ba.png][]

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

![da60d10629a249759cd2b2ada6b1c63d.png][]

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

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

![8e20aab443814e6cafcd48e55e1f1b09.png][]

总代码如下

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** 个空间。

[5d1ec4b01b8e4a99a5d737985a788e79.png]: https://img-blog.csdnimg.cn/5d1ec4b01b8e4a99a5d737985a788e79.png
[2faa8391292e4bc18f031c2b1879951c.png]: https://img-blog.csdnimg.cn/2faa8391292e4bc18f031c2b1879951c.png
[622. _ - _LeetCode]: https://leetcode.cn/problems/design-circular-queue/
[322c5a7aae684b4eb577b17eda636ddf.png]: https://img-blog.csdnimg.cn/322c5a7aae684b4eb577b17eda636ddf.png
[cca7f3a07cf44b93a8c4024f7d2ddd59.png]: https://img-blog.csdnimg.cn/cca7f3a07cf44b93a8c4024f7d2ddd59.png
[1e1f72985def49bca6565be031e6b406.png]: https://img-blog.csdnimg.cn/1e1f72985def49bca6565be031e6b406.png
[59c4ff8432a44480a2d7139dee0f623e.png]: https://img-blog.csdnimg.cn/59c4ff8432a44480a2d7139dee0f623e.png
[3e7f089fe9c34d05be9c92abc03502c0.png]: https://img-blog.csdnimg.cn/3e7f089fe9c34d05be9c92abc03502c0.png
[feb5ac6c6adf4aef935094d6c30865de.png]: https://img-blog.csdnimg.cn/feb5ac6c6adf4aef935094d6c30865de.png
[b93c93148af74fbdb05ee9759ec420ba.png]: https://img-blog.csdnimg.cn/b93c93148af74fbdb05ee9759ec420ba.png
[da60d10629a249759cd2b2ada6b1c63d.png]: https://img-blog.csdnimg.cn/da60d10629a249759cd2b2ada6b1c63d.png
[8e20aab443814e6cafcd48e55e1f1b09.png]: https://img-blog.csdnimg.cn/8e20aab443814e6cafcd48e55e1f1b09.png