LeetCode第622题—设计循环队列

本次写的题目是设计循环队列，为LeetCode里面的题目，让我们来康康是如何解出这道题目的吧，各位尚没有思路的小伙伴可以跟随着博主的解题思路一步步来，感受一下😎

🌱分析阶段

首先来看看题目吧~

在本道题目中，看到了两组关键字，首先是“循环”，然后是“队列”。在学习完了顺序表，链表，栈等知识后，发现没有一个直接的数据结构可以让我们来实现对队列的仿写。于是决定制作一个循环数列，来仿写该队列，具体图示如下👇：

在本文中front是队头，rear表示队尾。制作这样子的循环数组我们需要先解决下面两个问题：

1. 当rear下标到达7的时候，如何从7位置到0位置上？
2. 我们要如何判断数组是空还是满？

首先解决问题1️⃣，问题一的解决只需要用到一个公式：rear = （rear+1）%数组长度；只要rear每往下走一步，我们就用这个公式来计算rear的位置，从而代替 rear = rear++  这一行代码。

然后解决问题2️⃣，问题二的解决方法有三个：①设立一个flag，作为记录；②实际长度==数组长度；③将图中的front的前一个位置空出来，等到rear到达front前一个位置的时候就证明已经满了。在这里问题二的解决我们采用第三种方法。

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

首先来讲解一下第三种方法😎：

第三种方法相当于在front位置的前一个位置上设立了一个警戒线（该位置不放数据），如果rear已经到达那个警戒线，我们发现rear再走下一步就到了front的位置的时候，就证明数组已经放满。

考虑到要从7到0的移动，且要用于判定下一个是不是front位置或者rear位置，在这里我们使用  rear = （rear + 1）%  数组长度  和   front = （front + 1）%  数组长度  来使rear、front往下一步走。

以上便是全部的分析阶段，在分析完上面后，我们写代码思路会变的非常清晰😎 

---

🌱代码阶段

首先我们需要一个数组，创建一个数组，先不设置大小，然后再创建两个int变量，分别命名为front和rear。我们又知道，题目中有个构造函数，我们的数组大小再构造函数内创建👇：

class MyCircularQueue {
 
    public int[] elem;
    public int front;
    public int rear;
 
    public MyCircularQueue(int k) {
        elem = new int[k];
    }
    //暂时把其他函数给省略
}

在创建完后，我们开始写各个函数的代码是😎

---

🍃enQueue函数

创建enQueue函数过程蛮简单，就是先判定队列有没有满，如果满了就返回false；如果没满就放入数据，然后rear用之前分析阶段提出的公式往后走一步👇

class MyCircularQueue {
 
    public int[] elem;
    public int front;
    public int rear;
 
    public MyCircularQueue(int k) {
        elem = new int[k];
    }
    
    public boolean enQueue(int value) {
        if(isFull()){
            return false;
        }
        elem[rear] = value;    //入队
        rear = (rear+1)%elem.length;    //rear往下走一步
        return true;
    }
    //其他未写函数暂时省略
}

---

🍃isFull函数

这个需要用到判断rear的下一个位置是不是front位置的函数，具体代码如下👇：

class MyCircularQueue {
 
    public int[] elem;
    public int front;
    public int rear;
 
    public MyCircularQueue(int k) {
        elem = new int[k];
    }
    
    public boolean enQueue(int value) {
        if(isFull()){
            return false;
        }
        elem[rear] = value;    //入队
        rear = (rear+1)%elem.length;    //rear往下走一步
        return true;
    }
    
    public boolean isFull() {
        if((rear+1)%elem.length==front){    //若rear的下一个位置是front，结果为满，则返回true
            return true;
        }
        return false;
    }
}

---

🍃isEmpty函数

这个函数的判断很简单，当front和rear的位置相同的时候，就可以说明此时是空的数组。

class MyCircularQueue {
 
    public int[] elem;
    public int front;
    public int rear;
 
    public MyCircularQueue(int k) {
        elem = new int[k];
    }
    
    public boolean enQueue(int value) {
        if(isFull()){
            return false;
        }
        elem[rear] = value;    //入队
        rear = (rear+1)%elem.length;    //rear往下走一步
        return true;
    }
    
    public boolean isEmpty() {
        return rear==front;
    }
 
    public boolean isFull() {
        if((rear+1)%elem.length==front){    //若rear的下一个位置是front，结果为满，则返回true
            return true;
        }
        return false;
    }
}

---

🍃deQueue函数

这个函数是出队列的意思，我们的第一步是判断数组是不是为空，如果是空则直接返回false；如果不是再将front往前移动一个位置。具体代码如下👇：

class MyCircularQueue {
 
    public int[] elem;
    public int front;
    public int rear;
 
    public MyCircularQueue(int k) {
        elem = new int[k];
    }
    
    public boolean enQueue(int value) {
        if(isFull()){
            return false;
        }
        elem[rear] = value;    //入队
        rear = (rear+1)%elem.length;    //rear往下走一步
        return true;
    }
    
    public boolean isEmpty() {
        return rear==front;
    }
 
    public boolean deQueue() {
        if(isEmpty()){
            return false;
        }
        front = (front+1)%elem.length;
        return true;
    }
 
    public boolean isFull() {
        if((rear+1)%elem.length==front){    //若rear的下一个位置是front，结果为满，则返回true
            return true;
        }
        return false;
    }
}

---

🍃front函数

首先要注意，该队列中不能为空，如果判定为空了，那么我们要返回-1（题目要求）。

然后要返回front位置的元素，这里直接返回即可。具体代码如下👇：

class MyCircularQueue {
 
    public int[] elem;
    public int front;
    public int rear;
 
    public MyCircularQueue(int k) {
        elem = new int[k];
    }
    
    public boolean enQueue(int value) {
        if(isFull()){
            return false;
        }
        elem[rear] = value;    //入队
        rear = (rear+1)%elem.length;    //rear往下走一步
        return true;
    }
    
    public boolean isEmpty() {
        return rear==front;
    }
 
    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 boolean isFull() {
        if((rear+1)%elem.length==front){    //若rear的下一个位置是front，结果为满，则返回true
            return true;
        }
        return false;
    }
}

---

🍃rear函数

首先要注意，该队列中不能为空，如果判定为空了，那么我们要返回-1（题目要求）。

这里我们要注意的是，由于再前面我们写的enQueue入队函数的机制是在添加完一个元素后rear往下走，此时rear的位置处是还未放入数据的，所以我们要弹出的是rear-1处位置的元素。还要特别注意的是，当rear==0时不能减一，否则就变为-1了，所以我们要分情况讨论。这时就可以用到三目表达式。具体代码如下👇：

class MyCircularQueue {
 
    public int[] elem;
    public int front;
    public int rear;
 
    public MyCircularQueue(int k) {
        elem = new int[k];
    }
    
    public boolean enQueue(int value) {
        if(isFull()){
            return false;
        }
        elem[rear] = value;    //入队
        rear = (rear+1)%elem.length;    //rear往下走一步
        return true;
    }
    
    public boolean isEmpty() {
        return rear==front;
    }
 
    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;
        }
        //设置一个index作为记录返回的位置
        int index = (rear==0) ? elem.length-1 : rear-1 ;
        return elem[index];
    }
 
    public boolean isFull() {
        if((rear+1)%elem.length==front){    //若rear的下一个位置是front，结果为满，则返回true
            return true;
        }
        return false;
    }
}

至此，所有函数都大致完成了，但还有一处错误，让我们先运行逝逝😎

出现了如上错误，让我们来分析一下👇

原因是我们空了一个位置出来，所以在创建数组的时候要变成k+1，所以完整代码如下👇：

class MyCircularQueue {
 
    public int[] elem;
    public int front;
    public int rear;
 
    public MyCircularQueue(int k) {
        elem = new int[k+1];    //注意这里要k+1大小，因为我们采用了空一格位置不放元素的方法。
    }
    
    public boolean enQueue(int value) {
        if(isFull()){
            return false;
        }
        elem[rear] = value;    //入队
        rear = (rear+1)%elem.length;    //rear往下走一步
        return true;
    }
    
    public boolean isEmpty() {
        return rear==front;
    }
 
    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;
        }
        //设置一个index作为记录返回的位置
        int index = (rear==0) ? elem.length-1 : rear-1 ;
        return elem[index];
    }
 
    public boolean isFull() {
        if((rear+1)%elem.length==front){    //若rear的下一个位置是front，结果为满，则返回true
            return true;
        }
        return false;
    }
}

以上！便是全部代码了😎来运行一下逝逝吧~

 nice😎✨